Finite-Time Guarantees for Constrained Reinforcement Learning under Partial Observability

1 Introduction

• Theoretical guarantees for learning in CPOMDPs remain limited, particularly for unknown models learned solely through environment interaction.Prior methods do not provide finite-time guarantees for both reward optimality and constraint satisfaction in this setting.Source: §1 · p. 1
• Because optimal policies may depend on the full observation-action history, partial observability makes planning and learning challenging.Planning can be computationally intractable even with a known model, while learning near-optimal policies can require exponentially many samples in the worst case.Source: §1 · pp. 1–2
• The paper represents finite history windows as states of a superstate CMDP, extending finite-window methods from unconstrained reward maximization to CPOMDPs.Prior finite-window results described here address unconstrained reward maximization.Source: §1 · p. 2
• Under uniform filter stability, the analysis bounds how history truncation affects policy values and constrained optima, including both optimality and feasibility.The bounds quantify the effects of truncation in the superstate CMDP relative to the original CPOMDP.Source: §1 · p. 2
• The primal–dual algorithm has finite-time bounds on average optimality gap and average constraint violation in the original CPOMDP, accounting for trajectory-estimation error.Experiments on a partially observable Gridworld observe convergence across different history lengths, in accordance with the analysis.Source: §1 · p. 2

2 CPOMDP

• A CPOMDP models decision-making with partial observations of an underlying state, where the objective is to maximize expected cumulative reward subject to constraints.The paper considers an infinite-horizon discounted CPOMDP.Source: §2 · pp. 2–3
• At each timestep, the agent chooses an action and receives reward and cost, after which the latent state transitions and a new observation arrives.The initial state is drawn from the initial-state distribution, and the initial observation from the observation kernel.Source: §2 · p. 3
• Because latent states are hidden, policies select actions based on observation-action histories, and optimal policies may depend on the full history.The history length grows without bound over time.Source: §2 · p. 3

3 Finite-window Approximation

• The finite-window approximation replaces the CPOMDP with a CMDP whose states are finite windows of recent observations and actions.The approximation error depends on the window length.Source: §3 · p. 3

3.1 Superstate CMDP

• A superstate retains the recent history suffix and uses a finite-history belief to define transitions, rewards, and costs.The model uses a lower constraint threshold as a design choice that can help keep its feasible policies approximately feasible in the original CPOMDP.Source: §3.1 · p. 4

3.2 Approximating a CPOMDP with a Superstate CMDP

• Uniform filter stability controls the loss of current-state information from truncating history, supporting two-way transfer bounds for reward and cost values.The transfer maps history-dependent policies to stationary superstate policies with approximately matching values.Source: §3.2 · p. 5
• The constrained optimal reward gap between the superstate CMDP and original CPOMDP converges to zero as the window grows when d_g = d_o − δ(l) and ξ_o > 2δ(l).These conditions ensure the superstate problem remains strictly feasible.Source: §3.2 · p. 6
• Choosing d_g trades off optimality loss against feasibility: increasing it can reduce the optimality-loss bound but permit constraint violation in the original CPOMDP.For d_g = d_o − δ(l), policies feasible in the superstate CMDP are feasible in the original CPOMDP.Source: §3.2 · p. 6

4.1 Lagrangian Formulation

• The policy update applies exponential weights to maximize the modified reward r_g − λ_k c_g for a fixed multiplier.The modified reward is the reward less the multiplier-weighted cost.Source: §4.1 · p. 7
• Projected gradient descent raises the multiplier when the policy violates the cost threshold and lowers it otherwise.The Lagrangian formulation has the same optimal value as the constrained problem, with an optimal multiplier restricted to [0, λ_max].Source: §4.1 · pp. 6–7

4.2 Estimation Oracle

• Estimation Oracle B estimates policy values from CPOMDP trajectories for use in both updates.It may be instantiated with model-based or model-free TD policy evaluation; under filter stability, the model-mismatch component decreases as the window length increases.Source: §4.2 · pp. 7–8
• The tabular policy update requires time and memory exponential in the history-window length, trading computational cost for approximation accuracy.Source: §4.2 · p. 8

5 Theoretical Guarantees

• Theorem 1 specifies that, given Estimation Oracle B and Assumptions 1 and 2, Algorithm 1 runs for K iterations with constraint threshold d_g > d_o − ξ_o + δ(l).Source: §5 · p. 8
• Approximation error δ(l) decays geometrically with window length, while the bounds scale linearly with estimation error and finite-iteration optimization error decays as O(√(log |A|/K)).Source: §5 · pp. 8–9
• Lowering d_g reduces the constraint-violation bound term but loosens the optimality-gap bound through a larger opposing term and a smaller Slater margin.Source: §5 · p. 9

5.1 Proof Sketch

• The proof decomposes the average gaps into model-approximation terms bounded by δ(l) and superstate-MDP performance terms controlled by a primal–dual analysis.The average Lagrangian performance bound uses exponential-weights regret and direct expectation bounds on estimation errors.Source: §5.1 · p. 9

• The 7 × 7 Gridworld uses stochastic transitions and observations, with reward at the goal and cost in unsafe states.The agent seeks the goal while limiting expected discounted visits to unsafe cells despite not observing its position directly.Source: §6 · p. 10
• An exact superstate-CMDP policy-evaluation oracle isolates the effects of history length and iteration count from estimation error.Source: §6 · p. 10
• As K increases, average optimality gap and average constraint violation approach a neighborhood of zero, and increasing l reduces that neighborhood through lower approximation error.Figure 3 reports means as solid curves and evaluation uncertainty as shaded regions across history lengths.Source: §6 · p. 11, Figure 3 · p. 11

• Under filter stability, approximation errors in reward values and the feasible-policy set decay geometrically with window length.The primal–dual algorithm gives non-asymptotic guarantees on average reward suboptimality and constraint violation in the original CPOMDP.Source: §7 · p. 11
• The analysis is limited to tabular superstate CMDPs and the experiments to Gridworld.Continuous spaces, realistic benchmarks, and a weaker uniform filter-stability assumption remain future work.Source: §7 · p. 11

A Superstate CMDP posterior belief

• A superstate g is a recent observation-action window associated with a finite-history belief obtained by marginalizing compatible latent-state trajectories from the prior.This belief is generally based on less history than the exact posterior.Source: A Superstate CMDP posterior belief · p. 14

B History-state CMDP

• The history-state CMDP uses full observation-action histories as states and extends the POMDP construction to account for costs.Its transitions append the next action and observation; rewards and costs are conditional expectations over latent states.Source: B History-state CMDP · p. 14
• Under the same history-dependent policy, the history-state CMDP and original CPOMDP induce identical history distributions and expected reward and cost values.The initial history distribution reproduces the original initial observation distribution.Source: B History-state CMDP · pp. 14–15
• When the constrained problem is feasible, an optimal policy exists in the discounted history-state CMDP.The model has a countable history state space, finite actions, and rewards and costs in [0, 1].Source: B History-state CMDP · p. 15

C Full Theorem Statement

• Theorem 1 gives bounds on the average optimality gap and average constraint violation after K iterations, under Assumptions 1 and 2 and the specified oracle conditions.The full statement also imposes conditions on dg and λmax.Source: C Full Theorem Statement · p. 15

D.1 Proof of Proposition 1

• Under filter stability, the full-history and finite-window beliefs differ in total variation by at most (1 − κ)^l.This controls the approximation error in reward and cost values when transferring policies between models.Source: §D.1 · p. 16
• A history-dependent policy’s behavior in the auxiliary model can be reproduced in reward and cost values by a stationary policy over superstates using matching discounted occupancy measures.The proof constructs the stationary policy from the state-action occupancy measure and uses the Bellman flow constraint.Source: §D.1 · pp. 17–18

D.2 Proof of Lemma 2

• For a finite superstate CMDP, discounted occupancy measures form a polytope, making the constrained optimization equivalent to a linear program with an attained dual optimum.The argument uses feasibility and boundedness of that linear program.Source: §D.2 · pp. 18–19

D.3 Proof of Proposition 2

• The mapped version of an optimal CPOMDP policy may violate the superstate constraint, but is feasible for a relaxed threshold increased by the cost approximation error.Slater-based constraint sensitivity bounds the resulting reward difference in terms of the relaxation and ξg.Source: §D.3 · pp. 19–20

D.4 Proof of Lemma 3

• The average Lagrangian performance bound controls iterate reward and constraint behavior using oracle accuracy and an exponential-weights regret bound.The proof compares policy evaluation across the original and superstate models and bounds the gaps from approximation and optimization.Source: §D.4 · pp. 20–21

D.6 Average constraint violation

• The dual update converts a bound on the average constraint residual into a bound on positive-part average constraint violation.The argument selects λmax for a positive residual and zero otherwise.Source: §D.6 · pp. 22–23

E.1 Projected Linear TD Learning Estimation Oracle

• Projected linear TD critics estimate reward and cost action values from CPOMDP trajectories using a shared trajectory, so estimating both does not double interactions.Their error includes function-approximation, sampling-mismatch, initialization, and finite-sample TD terms.Source: §E.1 · pp. 24–25
• The sample-complexity guarantee is conditional on uniform mixing and coverage across Algorithm 1’s policy sequence, which the exponential-weights update does not itself ensure.Establishing sufficient conditions for these properties is left for future work.Source: §E.1 · p. 26

E.2 Sample Complexity Bound for Fixed Window Length

• The fixed-window reward and constraint floors combine CPOMDP-to-superstate approximation, linear approximation, and TD sampling-mismatch errors.Finite-sample TD and finite-iteration optimization errors remain as separate terms; the bound certifies target accuracy only above the floor.Source: §E.2 · pp. 26–27
• For fixed history length and admissible threshold, increasing samples cannot remove the fixed-window floor, so the stated accuracy guarantee requires ε > Fl.The remaining TD and optimization terms are controlled by choices of K and τ.Source: §E.2 · p. 27

F.1 Experimental Setup

• The Gridworld experiments test l ∈ {0, 1, 2, 3, 4} and K ∈ {100, 500, 1000, 5000, 10000}, using do = dg = 0.692 to ensure strict feasibility for each tested window.Performance is evaluated in the original CPOMDP; evaluation uses four seeds and 20,000 episodes per configuration.Source: §F.1 · pp. 27–28
• Figure 4 presents Algorithm 1’s performance in the finite-history superstate model for different values of K and l.Source: Figure 4 · p. 29

Performance in the Superstate CMDP

• Constraint violation decreases with K for all tested history lengths, while the signed optimality gap can become negative when finite-K mixtures remain infeasible.The curves are qualitatively compatible with O(K^-1/2) optimization terms and should be interpreted jointly.Source: §F.2 · p. 29

Effect of Implementing an Estimation Oracle

• The TD(0) oracle generally adds bias to both reward and constraint performance compared with exact policy evaluation.The experiment tests approximate policy evaluation, not an end-to-end TD sample-complexity bound; retained TD estimates cause errors to vary with K.Source: §F.2 · p. 29, Figure 5 · p. 30

Effect of Superstate Constraint Tightening

• Stronger superstate constraint tightening reduces cost in the original CPOMDP at the price of lower reward for history length l = 3.The experiment varies the superstate constraint threshold, with smaller values imposing more conservative constraints.Source: §F.2 · pp. 29–30, Figure 6 · p. 30

Fully Observable and Unconstrained Partially Observable Baselines

• The constrained SARSOP reference achieves reward 3.426 and cost 0.684, while the exact fully observable constrained optimum achieves reward 4.162 and cost 0.692.Removing the constraint under partial observability raises SARSOP reward to 3.898 but also raises cost to 1.302, above the threshold do ≃0.692.Source: §F.2 · p. 30, Table 1 · p. 30, Figure 7 · p. 31

Unconstrained and Fully Observable Learning Baselines

• At K = 10^4, the constrained variant has lower constraint violation than the unconstrained variant for every history length.The finite-iteration average policies are learned in the superstate model and evaluated in the original CPOMDP, so reward values need not follow the ordering of exact constrained and unconstrained optima.Source: §F.2 · pp. 30–31, Table 2 · p. 31
• The partial-versus-full-observability performance gap decreases as history length l increases.Figure 8 compares Algorithm 1 under partial and full observability.Source: §F.2 · p. 31, Figure 8 · p. 32

Matching the Theoretical stepsizes

• At K = 1000, practical calibration uses η1 = 0.0526 and η2 = 0.0034, while theorem constants yield η1 from 1.74 · 10^-5 to 1.38 · 10^-4 and η2 from 0.110 to 0.894.The theorem calibration yields stronger constraint reduction but considerably slower reward improvement, attributed to smaller primal and larger dual updates.Source: §F.2 · p. 31, Figure 9 · p. 32