PaperlayerView exact revision on arXiv

Source-linked AI summary

Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraints

Donghao Li, Ruiquan Huang, Cong Shen, Jing Yang

arXiv:2306.06265v1cs.LGcs.ITmath.ITstat.ML

TL;DR

In practical RL deployments, exploration can degrade performance before the agent has learned enough, even when a satisfactory baseline policy is available. StepMix addresses this with policies that interpolate between the baseline and an optimistic policy. The analysis shows near-optimal regret while maintaining the conservative constraint, and extends similar guarantees to sufficiently large offline datasets.

  • Problem

    Practical RL systems may have a satisfactory baseline but lack a performance guarantee throughout learning, when exploration can cause degradation.

    Source: §1 · p. 1

  • Method

    StepMix uses Bernstein-based uncertainty estimates to construct an optimistic policy and candidate policies that smoothly interpolate between it and the safe baseline.

    Source: §1 · p. 2, §4.2 · p. 5

  • Results

    StepMix and EpsMix achieve near-optimal regret order as in the constraint-free setting while never violating the conservative constraint during learning.

    Source: §1 · p. 2, §8 · p. 11

  • Takeaways & Limitations

    With a sufficiently large offline dataset, learning a baseline from it can preserve the algorithms' conservative guarantee and regret.

    Source: §1 · p. 2, §8 · p. 11

    EpsMix is less conservative than StepMix: a selected episode policy's expected return may fall below the threshold.

    Source: §5 · p. 8

Abstract

from arXiv · show

This paper investigates conservative exploration in reinforcement learning where the performance of the learning agent is guaranteed to be above a certain threshold throughout the learning process. It focuses on the tabular episodic Markov Decision Process (MDP) setting that has finite states and actions. With the knowledge of an existing safe baseline policy, an algorithm termed as StepMix is proposed to balance the exploitation and exploration while ensuring that the conservative constraint is never violated in each episode with high probability. StepMix features a unique design of a mixture policy that adaptively and smoothly interpolates between the baseline policy and the optimistic policy. Theoretical analysis shows that StepMix achieves near-optimal regret order as in the constraint-free setting, indicating that obeying the stringent episode-wise conservative constraint does not compromise the learning performance. Besides, a randomization-based EpsMix algorithm is also proposed and shown to achieve the same performance as StepMix. The algorithm design and theoretical analysis are further extended to the setting where the baseline policy is not given a priori but must be learned from an offline dataset, and it is proved that similar conservative guarantee and regret can be achieved if the offline dataset is sufficiently large. Experiment results corroborate the theoretical analysis and demonstrate the effectiveness of the proposed conservative exploration strategies.

1 Introduction

The paper asks whether reinforcement learning can explore while keeping expected reward above a baseline in every episode. It proposes mixture-based algorithms and reports near-optimal regret with high-probability conservative guarantees.

1 Introduction

  • Prior approaches that bank conservative budget across episodes cannot ensure a reward threshold in every episode, leaving episode-wise conservative exploration unresolved.The paper frames this per-episode requirement as more stringent than cumulative constraints.Source: §1 · pp. 1–2
  • StepMix constructs optimistic policies and smoothly interpolates them with a safe baseline, mixing candidate policies when needed to balance safe exploration and exploitation.Its design uses Bernstein-based uncertainty estimates to construct the optimistic policy.Source: §1 · p. 2
  • StepMix achieves order-optimal unconstrained-setting regret while satisfying the conservative constraint throughout learning with high probability; the constraint adds regret rather than a multiplicative coefficient.The introduction also reports that randomization-based EpsMix achieves the same regret and conservative guarantee.Source: §1 · p. 2
  • With an offline dataset from an unknown safe behavior policy, similar safety and regret guarantees hold when the dataset is sufficiently large.The paper characterizes how dataset size and behavior-policy quality affect those guarantees.Source: §1 · p. 2
  • Synthetic experiments corroborate the theoretical findings and report better performance for StepMix and EpsMix than for other baseline algorithms.The introduction attributes efficient implementation to the explicit design of optimistic, candidate, and mixture policies.Source: §1 · p. 2

2 Related Works

Related work spans unconstrained episodic tabular MDPs, conservative exploration, and constrained MDPs with baseline policies. The paper distinguishes its episode-wise requirement from prior cumulative conservative constraints.

Unconstrained Episodic Tabular MDPs

Conservative Exploration

  • Prior conservative exploration work studies bandits and tabular MDPs, but the cited approaches impose cumulative rather than episode-wise conservative constraints.The paper says its more stringent episode-wise constraint requires different algorithms and regret analysis.Source: §2 · p. 3

Constrained MDP with Baseline Policies

  • Related constrained-MDP methods with baseline policies do not achieve the optimal regret of their unconstrained counterparts.The passage names OptPess-LP and DOPE as examples.Source: §2 · p. 3

3 Problem Formulation

The paper formulates learning in a finite episodic MDP with unknown transitions and a baseline-based safety requirement. It aims to minimize regret while maintaining the reward threshold in every episode with high probability.

3 Problem Formulation

  • The setting is an episodic MDP with finite state and action sets, horizon H, known deterministic rewards, and transitions unknown in advance.The formulation notes that results can be generalized to random and unknown rewards.Source: §3 · p. 3
  • A policy maps each state and episode step to a distribution over actions, and an episode proceeds from a fixed initial state for H steps.At each step, the agent observes the state, chooses an action, receives reward, and transitions according to the unknown kernel.Source: §3 · p. 3
  • The conservative constraint requires each episode's expected total reward to meet a threshold based on a known baseline policy, with high probability.The baseline may be suboptimal, and the algorithm need not know its expected reward.Source: §3 · p. 4
  • Unlike cumulative constraints, the per-episode requirement prevents saving safety budget in early episodes for later exploration.The paper connects the episode-level guarantee to interactions that run from beginning to end, such as a robot walking a route.Source: §3 · p. 4
  • The objective is to minimize total expected regret over K episodes subject to satisfying the conservative constraint for a given δ.The per-episode regret is defined relative to the optimal policy.Source: §3 · p. 4

4 The StepMix Algorithm

StepMix is designed to achieve optimal learning regret while satisfying an episode-wise conservative constraint. It uses Bernstein-based estimates and candidate policies to select exploration that remains safe with high probability.

4.1 Challenges

  • Bernstein-based confidence bounds challenge conventional safe-policy optimization because tighter value-function confidence sets no longer yield a linear program.StepMix also must keep a fixed anchor close to a history-dependent exploration policy and construct a pessimistic value estimate for that policy.Source: §4.1 · p. 5

4.2 Algorithm Design

  • StepMix builds optimistic estimates with asymmetric Bernstein bonuses, enabling lower confidence bounds for both the optimal value and exploration-policy values.The passage identifies this asymmetry as critical to obtaining a valid lower confidence bound for exploration policies.Source: §4.2 · pp. 6–7
  • Candidate policies switch from the safe baseline to the optimistic policy at different steps, and StepMix mixes neighboring candidates when selecting safe exploration.If no candidate's lower confidence bound clears the threshold, it uses the baseline; if the optimistic policy is safe, it executes that policy.Source: §4.2 · p. 7

4.3 Theoretical Analysis

  • StepMix achieves near-optimal regret, ˜O(H^3SAK), with zero constraint violation with high probability; conservatism adds only an additive regret term.The additive term is ˜O(H^3SA∆0(1/κ^2 + S/κ)); when γ = 0, it becomes zero.Source: §4.3 · pp. 7–8

5 The EpsMix Algorithm

EpsMix uses randomization at the start of each episode to mix the optimistic policy with the baseline. It has the same performance guarantees as StepMix, although an individual selected policy may fall below the threshold.

5 The EpsMix Algorithm

  • Unlike StepMix's stepwise mixtures, EpsMix randomly chooses a policy at the episode's start and plays it for the entire episode.This is the paper's episodic mixture policy.Source: §5 · p. 8
  • At each episode's start, EpsMix executes the optimistic policy if its lower confidence bound clears the threshold; otherwise it mixes that policy with the baseline.If neither policy's lower confidence bound clears the threshold, it uses the baseline to collect more information.Source: §5 · p. 8
  • EpsMix has the same performance guarantees as StepMix, while its randomized episode mixture guarantees expected total return above the threshold with probability at least 1 − δ.An individual selected policy in an episode may have expected return below the threshold.Source: §5 · p. 8

6 From Baseline Policy to Offline Dataset

When a safe baseline is not supplied, the paper learns one from an offline dataset and uses it with StepMix or EpsMix. With a sufficiently large dataset, StepMix retains its conservative guarantee and regret order despite baseline-learning uncertainty.

6 From Baseline Policy to Offline Dataset

  • The offline-data setting replaces a supplied safe baseline with a policy learned from trajectories collected under an unknown behavior policy.The learned policy is then used as input to StepMix or EpsMix.Source: §6 · p. 9
  • Learning the baseline introduces safety uncertainty, but a sufficiently large offline dataset keeps that uncertainty from changing StepMix's constraint guarantee or regret order.The dataset also reduces safety uncertainty and ensures the regret bound is dominated by the number of online episodes K.Source: §6 · p. 9
  • With n = ˜Θ(H^5SA/κ̄^2) offline trajectories, StepMix using an offline-learned baseline can satisfy the conservative constraint and achieve a regret bound with probability at least 1 − δ.The theorem specifies an offline VI-LCB baseline; a similar EpsMix result is reported, and the conclusion extends to offline methods that produce an approximately safe policy with high probability.Source: §6 · p. 9

7 Experimental Results

In the synthetic experiments, StepMix and EpsMix preserve the conservative constraint while learning, and their exploration is more effective than the compared alternatives. Learning a baseline from offline data does not significantly affect their performance in the tested setting.

7.1 Performance Evaluation of StepMix and EpsMix

  • The first experiment uses a randomly generated tabular MDP with 5 states, 5 actions, and episode length 3, and a Boltzmann baseline whose larger η gives a more deterministic, higher-value policy.Source: §7.1 · p. 9
  • StepMix and EpsMix converge to the optimal policy without constraint violations, with EpsMix converging slightly faster; BPI-UCBVI violates constraints in earlier episodes.The comparison varies the conservative constraint γ and baseline parameter η.Source: §7.1 · pp. 9–10, Figure 1 · p. 10
  • Increasing γ makes StepMix and EpsMix more conservative and delays convergence, while a better baseline improves learning performance throughout.Source: §7.1 · p. 10
  • With offline data, StepMix and EpsMix perform similarly to the supplied-baseline setting; more trajectories yield a better starting baseline and faster convergence.The experiments use 5,000 and 8,000 offline trajectories and set γ to 2.2.Source: §7.1 · p. 10, Figure 2 · p. 10

7.2 Empirical Comparison with DOPE and OptPess-LP

  • DOPE explores before StepMix and EpsMix but incurs much higher regret, while OptPess-LP stays on the baseline and its regret grows linearly.All four algorithms have zero constraint violations throughout the learning horizon.Source: §7.2 · pp. 10–11, Figure 3 · p. 11

8 Conclusions

The paper studies conservative exploration under a stringent episode-wise constraint and proposes two model-based algorithms with near-optimal regret and high-probability constraint guarantees. It also extends the analysis to baselines learned from sufficiently large offline datasets.

8 Conclusions

  • StepMix and EpsMix achieve near-optimal regret order while never violating the conservative constraint during learning; sufficiently large offline datasets preserve these guarantees when the baseline must be learned.Source: §8 · p. 11

A Related Works

  • The related works distinguish this episode-wise constraint from prior cumulative conservative constraints, and note that OptPess-LP and DOPE do not attain unconstrained-optimal regret.The paper attributes the latter limitation to their linear-programming-based approaches.Source: A Related Works · p. 15

B Notations

  • The notations define core MDP quantities and provide symbols for occupancy measures, value functions, and upper and lower confidence bounds.Source: B Notations · pp. 16–17

C Algorithm Design and Analysis of StepMix

StepMix constructs and evaluates candidate policies before selecting a safe exploration policy. Its analysis connects confidence bounds and regret arguments to the final regret guarantee.

C Algorithm Design and Analysis of StepMix

C.1 Step One: Good Events and Basic Properties of Step Mixture Policies

This appendix section establishes high-probability good events and basic properties of StepMix mixture policies, including confidence-bound and estimation-error guarantees and a bound on episodes using non-optimistic policies.

C.1 Step One: Good Events and Basic Properties of Step Mixture Policies

  • Under Algorithm 1, the defined good events occur simultaneously with probability at least 1−δ.The proof combines the individual event guarantees by a union bound.Source: §C.1 · p. 19
  • Mixing two policies that differ at only one step makes both their occupancy measures and value functions linear combinations of the corresponding policies’ quantities.The occupancy measure is defined as d_h(s, a) = Eπ[1{sh = s, ah = a}].Source: §C.1 · pp. 19–20

C.2 Step Two: Confidence Bounds

  • The constructed UCBs and LCBs bound the true value functions, and a further lemma quantifies estimation error induced by the lower bound.The confidence-bound result covers the step-wise optimistic policies and the step mixture policies.Source: §C.2 · pp. 20, 21, 23

C.3 Step Three: Finite Episodes for Step Mixture Policies

  • StepMix has only finitely many episodes in which its executed policy differs from the optimistic policy, with the cardinality of those episodes upper-bounded by Lemma C.9.The set is N = {k | k ∈ [K], πk ≠ πk,0}.Source: §C.3 · pp. 25, 27, 28
  • The proof concludes by rearranging terms, then states that the proof is complete.Source: §C.3 · p. 28

C.4 Step Four: Putting Everything Together

StepMix’s final analysis establishes an episode-wise conservative guarantee alongside a regret bound, including a special case where an additive term vanishes. The section then introduces EpsMix’s episodic mixture of the optimistic policy and the baseline.

C.4 Step Four: Putting Everything Together

  • With probability at least 1 − δ, StepMix satisfies the conservative constraint in every episode and achieves the regret upper bound stated in Theorem C.10.The theorem specifies the confidence parameters and regret expression.Source: §C.4 · pp. 28–29
  • When γ = 0, StepMix still satisfies the conservative constraint, and the additive term in its regret bound can be dropped.The section identifies this as the vanishing additive-term case.Source: §C.4 · p. 29

D.1 Algorithm Design

  • EpsMix selects an episodic policy that mixes the optimistic policy with the baseline policy using probability ρ.The algorithm executes the selected policy and collects data for subsequent updates.Source: §D.1 · p. 30

D.2 Theoretical Analysis

EpsMix is analyzed for both conservative safety and regret, with the proof linking its mixture-policy design to bounded performance degradation. The section also points to the offline VI-LCB algorithm used to construct a policy from offline data.

D.2 Theoretical Analysis

  • With probability at least 1 − δ, EpsMix satisfies the conservative constraint and achieves the total-regret upper bound in Theorem D.1.The theorem presents both guarantees simultaneously.Source: §D.2 · p. 31
  • The proof bounds episodes using the baseline or mixture policy, while lower confidence bounds ensure the conservative constraint holds in each episode.It first establishes upper and lower confidence bounds for baseline and optimal-policy values.Source: §D.2 · p. 31
  • EpsMix preserves linearity of occupancy measures and value functions under its episodic mixture, despite using a different mixture construction from StepMix.This property supports the theoretical analysis of EpsMix’s mixture policies.Source: §D.2 · p. 33

E.1 Offline Algorithm

  • The section identifies offline VI-LCB as the algorithm detailed in Algorithm 5.The supplied passage names the algorithm but gives no further design detail here.Source: §E.1 · p. 35

E.2 Theoretical Analysis

The offline analysis uses VI-LCB to extract a policy from trajectories collected under a safe behavior policy, then uses it as the baseline for conservative exploration. Under the stated data condition, both StepMix and EpsMix retain conservative guarantees and regret bounds.

E.2 Theoretical Analysis

  • Offline VI-LCB forms a lower confidence bound by subtracting an offline estimation bonus, then outputs a policy for use as the baseline.Its analysis bounds the extracted policy’s value difference from the behavior policy.Source: §E.2 · pp. 36–37
  • With the required offline trajectories from a safe behavior policy, StepMix and EpsMix satisfy the conservative constraint with high probability and achieve regret bounds.The StepMix result gives an overall probability of at least 1 − δ; the EpsMix result states a similar guarantee.Source: §E.2 · p. 38

F Technical Lemmas

  • Appendix F collects technical lemmas used in the main proof.The listed results include concentration and value-function lemmas.Source: F Technical Lemmas · pp. 38–40
Loading 2306.06265v1…