PaperlayerView exact revision on arXiv

Source-linked AI summary

Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes

Yue Wang, George Atia

arXiv:2609.28792v1cs.LG

TL;DR

State-dependent long-run rewards under transition uncertainty call for a vector Bellman theory for robust average-reward MDPs. The paper develops a gain-first, bias-second certificate and characterizes when it is finite. Finite certificates identify the optimal gain and support undiscounted planning with eventually average-optimal greedy controllers.

  • Problem

    Robust average-reward MDPs can have optimal long-run rewards that depend on the initial state, requiring a theory that handles recurrent-class rewards alongside transition uncertainty.

    Source: §1 · p. 1

  • Method

    A coupled vector gain-bias Bellman system gives continuation gain priority over reward bias and is paired with solvability conditions based on stationary gain attainment and bounded canonical transient corrections.

    Source: §1 · p. 2, §4.1 · p. 4

  • Results

    Every finite Bellman solution identifies the optimal robust gain and supplies all-state stationary saddle strategies against history-dependent opponents.

    Source: §4.1 · p. 5

  • Takeaways & Limitations

    Under finite Bellman solvability, approximately shifted Halpern iteration recovers the optimal gain vector and its extracted greedy controllers are eventually average-optimal.

    Source: §1 · p. 2, §7 · p. 8

    A prescribed average-optimal controller or stationary saddle need not share a finite Bellman bias, even when another pair supports a certificate.

    Source: §4.1 · p. 5, §5 · p. 6

Abstract

from arXiv · show

Robust average-reward Markov decision processes provide a fundamental framework for long-term performance optimization under uncertainty, and can have optimal long-run rewards that depend on the initial state. This state dependence requires a vector Bellman theory that accounts for both recurrent-class rewards and transition uncertainty. We develop such a theory for finite models with compact, post-action $(s,a)$-rectangular ambiguity. A gain-first, bias-second optimization principle yields a coupled vector gain-bias system, and every finite solution identifies the optimal robust gain and supplies stationary saddle strategies against history-dependent opponents, simultaneously from all initial states. We further characterize solvability through stationary gain conditions and a uniform bound on canonical transient corrections, and give sufficient conditions that permit distinct recurrent-class gains. The certificates also yield asymptotically affine trajectories of the robust Bellman operator, based on which we design a robust approximately shifted Halpern planning algorithm. Under finite Bellman solvability, the gain estimates and Bellman displacements converge to the optimal gain vector, and every extracted greedy controller is average-optimal after a finite, instance-dependent budget. These results thus connect finite Bellman certificates to undiscounted planning for state-dependent robust average rewards, providing theoretical understandings.

1 Introduction

Robust average-reward control must handle uncertain transitions and long-run rewards that can vary by initial state. The paper develops a vector Bellman theory, characterizes finite solvability, and uses its certificates for undiscounted planning.

1 Introduction

  • Initial states can have different long-run gains because they may reach recurrent classes with different rewards and absorption probabilities.Under uncertainty, stationary gains can change abruptly when transition probabilities vanish, motivating an all-state gain-bias formulation.Source: §1 · p. 1
  • The paper’s coupled vector Bellman certificate optimizes continuation gain before reward bias and yields all-state stationary saddle strategies against history-dependent opponents.Every finite solution identifies the robust optimal gain.Source: §1 · p. 2
  • The solvability criterion combines stationary gain attainment with a uniform lower bound on canonical biases over zero-gain replies to a securing controller.Polytopic row sets, a uniform support gap, and several distributional ambiguity sets are sufficient regimes permitting distinct recurrent-class gains.Source: §1 · p. 2
  • Under finite Bellman solvability, approximately shifted Halpern iteration yields convergent gain estimates and Bellman displacements, with extracted greedy controllers eventually average-optimal.The analysis gives finite-budget bounds in terms of the affine defect and examples with arbitrarily small algebraic convergence exponents for the gain estimator.Source: §1 · p. 2

2 Problem Formulation and Preliminaries

The paper formulates a finite robust MDP in which the controller acts before nature selects an uncertain transition row. It studies statewise average-payoff values and saddle strategies across stationary and history-dependent strategy classes.

2 Problem Formulation and Preliminaries

  • The model has finite states and actions, nonempty compact transition-row sets, and (s, a)-rectangular ambiguity.At each stage, nature observes the chosen action before selecting a transition row.Source: §2 · p. 2
  • The objective is to maximize worst-case long-run reward, with deterministic stationary, randomized stationary, and randomized history-dependent controller strategies distinguished.Nature’s full stationary selectors specify rows for every state-action pair, including actions unused by a controller.Source: §2 · p. 2
  • The robust Bellman maps follow the within-stage order: the controller chooses an action, then nature chooses a row after observing it.The supplied passages introduce the resulting one-step saddle operators but do not preserve their formulas clearly.Source: §2 · p. 3
  • A stationary pair’s gain vector is an absorption-weighted average of recurrent-class rewards, so its coordinates can depend on the initial state.An all-state saddle requires the controller and nature strategies to satisfy the payoff inequalities for every initial state and opponent strategy.Source: §2 · p. 3

3 Statewise values and stationary strategies

The paper establishes statewise robust gains and stationary strategies that secure them from every initial state. The optimal gain has discounted-value, finite-horizon, and policy-optimization characterizations.

3 Statewise values and stationary strategies

  • For any stationary controller, its robust gain is the common normalized discounted and finite-horizon limit and the worst-case value under four payoff conventions.For every positive tolerance, one stationary nature selector simultaneously approximates the gain vector across states.Source: §3 · p. 3
  • The optimal robust gain is the coordinatewise maximum over deterministic stationary controllers and the limit of normalized discounted and finite-horizon values.One deterministic stationary controller attains every coordinate of the optimal gain vector.Source: §3 · p. 4
  • For each tolerance, one stationary nature selector and a common horizon threshold secure the finite-horizon guarantee for every initial state and history-dependent opponent.The controller remains the same across tolerances, while nature’s approximating selector may depend on the tolerance.Source: §3 · p. 4
  • The optimal gain vector is the common lower and upper value under all four payoff conventions, and the same controller is optimal in each case.The result also holds for intermediate strategy classes containing deterministic stationary controllers and stationary nature selectors, respectively.Source: §3 · p. 4

4 Vector Bellman equation system

The vector Bellman system prioritizes continuation gains before reward biases, and every finite solution certifies the optimal robust gain. It also links the certificate to the original Bellman operator and to fixed-policy guarantees.

4 Vector Bellman equation system

  • The vector formulation addresses multichain rewards, where different recurrent classes can have different gains, rather than assuming a constant gain across states.For singleton row sets it reduces to classical multichain MDP equations; with constant gain it becomes the robust constant-gain Bellman equation.Source: §4.1 · pp. 4–5

4.1 Robust Bellman optimality system: Gain first, bias second

  • The coupled system first enforces continuation-gain consistency, then balances reward and bias among gain-optimal actions and rows.Both gain restrictions are necessary: omitting either can certify an incorrect gain.Source: §4.1 · pp. 4–5
  • Every finite solution identifies the optimal robust gain and yields a deterministic stationary controller and stationary nature selector forming an all-state saddle against history-dependent opponents.The pair achieves the optimal robust average reward from every initial state.Source: §4.1 · p. 5
  • For large t, the original Bellman operator follows an asymptotically affine trajectory: T(h + tg) = h + (t + 1)g + o(1).Actions with fixed continuation-gain disadvantages cease to compete, although an optimizing row may remain outside its gain face at every finite t.Source: §4.1 · p. 5
  • A finite bias imposes one-step compatibility beyond average optimality, so a prescribed optimal controller or stationary saddle may not share a Bellman bias even when another solution exists.Biases can also retain harmonic directions after fixing a reference state.Source: §4.1 · p. 5

4.2 Fixed-policy equation

  • For a fixed stationary randomized controller, a finite Bellman pair certifies its robust gain and a stationary nature selector that attains both worst-case limits from every initial state.The same finite pair certifies the complete statewise gain vector.Source: §4.2 · pp. 5–6

5 Exact stationary conditions for solvability

Finite Bellman solvability requires stationary gain attainment together with control of transient reward corrections. The paper gives exact stationary criteria and sufficient regimes that can allow distinct recurrent-class gains.

Fixed-policy solvability

  • For a fixed policy, finite solvability requires a stationary nature selector attaining the robust gain and a uniform lower bound on its canonical corrections.Every finite solution has gain equal to the policy's robust gain.Source: §5 · p. 6

Exact optimal-control solvability

  • The optimal-control criterion centers rewards at the candidate gain and tests a zero-gain problem on gain-restricted actions and rows.A stationary saddle secures zero gain, while transient-correction bounds determine whether that saddle has a finite Bellman representation.Source: §5 · p. 6
  • For optimal control, a finite Bellman solution is equivalent to a stationary saddle in the gain-restricted game plus a uniform one-sided bound on canonical transient biases.The bound addresses transient control separately from stationary gain attainment; bounded iterates and finite lower and upper Bellman bounds are equivalent criteria.Source: §5 · p. 6

Sufficient regimes for solvability

  • Polytopic row sets, a uniform support gap, or continuous stationary projections each suffice for a finite Bellman solution, including cases with distinct recurrent-class gains.A uniform support gap implies continuous stationary projections; these regimes also control discounted values after centering by the gain vector.Source: §5 · p. 7

Distributional uncertainty sets

  • Total-variation ambiguity balls are polytopic, while forward KL balls satisfy the support-gap condition under the stated radius bound and support-restricted reverse KL balls do so at every finite radius.The passage also reports an unsolvable example when the forward KL radius condition fails.Source: §5 · p. 7

Further structure of Bellman certificates

  • For compatible controller–nature pairs, the analysis characterizes minimum bias span and shows that recurrent-class offsets can remain after fixing one reference state.An average-optimal pair may fail to share a Bellman bias even when another pair supports a finite certificate.Source: §5 · pp. 6–7

Solvability boundary

  • A robust gain and an all-state optimal stationary controller can exist even when the vector Bellman system has no finite solution.The paper contrasts this with nominal finite-state, finite-action MDPs, which always admit multichain gain-bias solutions.Source: §5 · p. 7

6 Planning from Finite Bellman Certificates

A finite Bellman certificate lets approximately shifted Halpern iteration plan directly with the robust, undiscounted operator despite state-dependent gain. Under finite solvability, its gain and displacement estimates converge, and its greedy controllers are eventually optimal from every state.

Planning from Finite Bellman Certificates

  • The algorithm estimates vector gain with xN/N, then anchors a second phase at xN and shifts robust Bellman updates by that estimate.It assumes the robust Bellman operator can be computed and applied exactly.Source: §6 · pp. 7–8
  • A finite solution guarantees a finite threshold after which every output controller is optimal from every initial state against history-dependent nature.The threshold is instance-dependent; the theorem does not assert a uniform budget.Source: §6 · p. 7
  • A finite solution yields comparison trajectories with vanishing affine defect, but compact ambiguity can prevent exact affine behavior at every finite time.The analysis retains this defect to establish convergence of both Bellman displacement and gain estimates.Source: §6 · p. 8
  • State-dependent gain retains vector drift after scalar normalization, so the method estimates the vector displacement rather than reducing planning to a fixed point modulo constants.This distinguishes its planning target from constant-gain approaches.Source: §6 · p. 8

7 Conclusion

The paper develops a vector gain-bias certificate for finite robust average-reward MDPs with compact post-action rectangular ambiguity, covering state-dependent gains. It also studies when the certificate exists and how it supports direct undiscounted planning, with numerical stress tests against nominal planning.

7 Conclusion

  • The coupled gain-bias system preserves gain priority for both players, certifies stationary saddle strategies against history-dependent opponents, and applies simultaneously from every initial state.Its solvability criterion links stationary gain attainment to uniform control of canonical transient corrections.Source: §7 · p. 8

A.1 Transition ambiguity, rectangularity, and dynamic consistency

  • Post-action (s, a)-rectangular ambiguity lets nature choose rows after observing the state and action, determining the Bellman operator’s optimization order.The paper distinguishes this stagewise model from coupled uncertainty and stationary-kernel choices.Source: §A.1 · p. 13

A.2 Multichain average reward and stochastic-game values

  • In multichain models, recurrent-class rewards and absorption probabilities determine a potentially state-dependent gain; the vector Bellman system compares continuation gains before rewards and biases.Earlier robust Bellman results often assume a state-independent gain, while some polytopic models already admit multichain planning.Source: §A.2 · pp. 13–14

A.3 Finite biases, nonlinear operators, and feasibility geometry

  • Finite bias solvability requires stationary gain attainment and uniform bounds on canonical transient corrections; pointwise finite biases for each kernel are insufficient.The robust control criterion also requires compatible controller and nature choices and a common bias bound.Source: §A.3 · p. 14
  • The robust max-min operator need not be convex, so the analysis uses selector pairs, induced-chain Poisson representations, and both players’ deviation inequalities to test a shared finite bias.Compact-row feasibility can involve infinitely many deviation constraints despite finitely many bias coordinates.Source: §A.3 · p. 14

A.4 Direct planning and anchored iterations

  • For compact row sets, planning tracks a vanishing affine defect rather than relying on an eventually exact invariant half-line.Existing robust Bellman update methods do not alone establish undiscounted multichain convergence, and efficient implementation depends on ambiguity-set representation.Source: §A.4 · pp. 14–15

B Numerical experiments

  • The numerical tests use three finite-certificate stress models: curved ambiguity with boundary leakage, curved ambiguity with periodic classes, and a polytopic safe-risky decision.Midpoint nominal parameters favor an action with smaller worst-case gain in these models.Source: B Numerical experiments · p. 15

B.2 Model I: boundary leakage

  • In the boundary-leakage model, the nominally preferred risky action has robust loss 2, while the curved action’s optimal gain is 0.The immediate reward of 10 affects transient decisions but not the long-run average after absorption.Source: §B.2 · p. 17

B.5 Results and interpretation

Across all three stress models, Algorithm 1’s extracted controllers attain the optimal robust gain, while the nominal baseline retains lower worst-case gains. Its joint robust-target errors are small at the largest tested budget, although convergence is asymptotic rather than necessarily monotone.

B.5 Results and interpretation

  • At every tested budget, Algorithm 1 selects optimal controllers in Models II and III, and does so in Model I for N ≥ 3.Figure 1 pairs joint error with robust controller gain; the dashed line marks the Bellman-equation optimum.Source: §B.5 · p. 18
  • The nominal baseline’s final robust gains are −2, −1, and 0.1, versus optimal gains 0, −3/40, and 0.4 in Models I–III.It selects the risky controller at every tested budget in Models I and III, and from N ≥ 4 in Model II.Source: §B.5 · p. 18
  • At N = 16384, Algorithm 1’s joint errors are approximately 5.51 × 10−3, 6.10 × 10−5, and 2.44 × 10−5 in Models I–III.Figure 2 separates gain-estimation, displacement, and own-objective errors; convergence for the nominal reference model does not ensure robust performance.Source: §B.5 · p. 18, Figure 2 · p. 18

C Preliminaries and applicability of prior results

The appendix verifies that standard rectangular dynamic programming and compact-action results apply to the paper’s post-action model. It supplies finite-chain and pathwise facts used in the Bellman arguments, including cases with periodic recurrent classes.

C Preliminaries and applicability of prior results

  • Weak duality and letting ξ decrease to zero establish stationary duality for the original row sets without convexification.The finite restriction retains selected rows and uses finite perfect-information game duality.Source: C Preliminaries and applicability of… · p. 19

C.1 Rectangular dynamic programming and the fixed-policy reduction

  • Rectangular dynamic programming gives order-preserving, additively homogeneous, sup-norm nonexpansive Bellman maps, whose discounted versions are contractions.For finite state and action spaces, deterministic stationary discounted-optimal selectors work simultaneously from every state.Source: §C.1 · p. 19

C.2 Finite-chain facts used by the Bellman arguments

  • For a finite chain, the canonical bias solves the Poisson equation with zero recurrent-class projection, and the result does not require irreducibility or aperiodicity.The long-run average equals the recurrent class’s invariant mean, including for periodic classes.Source: §C.2 · p. 20

C.3 The pathwise one-player input

  • Compact-action one-player payoff results provide pathwise endpoints for the two applications, independently of convergence of expected finite-horizon averages.The fixed-policy tuple reduction preserves the state-process law for history-dependent randomized nature; sampled-action reward differences vanish in average by the martingale strong law.Source: §C.1 · p. 19, §C.3 · p. 20

D Proof of Theorem 1: policy evaluation

For a fixed stationary controller, the robust gain is the common normalized discounted and finite-horizon limit. Finite-horizon guarantees approach that gain across states and nature’s strategies.

D Proof of Theorem 1: policy evaluation

  • The Tauberian argument transfers a normalized discounted limit to convergence of the Bellman iterates F^N0/N to the same vector.The passage states that no definability assumption is needed.Source: D Proof of Theorem 1: policy evaluation · p. 21
  • (Tπ)^N0/N converges to gπ, and sufficiently long horizons guarantee every state at least gπ_i − δ against every history-dependent nature strategy.The stationary and history-dependent infima of all four average-payoff conventions equal gπ.Source: D Proof of Theorem 1: policy evaluation · p. 21
  • A fixed stationary policy’s robust gain is shared by the stationary and history-dependent infima under all four average-payoff criteria.The result also gives a uniform finite-horizon guarantee over states and history-dependent nature strategies.Source: D Proof of Theorem 1: policy evaluation · p. 21

E Proof of Theorem 2: uniform control

The proof constructs common stationary strategies to secure the optimal gain simultaneously across states. It then establishes the result across payoff conventions and characterizes stationary-policy optimality through discounted gains.

E Proof of Theorem 2: uniform control

  • Theorem 7 establishes uniform finite-horizon bounds, with a common controller and an approximate minimizing selector that work across states.The proof uses a full-support initial law to turn weighted guarantees into simultaneous statewise guarantees.Source: E Proof of Theorem 2: uniform control · pp. 21–22

F Payoff conventions and strategy-class duality

  • The same controller is optimal for all four payoff criteria, every state, and every initial distribution.For an initial distribution μ, the value is μ⊤g⋆.Source: F Payoff conventions and… · p. 22

G Discounted characterizations of stationary policies

  • A stationary policy is average-optimal from all states exactly when its discounted gain limit equals the optimal gain vector.The threshold ensuring discounted optimality is existential and supplies no computable stopping rule.Source: G Discounted characterizations of… · p. 23

H Exact nature attainment and stationary saddles

The section characterizes approximate and exact nature attainment using stationary gains. Stationary gain inequalities also certify an all-state saddle against history-dependent opponents.

H Exact nature attainment and stationary saddles

  • For every δ > 0, one stationary nature selector satisfies d(q) ≤ g⋆ + δ1.The dual representation uses d(q), the optimal gain vector of the nominal MDP obtained by fixing q.Source: H Exact nature attainment and… · p. 23
  • Stationary gain inequalities hold exactly when u = g⋆ and the strategy pair is an all-state stationary saddle against history-dependent opponents for all four payoffs.The characterization expresses the full saddle property using stationary-chain gains.Source: H Exact nature attainment and… · p. 23
  • A selector worst against one optimal controller may still permit a profitable deviation through an unused action.In the example, the unused action raises the gain at s from 0 to 1.Source: H Exact nature attainment and… · p. 24

I Proof of Theorem 3: vector Bellman verification

This section verifies gain-first, bias-second vector Bellman certificates for robust policies, establishing all-state guarantees against history-dependent opponents and fixed-policy specializations. It also shows why both gain restrictions are necessary and develops proofs of finite Bellman solvability.

I Proof of Theorem 3: vector Bellman verification

  • Uniformly on compact bias sets, T(tg + h) = (t + 1)g + h + o(1), with eventual exactness when every ambiguity set is a polytope.The asymptotic identity is equivalent to the coupled gain-bias Bellman equations.Source: I Proof of Theorem 3: vector Bellman… · pp. 24–25

I.1 A compactness estimate for rows close to a gain face

  • A compactness estimate bounds bias loss by gain drift plus any η > 0; for affine functions on polytopes, η can be zero, while curved row sets may require o(N) error.The additive η cannot generally be removed for curved sets.Source: §I.1 · pp. 25–26

I.2 Verification against history-dependent opponents

  • The selected stationary controller and nature strategy form an all-state saddle against history-dependent opponents, and the certificate’s gain equals the robust value and is unique.The same gain is the limit of finite-horizon Bellman values; under the selected pair it is the recurrent-class gain, with transient-state values given by absorption-weighted class gains.Source: §I.2 · pp. 26, 29

I.3 Fixed-policy specializations of the verification theorem

  • For a fixed policy, the certificate requires both gain and gain-face bias equations, and one stationary nature selector simultaneously attains the robust infima from every initial state.The infima also hold over randomized history-dependent nature strategies.Source: §I.3 · p. 29

I.3.1 Randomized stationary policies and action-contingent nature

  • With a fixed randomized stationary policy, nature observes the realized action, and the analysis defines effective transition rows for that action-contingent response.Source: §I.3.1 · p. 30
  • The fixed-policy certificate selects nature’s minimizing row separately after each positive-probability action, yielding the Poisson identity and attainment.For randomized policies, the gain equation constrains the weighted average across actions; applying deterministic-policy reasoning to each realized action separately would be incorrect.Source: §I.3.1 · pp. 30–31

I.4 Why both gain restrictions are necessary

  • Counterexamples show that omitting either nature’s gain-minimizing face or the controller’s gain-active action restriction lets unrestricted equations accept an incorrect gain-bias pair.In the nature example the unrestricted equations accept gain (-3/4, -1, 0), while in the controller example they accept gain (3/4, 1, 0); each combines incompatible gain and bias choices.Source: §I.4 · p. 31

J Proofs of Theorems 4 and 5: finite Bellman solvability

  • The solvability proofs distinguish a prescribed recession fixed point, for which they ask whether g + h = Lgh has a finite solution, from an unspecified gain, whose tangent-operator eigenvalue can be absorbed into a scalar shift.The section specializes a classical compact-action criterion before applying it to the paper’s optimal-control argument.Source: J Proofs of Theorems 4 and 5: finite… · p. 32

J.1 The classical criterion and fixed-policy specialization

The section gives solvability criteria for finite gain-bias equations, connects them to bounded-orbit conditions, and characterizes stationary certificates and their compatible biases.

J.1 The classical criterion and fixed-policy specialization

  • A finite solution exists exactly when simultaneously gain-optimal policies exist and their canonical biases share a uniform lower bound; every solution has gain γ.Source: §J.1 · p. 32
  • For fixed-policy evaluation, solvability requires a stationary nature kernel attaining the complete worst-gain vector and a common lower bound on canonical biases.The deterministic-controller equations follow by specializing the one-player result.Source: §J.1 · p. 33

J.2 Fixed points, bounded orbits, and barriers

  • With gain unspecified, a finite gain-bias pair exists exactly when some recession fixed point yields a span-bounded orbit, equivalently an additive eigenpair.A scalar translation converts that eigenpair into a finite Bellman pair.Source: §J.2 · p. 34
  • At a prescribed gain, span-boundedness alone is insufficient because it can yield a nonzero additive eigenvalue.In the one-state example, every orbit has zero span, but a fixed point exists only when the gain equals the reward.Source: §J.2 · p. 34

J.3 Stationary tangent saddle and canonical-bias envelope

  • Finite solvability is characterized by stationary controller and nature conditions, including a uniform canonical-bias bound across zero-gain replies.The bound can be taken as the span of the common bias.Source: §J.3 · p. 34

K Geometry and structure of Bellman certificates

  • The certificate geometry uses two families of linear inequalities to characterize compatible biases and minimum span, then describes recurrent-class offsets and finite-span conditions.For listed polyhedral gain faces, the section also gives a finite linear-program formulation.Source: K Geometry and structure of Bellman… · p. 35

K.1 Common biases and the mixed-flow characterization

This section characterizes shared Bellman biases, minimum bias span, and admissible recurrent-class offsets, including infeasibility witnesses, selector compatibility, and offset repairs. It also gives geometric and finite-LP characterizations and addresses convergence and eventual policy optimality for unknown-gain anchored planning.

K.1 Common biases and the mixed-flow characterization

  • A common bias exists for fixed active selectors exactly when (0, −1) is outside the closed mixed-flow cone; finite global bias-span minima are attained over selectors.A finite Bellman bias exists if and only if some active selector pair has finite mixed-flow ratio.Source: §K.1 · p. 36

K.2 Proof of the mixed-flow theorem

  • Separation gives the attained fixed-pair minimum span 2β(π, q) when finite, and compactness attains the optimum across selectors without requiring ratio continuity.Source: §K.2 · p. 38

K.3 Sparse obstructions

  • Infeasibility has witnesses using at most r + 1 generators per combination, either an exactly balanced negative combination or a sequence whose flows approach balance.Here r is the dimension of the span of generator flows, and r + 1 ≤ n; for nonconstant g, r + 1 ≤ n − 1.Source: §K.3 · p. 38

K.4 Average optimality and common-bias compatibility

  • In the example, every stationary selector is average optimal, yet qx = p0 has separate lower and upper potentials but no common bias, while q′x = p1 has minimum span two.For q′, β(π, q′) = 1; the example shows that separate barriers need not certify the same selectors.Source: §K.4 · p. 39

K.5 Compatible recurrent-class offsets

  • For a fixed selector pair, compatible biases are Poisson solutions whose recurrent-class offsets satisfy the mixed inequalities; their offset region is closed and convex, and polytopic gain faces require only finitely many vertex-selector pairs.The canonical offset choice can fail even when a compatible offset repair exists.Source: §K.5 · pp. 39–40
  • The admissible recurrent-class offsets form a closed convex intersection of affine halfspaces, and offsets beyond the two invariant directions can repair a canonical bias.In the example, z = 0 fails the additional Bellman inequality, but z = (1, 0)^⊤ yields the exact bias h = (1, 2, 0)^⊤ for the same gain-controller pair.Source: §K.5 · p. 40

K.6 A quantitative geometric sufficient condition

  • If the balanced-mixture and flow-interior conditions hold, β(π, q) ≤ R/ρ and a feasible bias has span at most 2R/ρ.The relative-interior condition allows multiple recurrent classes and requires no lower bound on positive probabilities; the assumptions are sufficient, not necessary.Source: §K.6 · p. 41

K.7 Finite linear programs for polyhedral gain faces

  • For polyhedral gain faces, the minimum bias span is the smallest value across enumerated selector-pair LPs, with value +∞ if all are infeasible.Selector enumeration can be exponential and applies to prescribed recession-fixed gains; the unknown-gain planner instead uses robust Bellman updates.Source: §K.7 · p. 42

L Proof of unknown-gain anchored planning

  • The proof of unknown-gain anchored planning applies approximate-fixed-point Halpern estimates to asymptotically affine trajectories, then uses convergence of displacement and direction for policy extraction.A finite Bellman solution has the optimal gain and an affine defect tending to zero; the updates specialize approximately shifted Halpern iteration to the robust operator.Source: L Proof of unknown-gain anchored… · p. 43

L.1 Halpern iteration near an approximate fixed point

  • For a nonexpansive map, Halpern iteration admits distance and residual estimates around an approximate fixed point without requiring an exact fixed point.The residual can be evaluated at the current iterate; the additional iterate is used only in the proof.Source: §L.1 · p. 43

L.2 Gain, displacement, and direction estimates

  • Under finite Bellman solvability, the algorithm’s gain estimates, Bellman displacements, and directions converge to the optimal gain vector.The defect’s Cesàro average tends to zero, and the quantities used in the analysis are not required as algorithm inputs.Source: §L.2 · pp. 43–44

L.3 Gain-active action identification and average optimality

  • Every permitted greedy selector is eventually average-optimal from every initial state against history-dependent nature.This threshold is instance-dependent and need not be computable from the observable residual alone. With defect modulus ωh(t) ≤ C(1 + t)^−α, the stated rates are O(N^−α) for 0 < α < 1, O(log(N + 1)/N) for α = 1, and O(N^−1) for α > 1.Source: §L.3 · pp. 44–45

L.4 Finite solvability does not imply an inverse-budget rate

A three-state robust MDP with a finite vector Bellman solution shows that finite solvability alone guarantees no fixed algebraic convergence rate for Algorithm 1’s gain estimates.

L.4 Finite solvability does not imply an inverse-budget rate

  • A three-state, one-action robust MDP with compact convex semialgebraic row uncertainty has a finite vector Bellman solution despite the rate obstruction.The example uses rewards (0, −1, 1), with y moving deterministically to x and z absorbing; its certificate has g = (0, 0, 1) and h = (0, −1, 0).Source: §L.4 · p. 45
  • Finite Bellman solvability does not ensure an O(N^-α) gain-estimation rate for any fixed α > 0 throughout this class.For any prescribed α > 0, the construction chooses k with 1/(k −1) < α, even when the instance-dependent constant is allowed.Source: §L.4 · pp. 45–46
  • The affine-defect argument gives an O(N^-1/(k−1)) upper bound, with finitely many early steps contributing only a bounded amount.The defect vanishes at y and z; at x, the sufficiently-large-t minimizer is u = (kt)^-1/(k−1).Source: §L.4 · p. 45
  • Small positive leakage rows create long negative transients even though the gain-minimizing limiting row stays at x.This obstruction concerns Algorithm 1’s finite-horizon gain estimator, not every possible planning algorithm.Source: §L.4 · p. 46

M Supporting results and solvability obstructions

M.1 Structural multichain existence regimes

The section characterizes structural regimes for finite vector gain-bias solvability, giving sufficient conditions and examples of obstructions despite well-defined statewise average values. It also examines representation invariance and gain stability, and shows that gain-only recession equations do not identify reward-dependent gains.

M.1 Structural multichain existence regimes

  • Polytope ambiguity guarantees a finite gain-bias pair and an invariant half-line T(tg + h) = (t + 1)g + h for all sufficiently large t, without requiring a unique recurrent class.It also yields bounded discounted centering, ∥Vε − g/ε∥∞ ≤ 2∥h∥∞ for sufficiently small ε.Source: §M.1 · p. 47
  • A uniform support gap—each transition probability is zero or at least δ—ensures finite gain-bias solvability and bounded centering, including with multiple recurrent classes.The result extends to fixed stationary policies; for a randomized policy, the bound may depend on its positive action probabilities. Compactness, convexity, and semialgebraicity alone do not suffice.Source: §M.1 · pp. 47, 49
  • Continuity of P ↦ P∞ on each compact deterministic-policy kernel family also suffices for bounded discounted centering and a finite vector Bellman solution.The support gap is one way to obtain this continuity condition.Source: §M.1 · p. 48

M.1.1 Divergence balls and the support-loss boundary

  • Polytope rows, support-preserving forward or support-restricted reverse KL balls, and total-variation balls satisfy sufficient conditions for finite Bellman solvability and bounded centering.For forward KL balls, the support-preservation condition is a strict radius bound; reverse KL rows require the nominal support restriction, automatic for full-support nominal rows.Source: §M.1.1 · p. 49
  • At the first forward-KL support-loss boundary, a three-state model has robust gain g⋆ = 0 but no finite Bellman solution; the strict radius condition is sufficient, not necessary.At equality, feasible rows can lose a coordinate, and rows approaching that boundary can have arbitrarily small positive mass there.Source: §M.1.1 · p. 50

M.2 Two distinct obstructions to finite Bellman solvability

  • Compact convex semialgebraic ambiguity can prevent stationary nature from attaining the robust gain vector (−1, −1, 0), leaving no finite Bellman pair [20].In the example, the gain at state s is approached by stationary rows but is not attained; the gain-face bias equation is contradictory.Source: §M.2 · pp. 50–51
  • A different compact convex semialgebraic example has stationary kernels that attain the robust gain, but their canonical biases have no common lower bound, so no finite Bellman pair exists.The robust gain is zero for every stationary kernel in this example.Source: §M.2 · p. 51
  • In the second example, kernels attain gain zero but canonical bias coordinates diverge to −∞ as k ↓ 0, and no finite bias exists at gain zero.The canonical bias along the generating curve is w(k) = (−1/k, −1 −1/k, 0) for k > 0.Source: §M.2 · p. 51
  • The examples isolate failures of finite Bellman solvability: one violates simultaneous worst-gain attainment, while the other violates the one-sided canonical-bias envelope despite well-defined statewise average values.Source: §M.2 · p. 51

M.3 Representation invariance and elementary stability

  • Convexifying each ambiguity set preserves discounted, finite-horizon, and robust average values, as well as the set of average-optimal stationary controllers.Source: §M.3 · p. 52
  • The optimal gain is δ-Lipschitz in rewards, monotone, shift-equivariant, and positively homogeneous; enlarging ambiguity sets weakly decreases it.Here δ is the supremum-norm distance between reward arrays.Source: §M.3 · p. 52
  • The optimal gain satisfies g⋆ = bTg⋆, but gain-only recession equations cannot determine average reward because constant vectors satisfy them regardless of rewards.In a one-state model, the average gain is the reward r.Source: §M.3 · p. 52
Loading 2609.28792v1…