PaperlayerView exact revision on arXiv

Source-linked AI summary

Constrained Upper Confidence Reinforcement Learning

Liyuan Zheng, Lillian J. Ratliff

arXiv:2001.09377v1cs.LGstat.ML

TL;DR

In CMDPs, learning a high-reward policy must also satisfy cost constraints, including during exploration. C-UCRL uses confidence estimates and robust optimization when transitions are known but rewards and costs are unknown; it reports high-probability constraint satisfaction during learning and sub-linear reward regret.

  • Problem

    CMDP learning must maximize reward subject to cost constraints, while safety during initial learning remains a concern and prior model-based safety methods lack regret analysis.

    Source: §1 · pp. 1–2

  • Method

    C-UCRL combines upper-confidence reinforcement learning with robust linear programming, assuming known transitions and unknown rewards and constraint costs.

    Source: §1 · p. 2

  • Results

    C-UCRL guarantees constraint satisfaction during learning with probability at least 1 −δ and achieves O(T^(3/4)√(log(T/δ))) reward regret.

    Source: §1 · p. 2, §6 · p. 17

  • Takeaways & Limitations

    The paper presents C-UCRL as an approach for learning under cost constraints while targeting both learning-time safety and sub-linear reward regret.

    Source: §1 · p. 2, §6 · p. 17

    The approach requires a known transition kernel, and the authors expect its sample complexity may be much worse than approaches without safe-learning criteria.

    Source: §6 · p. 18

Abstract

from arXiv · show

Constrained Markov Decision Processes are a class of stochastic decision problems in which the decision maker must select a policy that satisfies auxiliary cost constraints. This paper extends upper confidence reinforcement learning for settings in which the reward function and the constraints, described by cost functions, are unknown a priori but the transition kernel is known. Such a setting is well-motivated by a number of applications including exploration of unknown, potentially unsafe, environments. We present an algorithm C-UCRL and show that it achieves sub-linear regret ($ O(T^{\frac{3}{4}}\sqrt{\log(T/\delta)})$) with respect to the reward while satisfying the constraints even while learning with probability $1-\delta$. Illustrative examples are provided.

1. Introduction

CMDPs separate reward from cost constraints, but safe exploration requires respecting those constraints from the start of learning. C-UCRL combines upper-confidence learning with robust optimization to target high-probability constraint satisfaction during learning and sub-linear reward regret.

1. Introduction

  • CMDPs maximize total reward while requiring expected trajectory costs to satisfy constraints, keeping return and risk as separate criteria.This contrasts with risk-sensitive formulations that transform the optimization criterion to balance return and risk.Source: §1 · p. 1
  • Policy-gradient CMDP methods may lack safety guarantees during initial learning, while model-based safety methods have lacked regret analysis.The introduction identifies this combination of learning-time safety and reward-regret guarantees as the motivation for C-UCRL.Source: §1 · pp. 1–2
  • The setting assumes known transition dynamics but unknown rewards and constraint costs, as in the example of a rover exploring potentially hazardous states.The costs can represent limits on visits to hazardous states.Source: §1 · p. 2
  • C-UCRL combines classical UCRL2 with robust linear programming to learn policies under reward and cost uncertainty.The paper presents illustrative examples comparing C-UCRL with Risk-Sensitive UCRL2; its organization passage reports that the latter fails to converge to the optimal policy while C-UCRL does.Source: §1 · p. 2
  • C-UCRL is guaranteed to satisfy constraints during learning with probability at least 1 −δ and achieves reward regret O(T^(3/4) sqrt(log(T/δ))).Source: §1 · p. 2

2. Related Work

Related work addresses CMDP policy search, model-based safety, linear programming, and constrained bandits. C-UCRL differs in its known-transition setting and its use of reward and cost confidence bounds with robust optimization.

2. Related Work

  • Constrained policy-search methods include Lagrangian actor-critic [5, 8] and CPO [1], but their safety and regret guarantees differ.The passage says Lagrangian methods generally do not guarantee safe learning, while CPO guarantees constraint satisfaction during training but lacks reward-regret analysis.Source: §2 · p. 2
  • Prior linear-programming work considered known rewards, costs, and transitions with uncertain initial state, whereas this setting has unknown stochastic rewards and costs.The transition kernel is known in the present setting.Source: §2 · p. 3
  • C-UCRL extends UCRL2 by incorporating constraints, assuming known transitions, and using a robust linear program to assess reward regret against an optimal randomized policy.CMDPs need not admit deterministic optimal policies.Source: §2 · p. 3
  • Unlike prior constrained bandit approaches using reward-to-cost bounds and a known stopping budget [28], C-UCRL bounds reward and cost separately and solves a linear program.With one state, the setting reduces to constrained bandits, where obtainable policies can be randomized rather than deterministic.Source: §2 · p. 3

3. Constrained Upper Confidence Reinforcement Learning Algorithm

C-UCRL formulates a CMDP with known transitions and unknown stochastic rewards and costs, then uses confidence estimates and robust optimization to select policies. Its episodes combine baseline-policy exploration with increasingly long execution of the selected policy.

3. Constrained Upper Confidence Reinforcement Learning Algorithm

  • The model assumes known transition probabilities and unknown stochastic rewards and costs; CMDP-optimal policies can be stochastic.The stochastic-policy distinction separates constrained MDPs from unconstrained tabular MDPs, where optimal policies are always deterministic.Source: §3 · p. 3, §3.1 · p. 4

3.1. Constrained Markov Decision Processes

  • The CMDP formulation maximizes average reward subject to average-cost bounds, using the steady-state occupation measure in a linear program.When mean rewards, mean costs, and the transition kernel are given, the passage states that the CMDP can be solved by this linear program.Source: §3.1 · p. 4

3.2. Constrained Upper Confidence Reinforcement Learning Algorithm

  • C-UCRL uses optimistic reward and pessimistic cost confidence estimates in a robust linear program to choose a policy satisfying estimated constraints.This implements the stated principle of optimism under reward uncertainty and pessimism under cost uncertainty.Source: §3.2 · pp. 4, 6
  • Choosing the baseline policy π0 is important, but further heuristic or theoretical development for selecting it is left to future work.The mixing-time heuristic is based on the known transition kernel and the Markov chain induced by π0.Source: §3.2 · p. 5
  • The analysis assumes the baseline policy and h make each episode's robust linear program feasible, with h chosen based on the baseline-induced chain's mixing time.The paper notes that feasibility may fail in the first episode and leaves theoretical guarantees of a nontrivial first-episode feasible set for future work.Source: §3.2 · p. 6
  • Each episode runs the baseline policy for h exploration steps, estimates rewards and costs, then executes the selected policy for (k − 1)h steps.Episode k therefore lasts kh steps, with execution of the selected policy increasing linearly across episodes.Source: §3.2 · p. 6

4. Analysis: Regret Bounds and High-Probability Safety Guarantees

C-UCRL is analyzed for high-probability constraint satisfaction throughout learning and sub-linear reward regret. The analysis also specializes these guarantees to constrained multi-armed bandits.

4.1. Constraint/Safety Guarantees

  • Confidence intervals define plausible CMDPs, and with probability at least 1−δ the true CMDP remains in the plausible sets across episodes.Source: §4.1 · p. 7
  • C-UCRL is δ-safe: with probability at least 1−δ, every executed policy satisfies each cost constraint at every time step.Source: §4.1 · pp. 6, 8

4.2. Regret Analysis of C-UCRL

  • Because regret depends on estimates for all state-action pairs, C-UCRL repeatedly runs a baseline policy whose steady-state occupancy is positive everywhere.Source: §4.2 · p. 11
  • With probability at least 1−δ, C-UCRL's total pseudo-regret is O(T^(3/4) sqrt(log(T/δ))).Source: §4.2 · p. 12

4.3. Specializing to the Constrained Multi-Armed Bandit Setting

  • For constrained multi-armed bandits (S=1), C-UCRL is δ-safe and, under Proposition 5's assumptions, has total pseudo-regret O(T^(3/4) sqrt(log(T/δ))) with probability at least 1−δ.Source: §4.3 · p. 13

5. Experiments

The experiments illustrate C-UCRL in a constrained bandit and two CMDPs, including settings where the constrained optimum is randomized. Comparisons with risk-sensitive UCRL2 highlight differences in learned policies, constraint violations, and reward regret.

5.1. Two Armed Bandit with per Round Budget Constraints

  • In the bandit, the constrained optimum pulls arm one with probability 0.75, and C-UCRL’s average pull count for that arm never exceeds 0.75.Arm one has higher reward, but its mean cost exceeds the per-round constraint.Source: §5.1 · p. 14

5.2. Three State CMDP

  • The three-state CMDP has risky navigation actions and safe stay actions; its expected average-cost constraint is less than 0.2, making the constrained optimum randomized.Without the constraint, navigating in every state is optimal.Source: §5.2 · p. 14
  • The three-state example compares C-UCRL with RS-UCRL2, which applies UCRL2 to the combined reward and cost criterion r−λc.Figure 2 also reports RS-UCRL2 constraint-violation probability over 30 training episodes for different λ values.Source: §5.2 · p. 14, Figure 2 · p. 15
  • In the three-state CMDP, C-UCRL converges to the optimal randomized policy and does not violate the constraint during learning; RS-UCRL2 can violate it or incur high regret as λ changes.The experiment sets δ to 0.1, corresponding to at least 0.9 probability that the constraint will not be violated in all episodes.Source: §5.2 · pp. 15–16

5.3. Grid World with Safety Constraints

  • The grid-world setup bounds the per-step probability of entering high-cost, potentially unsafe states; the constrained optimal policy uses both the blue and orange routes.The darker states represent larger mean costs, and the agent travels from origin O to destination D for reward.Source: §5.3 · p. 16, Figure 4 · p. 17
  • In the grid-world example, C-UCRL converges to the optimal policy, while RS-UCRL2 learns a single route that can bring either constraint violations or large reward regret.The example also reports that conservative RS-UCRL2 can avoid violations in a larger grid, but with much larger reward regret than C-UCRL.Source: §5.3 · p. 17
  • In the larger safety grid, conservative RS-UCRL2 can learn a policy that avoids constraint violations, but with much larger reward regret than C-UCRL.Source: §5.3 · p. 17

6. Conclusion

The paper formulates safe reinforcement learning with known transitions but unknown rewards and constraint costs, and proposes C-UCRL. Its guarantees and examples are qualified by choices needed to keep each episode’s robust linear program feasible and by likely higher sample complexity.

6. Conclusion

  • C-UCRL addresses safe learning when the transition kernel is known but rewards and constraint costs are unknown.The paper proposes the algorithm for learning an optimal policy in this CMDP setting.Source: §6 · p. 17
  • Examples illustrate that C-UCRL can learn randomized optimal policies and provide high-probability guarantees of remaining safe during learning.The paper identifies both properties as key features of the examples.Source: §6 · pp. 17–18
  • The baseline policy π0 and its execution duration h must be chosen so each episode’s robust linear program has a non-trivial feasible set.The paper bases h on the mixing time of the Markov chain induced by π0; ensuring non-trivial feasibility remains future work.Source: §6 · p. 18
  • C-UCRL likely has much worse sample complexity than approaches without safety criteria during exploration, and it requires a known transition kernel.Extending the approach to unknown transitions is not immediate under its robust linear-programming proof technique.Source: §6 · p. 18
Loading 2001.09377v1…