Exploration-Exploitation in Constrained MDPs

Yonathan Efroni; Shie Mannor; Matteo Pirotta

Source-linked AI summary

Exploration-Exploitation in Constrained MDPs

Yonathan Efroni, Shie Mannor, Matteo Pirotta

arXiv:2003.02189v1Mar 4, 2020cs.LGstat.ML

TL;DR

The paper asks how to explore an unknown CMDP while optimizing its main utility and limiting constraint violations. It analyzes optimistic LP-based planning and incremental optimistic primal-dual updates. Both achieve sublinear regret for performance and violations, but LP-based methods provide stronger guarantees than dual approaches.

Problem
Learning in an unknown CMDP requires exploration for information while limiting violations of long-term constraints that cannot yet be evaluated exactly.
Method
The paper analyzes optimistic LP-based CMDP planning and incremental optimistic updates of primal and dual variables for saddle-point formulations.
Results
Both algorithmic approaches obtain sublinear regret for the main utility and constraint violations, while LP-based methods have stronger theoretical guarantees than dual approaches.
Takeaways & Limitations
Algorithm designers face a computational-performance trade-off: practically amenable dual and primal-dual methods may sacrifice the stronger Reg+ guarantees of UCRL-like methods.
Takeaways & Limitations
Lagrangian analyses bound signed cumulative error rather than the sum of positive errors, allowing cancellation; obtaining stronger guarantees remains open.

Abstract

from arXiv · show

In many sequential decision-making problems, the goal is to optimize a utility function while satisfying a set of constraints on different utilities. This learning problem is formalized through Constrained Markov Decision Processes (CMDPs). In this paper, we investigate the exploration-exploitation dilemma in CMDPs. While learning in an unknown CMDP, an agent should trade-off exploration to discover new information about the MDP, and exploitation of the current knowledge to maximize the reward while satisfying the constraints. While the agent will eventually learn a good or optimal policy, we do not want the agent to violate the constraints too often during the learning process. In this work, we analyze two approaches for learning in CMDPs. The first approach leverages the linear formulation of CMDP to perform optimistic planning at each episode. The second approach leverages the dual formulation (or saddle-point formulation) of CMDP to perform incremental, optimistic updates of the primal and dual variables. We show that both achieves sublinear regret w.r.t.\ the main utility while having a sublinear regret on the constraint violations. That being said, we highlight a crucial difference between the two approaches; the linear programming approach results in stronger guarantees than in the dual formulation based approach.

1 Introduction

The paper studies exploration in unknown CMDPs, where agents must learn while limiting long-term constraint violations. It analyzes optimistic LP-based and incremental primal-dual approaches, finding guarantees for both performance and violations but stronger theoretical guarantees for LP-based methods.

Motivation: Unknown CMDP learning requires balancing information-gathering exploration with reward maximization while limiting constraint violations.The agent cannot exactly evaluate long-term constraints before learning the transition, reward, and constraint functions.
Evaluation: The paper evaluates regret for both the main objective and cumulative constraint violations.These measures capture convergence toward an optimal policy and the cost of violating constraints during learning.
LP-based approaches: OptCMDP performs episode-wise optimistic planning over plausible CMDPs using an extended occupancy-measure linear program.Its extended LP always has a feasible solution.
LP-based approaches: OptCMDP-bonus combines transition and cost uncertainty into an exploration bonus, reducing planning to one CMDP and an LP with O(SAH) constraints and variables.This is a factor O(S) smaller than OptCMDP’s LP.
Lagrangian approaches: OptDual-CMDP and OptPrimalDual-CMDP use optimistic saddle-point updates of dual or primal-dual variables, including mirror descent and projected subgradient descent.The incremental approach uses exploration bonuses for both the main cost and constraint costs and computes Q-functions by dynamic programming.
Results and comparison: All proposed algorithms have upper bounds for main-objective regret and cumulative constraint violations, but Lagrangian methods provide weaker guarantees because signed errors can cancel.Whether stronger Lagrangian guarantees are possible remains open.

2 Preliminaries

The preliminaries define finite-horizon CMDPs, their occupancy-measure representation, and the learning objectives used in the paper. They also explain why constrained control is formulated through linear programming and distinguish stronger positive-part regrets from weaker signed regrets.

Finite-horizon CMDPs: A finite-horizon CMDP specifies state and action spaces, time-dependent costs and transitions, an initial state, and horizon H.Immediate costs and constraint costs are bounded in [0, 1], while transitions define the next-state probabilities.
Policies and occupancy measures: Policies are non-stationary randomized mappings from states to action distributions, and occupancy measures record state-action visitation probabilities at each time step.Occupancy measures satisfy probability-flow constraints across the horizon.
CMDP objective: CMDP objectives minimize expected cost while satisfying multiple long-term constraint thresholds, under a feasibility assumption.A feasible unknown policy is assumed to exist, and therefore an optimal policy exists.
CMDP objective: Unlike unconstrained MDPs, CMDPs may require stochastic optimal policies, so Bellman backward induction and greedy optimization need not apply.Linear programming provides a way to compute an optimal constrained policy.
Learning problem: The learning agent interacts for K fixed-length episodes without knowing transitions or rewards, improving from observed trajectories while tracking performance and constraint violations.The paper analyzes both regret relative to the best policy and cumulative constraint-violation measures.
Regret definitions: Positive-part regret bounds are stronger than signed-regret bounds because signed cumulative violations permit cancellation of positive and negative errors.The weaker measure is used for reduced-complexity algorithms.
Linear programming: The occupancy-measure formulation converts constrained control into a linear program whose optimal solutions define optimal Markov policies.The reduction relies on linear cost criteria and the affine structure of the occupancy-measure set.

3 Upper Confidence Bounds for CMDPs

This section develops OptCMDP, a UCRL2-style optimistic algorithm for unknown CMDPs, using confidence sets and an extended occupancy-measure linear program. Its design preserves feasibility and optimism, enabling the stated regret guarantees.

OptCMDP construction: OptCMDP adapts UCRL2 by constructing confidence intervals for unknown costs and transition dynamics at the start of each episode.The confidence intervals use empirical Bernstein concentration for transitions and Hoeffding concentration for costs.
Optimism properties: The optimism requirements are that the optimal policy remains feasible and every policy's estimated value is optimistic relative to its true value.Satisfying both properties yields an optimistic estimate of the optimal value.
Guarantees: The resulting optimization problem is feasible, and the recovered policy is optimistic.These properties are established in Proposition 2 and support the subsequent regret analysis.
Optimistic planning: The algorithm optimizes over plausible CMDPs and recovers a policy from an extended linear program over state-action-state occupancy measures.The extended LP incorporates the uncertainty sets while representing policies through occupancy variables.
Computational formulation: The extended LP contains O(S2HA) constraints and O(S2HA) decision variables, reflecting the computational cost of the occupancy-measure formulation.The formulation can use different concentration inequalities for transition probabilities while retaining an extended-LP representation.
Guarantees: With probability at least 1 −δ, Theorem 3 provides regret bounds for OptCMDP uniformly over any K′ ∈[K].The theorem states the algorithm's regret guarantees under a confidence parameter δ ∈(0, 1).

4 Exploration Bonus for CMDPs

OptCMDP-bonus incorporates cost and transition uncertainty into a single exploration bonus, enabling optimistic CMDP planning with a smaller linear program. Its guarantees retain an OptCMDP-like term but can worsen with state-space dependence, and truncation creates unresolved computational difficulties.

OptCMDP-bonus combines cost and transition uncertainty into one exploration bonus and solves a single optimistic CMDP.The bonus-based formulation uses an LP rather than planning over a set of plausible CMDPs.
O(SAH) constraints and decision variables make OptCMDP-bonus's LP a factor O(S) smaller than OptCMDP's.OptCMDP uses an extended LP with O(S2HA) constraints and decision variables.
With probability at least 1 −δ, Theorem 4 provides regret bounds for OptCMDP-bonus for every K′ ∈[K].
OptCMDP-bonus retains the same e O term as OptCMDP, but its regret-bound constant has worse dependence on S, H, and N.The paper suggests this leads to worse performance than optimistic-model planning as the state space becomes large.
The larger transition-model bonus expands the value-function range beyond [0, H], motivating a truncated Bellman operator.The resulting value function is bounded within [−SH2, H], while applying truncation within CMDPs is not straightforward.
Combining truncation with CMDP occupancy-measure LPs remains unresolved, and dynamic programming is also problematic because constraints prevent Bellman optimality.The authors leave developing a polynomial algorithm or establishing hardness for this problem to future work.

5 Optimistic Dual and Primal-Dual Approaches for CMDPs

The paper develops optimistic dual and primal-dual algorithms for unknown CMDPs, reducing computational demands relative to extended linear-programming approaches. These methods retain guarantees for performance and constraint violations, but their theoretical guarantees are weaker.

5 Optimistic Dual and Primal-Dual Approaches for CMDPs: The algorithms are computationally easier than prior LP-based methods, but the resulting regret guarantees are weaker.The analysis bounds Reg rather than the stronger Reg+ measure used for UCRL-like algorithms; OptPrimalDual-CMDP also has worse regret terms multiplying K than OptDual-CMDP.
5.1 Optimistic Dual Algorithm for CMDPs: OptDual-CMDP uses optimistic dual projected sub-gradient updates, solving an optimistic MDP and updating Lagrange multipliers from constraint violations.The method can be viewed as a decentralized two-player game between the policy and Lagrange multiplier.
5 Optimistic Dual and Primal-Dual Approaches for CMDPs: Both approaches avoid solving a constrained optimization problem at each update by using optimistic MDPs and dynamic-programming-based Q-function computation.OptDual-CMDP computes Q-functions through standard dynamic programming on an extended MDP, while OptPrimalDual-CMDP evaluates them under the current policy.
5 Optimistic Dual and Primal-Dual Approaches for CMDPs: Theorems 5 and 6 establish guarantees for both performance and total constraint violation for OptDual-CMDP and OptPrimalDual-CMDP.The supplied theorem statements assert bounds for any K′ ∈ [K].
5.2 Optimistic Primal Dual approach for CMDPs: OptPrimalDual-CMDP performs incremental optimistic updates of primal and dual variables using exploration bonuses, Mirror Descent, and projected gradient steps.Its policy evaluation uses truncated values, while dual parameters are projected to keep Q-functions bounded and preserve violation guarantees.

6 Conclusions and Summary

The paper analyzes UCRL-like, dual, and primal-dual approaches for learning in CMDPs with safety constraints. It establishes regret guarantees for performance and constraint violations, while emphasizing weaker guarantees for the practically easier dual approaches.

6 Conclusions and Summary: The work analyzes UCRL-like, optimistic dual, and optimistic primal-dual algorithms for combining safety constraints with reinforcement learning.The approaches are motivated respectively by UCRL2 and practical Lagrangian-based algorithms.
6 Conclusions and Summary: All analyzed algorithms receive regret guarantees for both performance and constraint violations.The paper measures learning through regret relative to the main objective and cumulative constraint violations.
6 Conclusions and Summary: Dual and primal-dual approaches provide weaker Reg guarantees than the Reg+ guarantees obtained for UCRL-like algorithms.The paper identifies this difference as a deficiency relevant to designers seeking strong Reg+ performance guarantees.
6 Conclusions and Summary: The paper assumes bounded immediate costs and constraint costs, with Ch(s, a) ∈ [0, 1] and Di,h(s, a) ∈ [0, 1].The regret analysis is conditioned on high-probability good events.

A.2 Optimism

The optimism analysis shows that confidence sets contain suitable models and that the optimal policy remains feasible under the optimistic problems.

A.2 Optimism: Conditioned on the good event, the true transition model belongs to the confidence set, enabling optimistic comparisons.The optimism lemma supplies a transition model in the confidence set for any policy.
A.2 Optimism: Conditioned on the good event, the optimal policy is feasible for every episode's optimistic constraint problem.This property is stated for the true policy and the episode-specific feasible policy set.
A.2 Optimism: The optimism and feasibility lemmas yield value comparisons between optimistic models, the optimal policy, and the actual model.The corollary records both an optimistic upper comparison for the optimal value and a comparison for the executed policy.

A.3 Proof of Theorem 3

The appendix establishes the confidence-event and optimism machinery used to prove regret bounds for optimistic CMDP algorithms. It also shows feasibility of the optimal policy in the optimistic problems.

A.3 Proof of Theorem 3: OptCMDP's regret analysis begins by defining confidence intervals and a high-probability good event for costs, constraint costs, and dynamics.The true CMDP is contained in the plausible set on this event.
A.3 Proof of Theorem 3: Theorem 3 provides high-probability regret bounds for OptCMDP over every K′ ∈ [K].The proof separately analyzes regret for the main cost and constraint violations.
A.3 Proof of Theorem 3: The analysis uses bounded immediate costs and constraint costs together with concentration inequalities and union bounds.These assumptions and probability arguments establish the basic good event used throughout the proof.
A.3 Proof of Theorem 3: Optimism lemmas compare optimistic value functions with values under the true model for costs and constraint costs.These comparisons support the regret decomposition used in the proof.
A.3 Proof of Theorem 3: The optimistic optimization problem remains feasible because the optimal policy is feasible under the good event.The feasibility argument constructs the set of policies satisfying constraints across possible episode models.

B.3 Proof of Theorem 4

This section establishes high-probability regret bounds for OptCMDP-bonus and analyzes how its optimistic value estimates support those bounds. It also notes that its value-function range differs from OptCMDP, worsening the constant term.

Regret guarantee: Theorem 4 gives high-probability regret bounds for OptCMDP-bonus for every K′ ∈[K].The guarantee holds with probability at least 1 −δ.
Value estimates: Unlike OptCMDP-bonus, the estimated value function is not constrained to [0,H]; it is bounded in [−SH^2,H].This follows from the bounded bonus and the algorithm’s value-estimation construction.
Comparison with OptCMDP: The different value-function range produces a worse constant term than in OptCMDP, despite similar dependence in √K.The comparison is stated explicitly in Remark 2.
Proof strategy: The proof conditions on a good event and uses optimism together with an on-policy error bound.The cited proof passages connect the theorem to optimism and Lemma 31.
Constraint violations: The constraint-violation analysis derives bounds for every constraint index i ∈[I] and every K′ ∈[K].The section explicitly turns to regret bounds on constraint violation.

C.3 Proof of Theorem 5

This section proves regret guarantees for OptDual-CMDP using optimism, good-event conditioning, and constrained convex-optimization arguments. The analysis also highlights the algorithm’s relationship to incremental primal-dual methods and state-action visitation convexity.

Regret guarantee: Theorem 5 establishes regret bounds for OptDual-CMDP for any K′ ∈[K].The theorem is proved after conditioning on a high-probability good event.
Proof strategy: The proof first establishes dual optimism and then applies constrained convex-optimization results to derive regret bounds.The good-event framework supports both steps.
Convex formulation: In the state-action visitation polytope, the reinforcement-learning objective is linear and therefore convex, enabling constrained convex-optimization tools.The problem remains constrained to the state-action visitation polytope.
Error control: The analysis uses Online Mirror Descent terms and policy-estimation optimism to control optimization and on-policy errors.The OMD analysis uses KL divergence as the Bregman distance.

D.3 Proof of Theorem 6

This section establishes regret bounds for OptPrimalDual-CMDP through good-event optimism, projected primal-dual updates, and constrained convex-optimization analysis. Its computational approach uses truncated policy estimation but yields weaker guarantees than OptDual-CMDP.

Regret guarantee: Theorem 6 establishes regret bounds for OptPrimalDual-CMDP for any K′ ∈[K].The theorem follows the section’s good-event and optimism analysis.
Proof strategy: The proof establishes optimism and then applies adapted constrained convex-optimization results to bound regret.The analysis is conditioned on a high-probability good event.
Primal-dual recursion: Projected primal-dual updates use non-expansiveness of projection to derive the update-rule recursion bound.This is the key step identified in the proof of Lemma 28.

E Bounds of On-Policy Errors

This section develops on-policy error bounds for optimistic models, truncated policy estimation, and bonus-based optimism. The proofs combine value-difference arguments, concentration assumptions, Jensen’s inequality, and self-bounding relations.

Error settings: The section analyzes on-policy errors for optimistic models and truncated policy estimation under assumptions on costs, transitions, and value estimates.The corresponding lemmas define the true and optimistic models and the acting policy πk.
Bonus-based optimism: Bonus-based optimism adds a separate error term to the value-difference analysis, while the true value remains bounded in [0,H].The proof bounds the additional term using Lemma 32.
Value ranges: The bonus-based analysis allows estimated values in [−SH^2,H] because instantaneous costs can be negative under its assumptions.This range is used when bounding the relevant error terms.
Value-difference analysis: The proofs use the value difference lemma to relate model, cost, transition, and policy-estimation discrepancies to value-function differences.The value difference lemma is identified as central to the OptPrimalDual-CMDP analysis.
Self-bounding step: Self-bounding inequalities convert relations of the form 0 ≤ X ≤ a + b√X into upper bounds on X.This auxiliary result is used to close the error analysis.

G Useful Results from Constraint Convex Optimization

This section develops constraint-convex-optimization results used to establish bounds for the dual algorithms, including dual formulations, optimality conditions, and bounds on optimal dual parameters.

Problem setup: The section formulates a convex optimization problem with convex objective and constraint functions, linear equality constraints, and an associated value function.The value function and dual problem are introduced before deriving the results used later.
Problem setup: The Lagrangian combines the objective, inequality constraints, and equality constraints as L(x, λ, µ) = f(x) + λT g(x) + µT (Ax + b).An optimal dual solution is denoted by λ∗, µ∗.
Regularity assumption: Under the stated assumption, strong duality holds, so the optimal dual value equals the primal optimal value: qopt = fopt.This equality is used in the subsequent optimality and bounding arguments.
Regularity assumption: Assumption 3 requires a finite attained optimum and a Slater point satisfying strict inequalities and Abx + b = 0.The Slater point lies in the relative interior of X.
Optimality conditions: Theorem 41 characterizes optimal solutions of the constrained problem through subgradient conditions involving the value function.The section explicitly defines ∂f(x) as the set of all sub-gradients of f at x.
Dual bounds: A variant of Beck’s theorem derives relations for an optimal dual solution λ∗ when 2∥λ∗∥1 ≤ ρ, using a feasible point satisfying Aex + b = 0.The resulting relations are rearranged using the assumption on the dual norm parameter.
Dual bounds: A further adjusted theorem bounds the optimal dual parameter using the properties of a Slater point, followed by a corollary and proof.The result is presented as an adjustment of Beck 2017, Theorem 8.42.