PaperlayerView exact revision on arXiv

Source-linked AI summary

Provably Efficient Safe Exploration via Primal-Dual Policy Optimization

Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, Mihailo R. Jovanović

arXiv:2003.00534v2cs.LGmath.OCstat.ML

TL;DR

The paper addresses the lack of provable computational and statistical efficiency guarantees for safe reinforcement learning in linear episodic CMDPs. It proposes OPDOP, combining least-squares policy evaluation with a safe-exploration bonus, and proves sublinear regret and constraint violation under bandit feedback.

  • Problem

    Existing CMDP safe reinforcement learning algorithms often lack theoretical guarantees or only converge asymptotically in batch offline settings.

  • Method

    OPDOP estimates value functions using least-squares policy evaluation combined with an additional bonus term for safe exploration.

  • Results

    The algorithm achieves eO(dH^2.5√T) regret and eO(dH^2.5√T) constraint violation under bandit feedback for fixed reward and utility functions.

  • Takeaways & Limitations

    The work provides, to the authors’ knowledge, the first provably efficient online policy optimization algorithm for CMDPs with safe exploration and function approximation.

  • Takeaways & Limitations

    Designing provably efficient reinforcement learning algorithms beyond the paper’s linear-type CMDP settings remains open.

Abstract

from arXiv · show

We study the Safe Reinforcement Learning (SRL) problem using the Constrained Markov Decision Process (CMDP) formulation in which an agent aims to maximize the expected total reward subject to a safety constraint on the expected total value of a utility function. We focus on an episodic setting with the function approximation where the Markov transition kernels have a linear structure but do not impose any additional assumptions on the sampling model. Designing SRL algorithms with provable computational and statistical efficiency is particularly challenging under this setting because of the need to incorporate both the safety constraint and the function approximation into the fundamental exploitation/exploration tradeoff. To this end, we present an \underline{O}ptimistic \underline{P}rimal-\underline{D}ual Proximal Policy \underline{OP}timization (OPDOP) algorithm where the value function is estimated by combining the least-squares policy evaluation and an additional bonus term for safe exploration. We prove that the proposed algorithm achieves an $\tilde{O}(d H^{2.5}\sqrt{T})$ regret and an $\tilde{O}(d H^{2.5}\sqrt{T})$ constraint violation, where $d$ is the dimension of the feature mapping, $H$ is the horizon of each episode, and $T$ is the total number of steps. These bounds hold when the reward/utility functions are fixed but the feedback after each episode is bandit. Our bounds depend on the capacity of the state-action space only through the dimension of the feature mapping and thus our results hold even when the number of states goes to infinity. To the best of our knowledge, we provide the first provably efficient online policy optimization algorithm for CMDP with safe exploration in the function approximation setting.

1 Introduction

Safe reinforcement learning formulates reward maximization with utility constraints, making exploration–exploitation more difficult when safety information is unknown. This paper proposes OPDOP to provide online efficiency guarantees for CMDPs with linear function approximation.

  • Motivation: CMDPs extend MDPs with utility constraints on expected total utility, complicating the exploration–exploitation tradeoff.The constraint represents safety requirements in settings such as autonomous driving, medicine, and finance.
  • Motivation: Existing policy-based SRL methods generally lack theoretical guarantees or converge only asymptotically in batch offline settings.The paper identifies computational and statistical efficiency guarantees for online SRL as an important open need.
  • Research question: The paper asks whether CMDPs admit a provably sample-efficient online policy optimization algorithm.The target setting involves streaming interaction and unknown safety constraints.
  • Contribution: OPDOP combines optimistic value estimation with least-squares policy evaluation and an additional safe-exploration bonus.Its name expands to Optimistic Primal-Dual Proximal Policy Optimization.
  • Related work: The proposed approach extends optimistic PPO with UCB exploration to constrained RL and supplies theoretical efficiency guarantees.Prior optimistic PPO results cited in the paper apply to unconstrained problems, while several constrained methods lack such guarantees.
  • Contribution: The bounds depend on state-action capacity through feature dimension rather than the number of states, allowing potentially infinite state spaces.The result is stated as the first provably efficient online policy optimization algorithm for CMDPs with safe exploration in function approximation.

2 Problem Setup

The paper studies episodic CMDPs with unknown linear transition structure, fixed deterministic reward and utility functions, and bandit feedback at visited state-action pairs. The objective is hindsight reward maximization subject to an expected-utility constraint while controlling violations during exploration.

  • CMDP model: The episodic CMDP contains states, actions, horizon H, transition kernels, reward functions, and utility functions.The state space may be measurable and potentially infinite.
  • Feedback model: Under bandit feedback, the agent observes reward and utility values only at visited state-action pairs, with reward and utility fixed across episodes.The analysis assumes deterministic reward and utility functions and notes extension to random functions.
  • Learning objective: The learning objective maximizes expected total reward subject to a constraint requiring expected total utility to meet threshold b.The optimal policy is computed with full knowledge of reward and utility functions and is therefore optimal in hindsight.
  • Safe exploration: Because utility information is revealed only after policy selection, policies may violate the constraint during exploration while total violations are minimized.Regret compares against the best fixed policy in hindsight over K episodes.
  • Guarantees: The algorithm targets sublinear regret and constraint violation in total steps T = HK, with O(1/ε^2) steps sufficient for both quantities to be O(ε) with high probability.The analysis assumes a Slater condition and bounded optimal dual variable.
  • Linear function approximation: The linear CMDP assumption represents transition and reward/utility structure through feature maps whose dimensions are bounded by d.The framework includes tabular MDPs, feature-embedded transitions, and linear combinations of base models.
  • Scope: The analysis is restricted to linear-type CMDPs; designing provably efficient algorithms beyond these transition structures remains open.The paper also distinguishes its feature-map definition from other linear MDP definitions, despite both including tabular cases.

3 Proposed Algorithm

OPDOP updates policies, dual variables, and optimistic value estimates in three stages. It uses proximal mirror-descent policy improvement, constraint-driven dual updates, and LSTD evaluation augmented with UCB exploration bonuses.

  • Algorithm structure: Each episode performs policy improvement, dual update, and policy evaluation.The policy is improved from the previous policy, the dual variable responds to constraint violation, and the new policy is evaluated optimistically.
  • Policy Improvement: Policy improvement uses an easily computable proximal step instead of an oracle solver for Q-learning, PPO, or TRPO.The update is based on the performance difference lemma and is implemented in online mirror-descent fashion.
  • Policy Improvement: Mixing the previous policy with the uniform action distribution ensures absolute continuity and uniformly bounds the KL divergence.The mixed policy uses parameter θ ∈ (0, 1].
  • Dual Update: The dual update increases emphasis on utility when the approximated constraint is violated and otherwise favors reward maximization.The multiplier is projected onto [0, χ], with χ chosen to include the optimal dual variable under the stated analysis.
  • Policy Evaluation: Policy evaluation applies LSTD to historical trajectories and adds UCB bonuses to produce optimistic reward and utility value estimates.Least-squares estimates are formed for transition-value terms and reward or utility functions.
  • Computational efficiency: The total time complexity is O(d^2|A|T), while recursive updates require O((d^2 + |A|)H) space.Sherman–Morrison updates and Monte Carlo integration are cited as computational strategies.

4 Regret and Constraint Violation Analysis

The analysis establishes high-probability sublinear regret and constraint-violation bounds for OPDOP under the Slater and linear-MDP assumptions. The proof combines primal-dual mirror descent, optimistic evaluation, martingale concentration, and elliptical-potential control.

  • Interpretation: The bounds have optimal dependence on T up to logarithmic factors and add one factor of H relative to comparable unconstrained linear-MDP bounds.The paper attributes the extra H to uniformly bounding constraint violation.
  • Tabular case: In the tabular specialization, the feature dimension becomes d = |S|^2|A|, yielding corresponding regret and constraint-violation bounds.The paper notes that this dependence can be improved using other optimistic policy-evaluation methods specialized to tabular settings.
  • Proof outline: The proof couples regret and constraint violation through a primal-dual mirror-descent policy-improvement inequality.The coupling uses the performance difference lemma and the dual update.
  • Proof outline: Martingale concentration controls trajectory fluctuations, while UCB optimism and the elliptical potential lemma control model prediction error.The proof invokes Azuma–Hoeffding for martingale terms.

5 Further Results on Tabular Case

The tabular CMDP is represented within the linear MDP framework using canonical feature maps, enabling reward, utility, and transition estimation with optimistic policy evaluation. The resulting algorithm has theoretical regret and constraint-violation guarantees and is described as generic enough to handle infinite state spaces.

  • Tabular representation: The tabular CMDP is embedded in the linear MDP framework through feature dimensions d1 = |S|^2|A| and d2 = |S||A|.The construction uses canonical basis features for transitions and state-action features for rewards and utilities.
  • Tabular representation: Canonical feature maps represent transition probabilities, rewards, and utilities as parameter vectors in the linear model.The transition parameter stores conditional probabilities, while analogous parameters represent reward and utility functions.
  • Guarantees: The proof of Theorem 1 is generic when policy evaluation is sample-efficient, and the algorithm can handle an infinite state space.The tabular policy-evaluation procedure is presented as an additional efficient option for the finite tabular setting.
  • Optimistic policy evaluation: Optimistic policy evaluation estimates reward and utility values using least-squares model estimates, transition estimates, and an additional bonus term.The estimated action values are then used for policy improvement and the dual update.
  • Guarantees: Theorem 2 provides high-probability regret and constraint-violation guarantees for the tabular case under the stated assumptions and parameter choices.The theorem uses probability 1 − p and specifies α, θ = 1/K, and λ = 1 in Algorithm 1.

6 Concluding Remarks

The paper develops a provably efficient safe reinforcement learning algorithm for linear MDPs by extending proximal policy optimization to constrained MDPs with UCB exploration. It establishes sublinear regret and constraint violation under mild regularity conditions, including settings with bandit feedback for reward and utility functions.

  • Concluding remarks: The algorithm extends proximal policy optimization to constrained MDPs and incorporates UCB exploration in the linear MDP setting.The paper presents this as its central algorithmic development.
  • Concluding remarks: The paper proves sublinear regret and constraint violation bounds in the total number of steps under mild regularity conditions.The supplied conclusion identifies both regret and constraint violation as the principal guarantees.
  • Concluding remarks: The algorithm applies when reward and utility functions are observed through bandit feedback.This extends the stated setting beyond full-information feedback for those functions.
  • Concluding remarks: The paper claims to provide the first provably efficient online policy optimization algorithm for CMDPs with safe exploration in the function-approximation setting.This claim is stated as the paper’s concluding contribution.
  • Analysis: The analysis decomposes regret and constraint violation using optimistic policy evaluation, model-prediction errors, and separate reward and utility terms.The proof introduces reward and utility model-prediction errors and expands the corresponding regret components.

B Proof of Regret and Constraint Violation

The proof targets sublinear regret and constraint violation over T = KH total steps, using a theorem under the paper’s assumptions and selected algorithm parameters. The result is stated with high probability and absolute-constant factors.

  • Setup: The analysis defines total interaction length as T := KH, where K is the number of episodes and H is the horizon.The theorem proof is organized around regret and constraint violation over these total steps.
  • Theorem 1: Theorem 1 states regret and constraint-violation guarantees under Assumptions 1 and 2 with specified choices of α, θ, and λ.The supplied theorem text specifies θ = 1/K and λ = 1, while α is set according to the theorem’s displayed condition.
  • Theorem 1: The stated guarantees hold with probability 1 − p, with C and C′ denoting absolute constants.The proof separately addresses the regret and constraint-violation bounds.

B.1 Proof of Regret Bound

The regret proof combines primal-dual mirror-descent analysis with optimistic model estimation and martingale concentration. Separate lemmas control policy improvement, model-prediction error, and stochastic fluctuations before the final regret bound is assembled.

  • Primal-dual policy analysis: The policy update is analyzed as a primal-dual mirror-descent step, producing upper bounds on weighted differences of estimated values.The dual update is then used to simplify the resulting regret expression.
  • Regret decomposition: The regret decomposition separates policy differences from cumulative model-prediction errors for reward and utility values.The proof uses expectations under the hindsight-optimal policy and standard inequalities to bound the resulting terms.
  • Concentration bounds: The model-prediction error is controlled by an optimistic UCB argument with a confidence parameter β depending on d, H, T, and p.The resulting bound holds uniformly over episodes, steps, states, and actions with high probability.
  • Concentration bounds: A martingale lemma controls stochastic fluctuations using truncation and the Azuma-Hoeffding inequality.The proof bounds the martingale increments after truncating the relevant quantity.
  • Final assembly: The final regret bound follows by substituting the model-error and martingale bounds into the primal-dual inequality.The proof also specifies logarithmic action-space dependence and absolute-constant factors.
  • Constraint violation: Constraint violation is extracted by refining the primal-dual inequality and using feasibility of an appropriate comparator policy.The argument uses linearity in occupancy measures to construct a policy from their average.

C Further Results on Tabular Case

The tabular CMDP is represented as a special case of the linear function-approximation model using canonical feature maps. This specialization yields a dimension-dependent formulation and corresponding tabular algorithmic results.

  • Tabular feature representation: The transition kernel, reward, and utility functions are encoded with canonical basis feature maps and parameter vectors.The transition feature dimension is d1 = |S|^2|A|, while reward and utility feature dimension is d2 = |S||A|.
  • Tabular feature representation: The tabular CMDP is a special case of the linear model with d = max(d1, d2) = |S|^2|A|.The transition representation determines the dimension used in the general assumption.
  • Algorithmic specialization: Algorithm 1 applies to the tabular case by estimating value functions and then performing policy improvement and dual updates.The tabular construction uses the regression features associated with the reward and utility estimators.
  • Guarantees: The tabular corollary sets α, θ, and λ as specified and gives regret and constraint-violation guarantees with probability 1 − p.The supplied theorem statement includes the parameter choices and identifies C1, C, and C′ as absolute constants.

C.2 Further Results: Proof of Theorem 2

The proof of the tabular theorem combines optimistic least-squares policy evaluation with visitation-based bonuses, martingale concentration, and self-normalized bounds. These ingredients control both regret and constraint violation under the theorem’s parameter choices.

  • Proof strategy: The optimistic policy-evaluation analysis identifies accumulated bonus terms as the dominant contribution to the final regret and constraint-violation bounds.The bonus implements optimism in the face of uncertainty and can be combined with alternative optimistic policy-evaluation methods.
  • Concentration analysis: The proof bounds estimation errors through visitation counters, martingale sequences, Cauchy–Schwarz inequalities, and self-normalized concentration results.These bounds are applied across episodes, stages, states, and actions to control the regression and transition-prediction errors.
  • Optimistic evaluation: The algorithm estimates transition, reward, and utility quantities using regularized regression and adds a bonus term for safe exploration.The regularization parameter is λ > 0, and β controls the bonus magnitude.
  • Regret analysis: The regret proof concludes after bounding the accumulated estimation and bonus terms with logarithmic factors involving |S|, |A|, T, and p.The cited proof passage states that the resulting bound follows from the preceding inequalities.
  • Constraint analysis: The constraint-violation proof reuses the martingale and bonus bounds for the utility function and invokes the constraint-violation lemma.The analysis sets λ and β as in the earlier result.

E Supporting Lemmas from Optimization

The supporting optimization results establish strong duality and control the dual variables under the Slater condition. They also relate approximate feasibility to constraint violation through the dual formulation.

  • Duality assumptions: The Slater condition assumes a policy whose expected utility exceeds the constraint threshold by γ > 0.This condition supplies a strictly feasible policy for the constrained problem.
  • Duality assumptions: Under the Slater condition, the constrained finite-horizon problem satisfies strong duality.The optimal dual solution minimizes the dual function over nonnegative dual variables.
  • Dual-variable control: The Slater condition bounds sublevel sets of the dual function and consequently helps bound optimal dual variables.The paper defines the relevant sublevel set and derives a boundedness corollary.
  • Constraint control: The constraint-violation lemma converts a weak approximate policy guarantee into a bound on the positive part of the constraint violation.The result assumes the Slater condition and a sufficiently large bound on the optimal dual variable.

F Other Supporting Lemmas

The remaining lemmas provide the concentration, covering, KL-divergence, and performance-difference tools used in the analysis. Together they support high-probability control of stochastic regression and policy-update terms.

  • Policy comparison: The performance-difference lemma relates the values of two policies and supports comparisons between the learned and reference policies.It applies to any two policies in the finite-horizon policy class.
  • Concentration tools: Self-normalized concentration controls stochastic processes with conditionally zero-mean sub-Gaussian noise and predictable vector features.The lemma assumes a positive-definite normalization matrix and bounded feature norms.
  • Concentration tools: The customized concentration lemma applies these bounds to the reward and utility processes used by Algorithm 2.With λ = 1, the result holds uniformly over episode and stage indices with high probability.
  • Policy regularization: The KL-divergence lemmas provide a pushback property and bound the divergence after mixing a policy with the uniform distribution.The uniform bound is D(π1 | π̃2) ≤ log(|A|/θ).
Loading 2003.00534v2…