PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation

Kihyun Yu, Seoungbin Bae, Dabeen Lee

arXiv:2609.39093v1cs.LG

TL;DR

For weakly communicating average-reward CMDPs, it remained open whether a computationally efficient algorithm could achieve rate-optimal regret and cumulative constraint violation. The paper introduces state augmentation with a Huber-potential reward and reports rate-optimal guarantees in the tabular setting.

  • Problem

    Whether computationally efficient algorithms can achieve rate-optimal regret and cumulative constraint violation for weakly communicating average-reward CMDPs remained open, while constraint-aware planning complicates existing analyses.

    Source: §1 · pp. 2–3, §3 · p. 5

  • Method

    SA-CVI-UCB tracks cumulative constraint violation in an augmented state and uses a fixed Huber-potential reshaped reward with finite-horizon approximation, optimistic value iteration, and clipping.

    Source: §1 · p. 3, §3.3 · p. 9, §6 · p. 13

  • Results

    SA-CVI-UCB achieves rate-optimal ~O(T^1/2) regret and constraint violation in the tabular setting.

    Source: §6 · p. 12

  • Takeaways & Limitations

    The fixed reward and known deterministic safety-state dynamics avoid additional reward variation and require estimating only the original transition kernel.

    Source: §3.3 · p. 9, §6 · p. 13

    For x≥W, the Huber potential grows linearly, so the same argument no longer yields the desired bound.

    Source: §4 · p. 11

Abstract

from arXiv · show

We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Existing high-probability guarantees for this setting either require computationally inefficient algorithms or have suboptimal dependence on the number of interactions $T$. We propose, to the best of our knowledge, the first computationally efficient algorithm that achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and cumulative constraint violation with high probability in the tabular setting. The $\sqrt{T}$ dependence is optimal up to logarithmic factors. Our approach incorporates cumulative constraint violation into the state and defines a reshaped reward through differences of a Huber potential. The added state determines the penalty on further violations while the reward function remains fixed on the augmented state space. Since the added state has known deterministic dynamics, only the original transition kernel needs to be estimated. The bounded slope of the Huber potential keeps the per-step reward bounded, and the potential differences telescope to relate the reshaped return to the original cumulative reward and the terminal potential. These properties allow us to apply finite-horizon approximation and optimistic value iteration with clipping, as used in unconstrained average-reward MDPs, without worsening the regret rate in $T$.

1 Introduction

The introduction frames learning weakly communicating average-reward CMDPs as an open challenge: efficient algorithms with strong regret and constraint-violation guarantees are lacking. It proposes SA-CVI-UCB, using state augmentation and a Huber-based reshaped reward to obtain rate-optimal guarantees in the tabular setting.

1 Introduction

  • Average-reward CMDPs describe continuing tasks without resets, evaluating reward and constraint costs through their long-run averages.The introduction contrasts this setting with finite-horizon and discounted CMDPs.Source: §1 · p. 2
  • Weakly communicating CMDPs pose additional learning challenges because constraints can make reward-greedy actions infeasible and dual-multiplier updates vary the planning reward.The introduction notes that existing results in this setting either require computationally inefficient algorithms or have suboptimal dependence on T.Source: §1 · p. 2
  • SA-CVI-UCB provides computationally efficient, high-probability regret and constraint-violation guarantees for weakly communicating tabular average-reward CMDPs.The introduction presents this as the first such algorithm.Source: §1 · p. 3
  • The regret and constraint-violation dependence on T is optimal up to logarithmic factors when both are controlled simultaneously.A direct backward-value-iteration implementation uses O(S2AT 5/2) arithmetic operations over T interactions.Source: §1 · p. 3
  • The algorithm combines a state tracking cumulative constraint violation with a reshaped reward based on differences of a Huber potential.The added state sets the penalty on further violations while the reward remains fixed on the augmented state space.Source: §1 · p. 3

2 Problem Setting

The problem setting is a finite-state, finite-action average-reward CMDP with known deterministic reward and constraint functions and unknown transitions. Learning is evaluated by regret and cumulative constraint violation under weak communication, a stationary-optimum assumption, and strict feasibility.

2 Problem Setting

  • The CMDP has finite state and action spaces, a transition kernel, an initial state, and reward and constraint functions.The reward lies in [0, 1] and the constraint function in [-1, 1].Source: §2 · p. 3
  • The reward and constraint functions are known and deterministic, whereas the transition kernel is unknown.Source: §2 · p. 4
  • The learner interacts for T steps and is evaluated by regret and cumulative constraint violation; the Slater condition assumes a stationary policy with constraint gain at least γ > 0.The Slater constant γ is known, but the Slater policy is unknown.Source: §2 · p. 4
  • Weak communication permits communicating states and states transient under every stationary policy, and is weaker than ergodicity or the unichain assumption.The setting additionally assumes an optimal stationary policy whose reward and constraint gains are independent of the initial state.Source: §2 · p. 4

3 Algorithm

SA-CVI-UCB turns a weakly communicating average-reward CMDP into an augmented MDP with a Huber-potential reshaped reward. The paper reports rate-optimal guarantees in T with polynomial running time.

3 Algorithm

  • The method augments the state to track cumulative constraint information and uses a Huber-potential difference as its reshaped reward.Unlike primal-dual reward changes, the reward stays fixed on the augmented state space.Source: §3 · p. 5

3.1 State-Augmented MDP

  • The Huber potential is globally Lipschitz, keeping the potential-difference reward uniformly bounded while retaining the telescoping structure used to relate augmented and original regret.The telescoping relation also includes the terminal potential, which helps control constraint violation.Source: §3.1 · pp. 6–7

3.2 Description of Algorithm

  • SA-CVI-UCB uses finite-horizon episodes, backward optimistic value iteration, and a transition estimate based on visits to each original (s, a) pair.The safety-state transition is deterministic, so the bonus accounts only for uncertainty in the original transition kernel.Source: §3.2 · pp. 7–8
  • For each fixed safety state, clipping the value estimate across original states preserves optimism while using the tighter span parameter C rather than the naive horizon span H.This clipping step is identified as crucial to the desired regret bound.Source: §3.2 · p. 8

3.3 Main Result

  • SA-CVI-UCB is reported as the first computationally efficient algorithm with rate-optimal guarantees in T for this setting, running in O(S^2AT^(5/2)) time.The guarantees cover regret and constraint violation, with problem-dependent factors involving S, A, γ, and relevant bias spans.Source: §3.3 · p. 9
  • The augmentation avoids variation from a changing dual multiplier, and its known safety-state dynamics leave only the original transition kernel to estimate.These properties are presented as making the formulation suitable for rate-optimal guarantees in the tabular setting.Source: §3.3 · p. 9

4 Analysis

The analysis first bounds regret in the augmented MDP, transfers that bound to the original CMDP using telescoping, and then separates regret from constraint violation. A sharper regret lower bound and a Huber-potential inequality are needed to control violation.

4 Analysis

  • The proof proceeds by bounding augmented-MDP regret, transferring the bound to original regret plus the terminal potential, and then separately bounding regret and violation.The transfer uses the reshaped reward's telescoping structure.Source: §4 · pp. 10–11
  • Clipping preserves optimism because the comparator value function has bounded span, allowing the augmented-MDP regret analysis to use the tighter span control.The analysis uses the optimism lemma after clipping.Source: §4 · pp. 10–11
  • The naive lower bound Regret(T) ≥ −T is insufficient for violation control with the Huber potential, whose growth becomes linear beyond W.The analysis instead invokes a sharper lower bound from strong duality and the Huber-potential inequality to bound the terminal safety state.Source: §4 · pp. 11–12

5 Numerical Experiments

The experiments compare Algorithm 1 with four baselines on a modified tabular CMDP and test sensitivity to bonus scale. Algorithm 1 has sublinear regret and constraint violation across tested scales c ≤ 1.

5 Numerical Experiments

  • Algorithm 1 achieves sublinear regret and constraint violation, with lower regret and violation than PD-LSCVI-UCB; two baselines incur linear constraint violation or regret.At T = 32,000, Algorithm 2 of Ghosh et al. (2023) has linearly growing violation, while Algorithm 3 of Chen et al. (2022) has negative regret alongside linearly growing violation.Source: §5 · p. 12
  • In sensitivity experiments, Algorithm 1 achieves sublinear regret and constraint violation for every bonus scale c ≤ 1, whereas every baseline incurs linear regret or constraint violation for some c.Source: §5 · p. 12

6 Conclusion

SA-CVI-UCB achieves rate-optimal regret and constraint-violation guarantees for tabular, weakly communicating average-reward CMDPs. It combines cumulative-violation state augmentation with a Huber-based reshaped reward, while extending the result to linear CMDPs remains open.

6 Conclusion

  • The computationally efficient SA-CVI-UCB algorithm achieves rate-optimal eO(T^1/2) regret and constraint violation in tabular weakly communicating CMDPs.The guarantees are for infinite-horizon average-reward CMDPs.Source: §6 · p. 12
  • The method tracks cumulative constraint violation in the state and reshapes reward using a Huber potential.The reshaped reward stays bounded and avoids the extra reward variation caused by changing dual multipliers; the algorithm uses finite-horizon approximation, optimistic value iteration, and value-function clipping.Source: §6 · p. 13
  • Whether computational efficiency and rate-optimal guarantees extend to weakly communicating average-reward linear CMDPs remains open.Source: §6 · p. 13

A Related Work

Prior work studies average-reward CMDPs, budget and cost augmentation, and optimistic methods for unconstrained average-reward MDPs. This work combines these lines to obtain efficient, high-probability guarantees for weakly communicating tabular CMDPs.

Average-reward CMDPs

  • Prior average-reward CMDP results include model-based guarantees, model-free expected guarantees, and efficient weakly communicating bounds that remain suboptimal in T.The cited efficient bounds include eO(T^2/3) and eO(T^3/4); another eO(T^1/2) result is computationally inefficient.Source: A Related Work · p. 19
  • The paper reports computationally efficient eO(T^1/2) regret and constraint-violation guarantees with high probability for weakly communicating tabular CMDPs.The comparison table concerns unknown transitions after T steps; its weak-communication results assume an optimal stationary policy with state-independent gains.Source: A Related Work · p. 19, Table 1 · p. 20

Unconstrained average-reward MDPs

  • Optimistic planning, bias-span control, discounted-reward approximation, and value clipping have established tools for unconstrained average-reward MDPs.The paper adapts optimistic value iteration and clipping to an augmented MDP, where cumulative constraint violation is part of the state.Source: A Related Work · p. 19

CMDPs via State Augmentation

  • Prior state-augmentation work covers multiplier-conditioned policies and budget or cumulative-cost variables for different constraint settings and objectives.Examples include discounted expected-cost and episodic knapsack constraints, as well as anytime and probabilistic state-avoidance constraints.Source: A Related Work · pp. 19, 21

Risk Criteria via State Augmentation; Reward Penalties on Augmented States

  • Other augmentation work addresses nonlinear risk criteria, while reward-penalty methods target discounted or finite-horizon constraints rather than this continuing setting.Here, a bounded-derivative Huber potential supports finite-horizon approximation and clipped optimistic value iteration, yielding efficient high-probability eO(T^1/2) guarantees.Source: A Related Work · pp. 21–22

B Strong Duality

This appendix uses strong duality for feasible weakly communicating average-reward CMDPs to support the analysis. Under Slater’s condition, it bounds the optimal dual variable in terms of the feasibility margin.

B Strong Duality

  • The strong-duality lemmas apply to feasible weakly communicating average-reward CMDPs with finite state and action spaces and any initial state.Source: B Strong Duality · p. 22
  • Under Slater’s condition with margin γ > 0, the optimal dual variable satisfies λ* ≤ 1/γ.Source: B Strong Duality · p. 22
  • With a bounded optimal dual variable, the analysis considers the unconstrained average-reward MDP with composite reward r + λ*g and invokes its Bellman optimality condition.Source: B Strong Duality · p. 22
  • The appendix also states that, under Slater’s condition, regret can be lower-bounded in terms of cumulative violation.The supplied passage does not give the bound’s quantitative form.Source: B Strong Duality · pp. 22–23

C.1 Proof of Lemma 1

The proof uses Huber-potential inequalities to control the reward reshaping, then applies them in the augmented-MDP analysis. The supplied proof passages also describe how the cumulative-cost state updates and enters the reshaped reward.

C.1 Proof of Lemma 1

  • The potential increment is bounded below by its derivative term and above by that term plus a quadratic remainder.The stated remainder is Λ²x²/(2W).Source: §C.1 · pp. 23–24
  • For λ in [0, Λ), the potential minus λx is bounded below by (Λ − λ)[x]+ − ΛW/2.Source: §C.1 · p. 23
  • The Huber potential’s derivative is piecewise 0, Λ/W times x, or Λ across the nonpositive, transition, and above-W regions.Source: §C.1 · p. 23

C.2 Proof of Lemma 3

  • The augmented cost state updates deterministically as z′ = ΠZ(z − g(s,a)), and the reshaped reward adds the difference between successive potential values to the original reward.This construction is used in the proof’s augmented-MDP analysis.Source: §C.2 · p. 24
  • The proof invokes the potential’s Lipschitz property to bound changes in the reshaped reward.Source: §C.2 · p. 25

C.3 Deferred proofs for Step 1 of Section 4

These deferred proofs support the three analysis steps by establishing transition-estimation and value-function bounds, then applying them to the reshaped reward and the final bound. The proofs also use clipping and bounds on the augmented constraint state.

C.3 Deferred proofs for Step 1 of Section 4

  • The transition-estimation proof uses concentration and a union bound over time, states, actions, and next states, then substitutes visit counts into the empirical transition estimate.The following value-function argument uses induction over the finite-horizon steps and the algorithm's clipping operation.Source: §C.3 · pp. 30–32

C.4 Deferred proofs for Step 2 of Section 4

  • The Step 2 proof starts from the reshaped reward defined by differences of the potential and uses the preceding bound to establish its formal inequality.The proof notes that the initial potential is zero.Source: §C.4 · pp. 36–37

C.5 Deferred proofs for Step 3 of Section 4

  • The Step 3 proof applies the preceding bounds and controls the terminal potential using inequalities involving Λ, λ*, and γ.The proof uses Λ = 2/γ and λ* ≤ 1/γ.Source: §C.5 · pp. 37–38

C.6 Proof of Theorem 2

The proof of Theorem 2 combines the preceding lemmas to bound regret and cumulative constraint violation. An auxiliary inequality controls differences between probability-weighted values using their span.

C.6 Proof of Theorem 2

  • With probability at least 1−3δ, the proof combines the preceding lemmas to bound regret and constraint violation.The union bound ensures Lemmas 7, 12, and 14 hold together; the proof then applies Lemmas 17 and 18 to the respective bounds.Source: §C.6 · p. 39

D Auxiliary Lemmas

  • For probability vectors p and q, the auxiliary lemma bounds |(p−q)^T v| by sp(v)||p−q||_1.Here the span is the maximum difference between entries of v.Source: D Auxiliary Lemmas · pp. 39–40

E Experimental Details

The experiments test bonus-scale sensitivity in a constructed tabular CMDP and compare Algorithm 1 with three baselines. Algorithm 1 retains sublinear regret and constraint violation for bonus scales c ≤ 1.

Environment

  • The test CMDP uses action-dependent constraint values score(a) and rewards that favor lowering the constraint early and raising it later.The setup chooses Henv = 6, m = 2, b = 0.7, and s1 = 0; the two terminal states return to state 0.Source: E Experimental Details · p. 40

Sensitivity to the bonus term

  • For every c ≤ 1, Algorithm 1 achieves sublinear regret and constraint violation; its violation is no greater than PD-LSCVI-UCB's, and its regret is smaller or comparable for every tested c.Figure 2 plots regret and constraint violation across c ∈ {0.1, 0.3, 1, 3, 10}, averaging three trials with 95% confidence intervals.Source: E Experimental Details · p. 41, Figure 2 · p. 41

Metrics and hyperparameters

  • The sensitivity experiment scales each algorithm's bonus by c, while the baselines use their stated parameter choices and Algorithm 1 uses H = W = ⌊√T⌋.For Algorithm 1, the chosen constraint values are integer multiples of the grid gap, so projection has no rounding error.Source: E Experimental Details · pp. 40–41

F Discussions and Future Work

The discussion identifies obstacles to extending the algorithm beyond the tabular setting and explains why two primal-dual routes do not directly yield rate-optimal guarantees. It also outlines a possible linear-CMDP extension and discloses the use of generative AI tools.

F Discussions and Future Work

  • The proposed linear extension otherwise replaces empirical transitions with least-squares value iteration and uses the elliptical potential lemma to bound bonuses.The discussion says most analysis does not rely on tabular structure, while value-function clipping can be applied for each debt value.Source: F Discussions and Future Work · p. 42
  • The linear-CMDP extension has a larger covering number because each debt value depends on regression weights for reachable debt values, yielding Õ(T^2/3) regret and violation rather than Õ(√T).Balancing the resulting bonus against projection error gives Δ ≍ T^-1/3; the bound matches Yu et al. (2026), and resolving the covering-number growth is left for future work.Source: F Discussions and Future Work · p. 42
  • Yu et al.’s finite-horizon primal-dual method has only Õ(T^2/3) guarantees because its standard dual-regret term cannot be bounded by Õ(√T) when T = KH.The episode constraint sum can be as large as H, producing a term λ²/(2η) + ηKH²/2.Source: F Discussions and Future Work · p. 42
  • A primal-dual multiplier changes the composite reward across episodes, adding value-function variation that obstructs direct use of deviation control for unconstrained average-reward MDPs.The discussion identifies the additional term as ∥r_{k+1} − r_k∥∞, induced by changing λ_k.Source: F Discussions and Future Work · pp. 42–43

Use of Generative-AI Tools

  • The authors report using generative AI for state-augmentation ideas, related-work discovery, and experiment implementation, while retaining responsibility for the final work.They state that reward design, manuscript drafting, theoretical development, and proofs were carried out by the authors.Source: Use of Generative-AI Tools · p. 43
Loading 2609.39093v1…