PaperlayerView exact revision on arXiv

Source-linked AI summary

Provably Efficient Exploration in Policy Optimization

Qi Cai, Zhuoran Yang, Chi Jin, Zhaoran Wang

arXiv:1912.05830v4cs.LGmath.OCstat.ML

TL;DR

Policy optimization remains theoretically less understood, and designing an exploration-capable algorithm with provable efficiency remains elusive. This paper proposes OPPO, an optimistic variant of PPO, and proves a regret bound of ~O(sqrt(d^2 H^3 T)) for episodic MDPs with linear function approximation, unknown transitions, and adversarial rewards with full-information feedback.

  • Problem

    Theoretical understanding of policy optimization remains limited.

    Source: §1 · p. 2

  • Method

    The paper develops OPPO, an optimistic PPO variant that incorporates exploration in a principled manner.

    Source: §1 · p. 3

  • Results

    ~O(sqrt(d^2 H^3 T)) regret up to logarithmic factors is achieved by OPPO for episodic MDPs with unknown transitions and adversarial rewards.

    Source: §5 · p. 22

  • Takeaways & Limitations

    OPPO is the first provably efficient policy optimization algorithm that explicitly incorporates exploration.

    Source: §5 · p. 22

    The guarantee is scoped to MDPs with full-information feedback.

    Source: §1 · p. 3

Abstract

from arXiv · show

While policy-based reinforcement learning (RL) achieves tremendous successes in practice, it is significantly less understood in theory, especially compared with value-based RL. In particular, it remains elusive how to design a provably efficient policy optimization algorithm that incorporates exploration. To bridge such a gap, this paper proposes an Optimistic variant of the Proximal Policy Optimization algorithm (OPPO), which follows an ``optimistic version'' of the policy gradient direction. This paper proves that, in the problem of episodic Markov decision process with linear function approximation, unknown transition, and adversarial reward with full-information feedback, OPPO achieves $\tilde{O}(\sqrt{d^2 H^3 T} )$ regret. Here $d$ is the feature dimension, $H$ is the episode horizon, and $T$ is the total number of steps. To the best of our knowledge, OPPO is the first provably efficient policy optimization algorithm that explores.

1 Introduction

This section introduces OPPO, an optimistic policy-optimization method that applies optimism to policy-gradient algorithms to address sample-efficient exploration in linear episodic MDPs, and situates it among value-based and earlier policy-gradient approaches.

1 Introduction

  • OPPO adds an uncertainty bonus to the action-value function in a KL-regularized policy update, promoting conservative optimism while remaining easily implementable.The update corresponds to mirror descent or dual averaging, with the action-value function playing the role of the gradient.Source: §1 · p. 3

1.1 Related Work

  • Without a simulator or finite concentratability coefficients, prior policy-optimization convergence results do not establish finite regret or sample complexity; OPPO adds exploration while retaining computational efficiency.The related work characterizes OPPO as both computationally efficient and sample-efficient.Source: §1.1 · p. 4
  • Unlike existing unknown-transition methods that follow gradients with respect to visitation measures, OPPO follows the policy gradient and is an optimistic variant of NPG, TRPO, and PPO.The passages characterize this approach as not restricted to the tabular setting and as a practical policy-optimization algorithm.Source: §1.1 · p. 6
  • In the tabular specialization, OPPO’s setting corresponds to the third setting and achieves T-regret up to logarithmic factors.Source: §1.1 · p. 6
  • OPPO attains the same performance as value-based reinforcement learning methods in the presence of adversarially chosen rewards.Source: §1.1 · p. 6
  • OPPO attains computational and sample efficiency in the linear setting, whereas OLIVE (Jiang et al., 2017) is only sample-efficient.Source: §1.1 · p. 6
  • OPPO carries optimism from value-iteration algorithms such as optimistic LSVI to policy-optimization algorithms such as NPG, TRPO, and PPO, enabling sample efficiency and conservative optimism against adversarial rewards.Source: §1.1 · p. 7

2 Preliminaries

The preliminaries define an episodic MDP with adversarially chosen rewards and describe the linear-MDP assumptions used to model its transitions.

2.1 MDPs with Adversarial Rewards

  • The episodic MDP has horizon H and stage-specific transition kernels and rewards, with rewards allowed to be chosen adversarially each episode.Source: §2.1 · pp. 7, 9
  • The agent chooses each episode’s policy based on prior trajectories, and the reward function is revealed after it takes an action.Source: §2.1 · pp. 7–8
  • Regret compares the agent with the globally optimal policy in hindsight, over T = HK total steps; its definition cites Cesa-Bianchi and Lugosi (2006) and Bubeck and Cesa-Bianchi (2012).Source: §2.1 · p. 8

2.2 Linear Function Approximations

3 Algorithm and Theory

This section presents OPPO’s KL-regularized policy-improvement and historical-data evaluation approach, then analyzes its regret guarantees. It also examines conservatively greedy updates in the stationary linear setting, including their total-step bound and the behavior of finite-step updates.

3.1 Optimistic PPO (OPPO)

  • OPPO updates each episode’s policy from the previous one, using KL regularization to keep it nearby and ensure improved expected total reward for the previous reward function.Source: §3.1 · pp. 10–11
  • At episode end, OPPO evaluates its policy using prior trajectories via one LSTD step and adds a bonus so its estimated Q-function is an upper confidence bound.Source: §3.1 · pp. 12–13

3.2 Regret Analysis

  • Under Assumption 2.1 and log|A|=O(d^2·[log(dT/ζ)]^2), OPPO guarantees d^2H^3T regret up to logarithmic factors with probability at least 1−ζ.Source: §3.2 · p. 14
  • When rewards and initial states are stationary, the regret implies d^2H^4/ε^2 sample complexity; adversarial rewards do not exacerbate regret, yielding robustness.Source: §3.2 · pp. 14–15
  • With known transitions, the analysis obtains H^3T·log|A| regret in an ideal setting and identifies KL divergence as key to this bound.Source: §3.2 · pp. 15–16
  • Without the KL divergence, setting the step size α to infinity makes the regret upper bound tend to infinity.Source: §3.2 · p. 16
  • With known (3.3), fully greedy improvement corresponds to one policy-iteration step and reaches the globally optimal policy within K = H episodes, inducing H^2 regret.Source: §3.2 · p. 17
  • OPPO attains the information-theoretic lower bound in total steps T = HK in the stationary linear setting, where conservative greediness suffices for sample-efficiency.This complements the method’s robustness in the more challenging setting with adversarially chosen rewards.Source: §3.2 · p. 17

4 Proof Sketch

The proof decomposes regret into three terms, then controls model prediction error through uncertainty bonuses that make the estimated Q-function optimistic. It also explains how this error can be analyzed without explicitly estimating transition dynamics.

4.1 Regret Decomposition

  • Lemma 4.2 splits regret into policy-improvement, martingale, and model-prediction-error terms.The martingale term is bounded using Azuma–Hoeffding; the decomposition does not depend on the linear setting.Source: §4.1 · p. 19
  • The regret decomposition applies beyond linear function approximation when its model-prediction-error term can be upper bounded.The paper states that this part of the analysis is independent of the linear-setting assumption.Source: §4.1 · pp. 19–20

4.2 Model Prediction Error

  • With λ = 1 and the bonus specified in (3.6), the estimated Q-function is optimistic with probability at least 1 − ζ/2.The bonus compensates for uncertainty from finite data, including at less-visited or unseen state-action pairs.Source: §4.2 · p. 20
  • The model prediction error reflects finite-data transition-estimation error, but the analysis bypasses explicit transition estimation by using the policy-evaluation Q-function.This error enters the regret decomposition through the model prediction error term.Source: §4.2 · p. 21

5 Conclusion · A Proofs of Lemmas in Section 3

The paper studies sample efficiency for policy-based RL in episodic linear MDPs with full-information feedback and introduces OPPO, an optimistic PPO variant that achieves near-optimal regret under unknown transitions and adversarial rewards.

5 Conclusion

  • The study considers the sample efficiency of policy-based reinforcement learning in episodic linear MDPs with full-information feedback.The conclusion identifies this as the setting studied.Source: §5 · p. 22
  • OPPO incorporates “optimism in the face of uncertainty” into policy optimization as an optimistic variant of proximal policy optimization.The algorithm is dubbed OPPO.Source: §5 · p. 22
  • OPPO achieves sqrt(d^2 H^3 T) regret up to logarithmic factors for episodic MDPs with unknown transitions and adversarial rewards.The paper describes this rate as near-optimal.Source: §5 · p. 22
  • OPPO is presented as the first provably efficient policy optimization algorithm that explicitly explores.Source: §5 · p. 22

A.1 Proof of Lemma 3.2

The proof of Lemma 3.2 uses Bellman evaluation operators to relate policy values, then combines operator identities and linearity to conclude the result.

A.1 Proof of Lemma 3.2

  • For any h and policy π, the Bellman operator applies the expected immediate reward plus next-state value under π and the transition model.Source: §A.1 · p. 30
  • Using the value-function definition and a zero terminal function, the proof develops Bellman-operator identities for policies π′ and π.Source: §A.1 · p. 30
  • Combining equations (A.3)–(A.5) with Bellman-operator linearity concludes the proof of Lemma 3.2.Source: §A.1 · p. 31

A.2 Proof of Lemma 3.3 · B Proofs of Lemmas in Section 4

The supplied proof excerpt derives Lemma 3.3 using a simplex-based inner-product equality, Pinsker’s inequality, and a bound on Q. The Section 4 proof excerpt introduces indexed operators, but does not include their formulas.

A.2 Proof of Lemma 3.3

  • The proof starts with an arbitrary function g and distributions p, p′, and p* satisfying a condition not visible in the excerpt.The passage gives their domains as g:A→R and p,p′,p*∈∆(A).Source: §A.2 · p. 31
  • From (A.6), the proof obtains ⟨z, p*−p′⟩=0 because p′ and p* belong to ∆(A).Source: §A.2 · p. 31
  • The proof rewrites α⟨Q(x,·),p*−p⟩ as the difference of its pairings with p*−p′ and p−p′.The identity is stated for the displayed Q expression; the excerpt does not give further conditions on x here.Source: §A.2 · p. 31
  • For any state x, the proof invokes Pinsker’s inequality and then combines (A.7) and (A.8) with ∥Q(x,·)∥∞≤H.Source: §A.2 · p. 32
  • The excerpt concludes the argument by stating that this combination proves Lemma 3.3.Source: §A.2 · p. 32

B Proofs of Lemmas in Section 4

  • For notational simplicity, the Section 4 proofs introduce operators Jh and Jk,h, indexed by h and by (k,h), respectively.The excerpt says these are defined for functions f:S×A→R, but omits the defining formulas.Source: B Proofs of Lemmas in Section 4 · p. 32

B.1 Proof of Lemma 4.2

The proof of Lemma 4.2 decomposes instantaneous regret at episode k and combines recursive expansions with model-prediction-error and martingale arguments.

B.1 Proof of Lemma 4.2

  • The proof begins by decomposing instantaneous regret at the k-th episode.The decomposition is the starting point for the subsequent argument.Source: §B.1 · p. 32
  • Recursive expansions across the horizon combine identities involving value functions, operators, and model prediction errors.The proof applies these expansions to intermediate relations before combining them in its final steps.Source: §B.1 · pp. 32–33
  • The proof identifies two terms as martingale differences with zero conditional means under the stated filtrations.These terms are adapted to the filtration indexed by timestep, episode, horizon step, and m.Source: §B.1 · p. 35
  • Combining the preceding relations concludes the proof of Lemma 4.2.The final step combines (B.3), (B.7), (B.12), and (B.15).Source: §B.1 · p. 35

B.2 Proof of Lemma 4.3

The proof of Lemma 4.3 bounds two terms and combines those bounds to control the model-prediction error under event E.

B.2 Proof of Lemma 4.3

  • The derivation uses the stated forms of h and the estimated Q-function, and plugs in the definition of Λk.These expressions are introduced for the specified (k, h), state, and action ranges.Source: §B.2 · p. 36
  • The proof separately bounds terms (i) and (ii), using Cauchy–Schwarz and Assumption 2.1 in the bound for term (ii).It then combines the term bounds with λ = 1.Source: §B.2 · pp. 36–37
  • Under event E, the proof combines its bounds to control the model-prediction error; E occurs with probability at least 1 − ζ/2.The argument concludes by combining (B.26) and (B.27) with Lemma D.1.Source: §B.2 · pp. 37–38

C Proof of Theorem 3.1

The proof establishes Theorem 3.1 by bounding the three terms in Lemma 4.2 and combining those bounds to obtain the stated high-probability conclusion.

C Proof of Theorem 3.1

  • Term (i) is bounded using Lemma 3.3 and the policy-improvement step, with the proof also invoking the algorithm’s initialization.The initialization makes π1_h(· | x_h) uniform over A.Source: C Proof of Theorem 3.1 · p. 39
  • For term (ii), restricting Q_k^h to [0, H − h + 1] yields |Dk,h,1| ≤ 2H and |Dk,h,2| ≤ 2H for every (k,h) ∈ [K] × [H], permitting Azuma–Hoeffding.Source: C Proof of Theorem 3.1 · p. 40
  • Term (iii) is controlled using Lemma 4.3 and the proof’s subsequent bounds, which are combined with Cauchy–Schwarz.The stated probability for the final bound is at least 1 − ζ.Source: C Proof of Theorem 3.1 · pp. 40, 42
  • Combining the bounds on terms (i)–(iii) yields the theorem’s conclusion with probability at least 1 − ζ and an absolute constant C′.The proof also uses log |A| = O(d^2 · [log(dT/ζ)]^2) in bounds (C.2) and (C.12).Source: C Proof of Theorem 3.1 · p. 42

D Supporting Lemmas · E OPPO in the Tabular Setting

Section D supplies concentration and elliptical-potential lemmas used in the analysis. Section E specializes OPPO to finite tabular MDPs and states a high-probability regret corollary for that setting.

D Supporting Lemmas

  • Lemma D.1 states that, with λ = 1, its specified event holds with probability at least 1−ζ/2 for ζ ∈ (0, 1].The event’s content is not visible in the supplied passages.Source: D Supporting Lemmas · pp. 42, 44
  • Lemma D.2 gives a self-normalized process concentration result under measurability and conditionally zero-mean, σ-sub-Gaussian noise assumptions.It states a probability-at-least-1−δ bound; the displayed inequality is not included in the supplied passages.Source: D Supporting Lemmas · p. 44
  • Lemma D.3 invokes the elliptical potential lemma for feature vectors with norm at most 1 and an initial matrix whose minimum eigenvalue is at least 1.The lemma’s displayed bound is not included in the supplied passages (Jin et al., 2019).Source: D Supporting Lemmas · pp. 44–45

E OPPO in the Tabular Setting

  • A tabular MDP with finite state and action sets is a linear MDP using canonical-basis features of dimension d = |S|^2|A|.The feature vector marks a state-action-next-state tuple, and the transition parameter records the corresponding transition probabilities.Source: E OPPO in the Tabular Setting · pp. 45–46
  • The tabular OPPO restatement specializes policy evaluation and policy updating to this finite-state representation.Its evaluation step uses least-squares regression, with a feature vector having |S| nonzero entries for each state-action pair.Source: E OPPO in the Tabular Setting · pp. 46–47
  • With probability at least 1−ζ, Corollary E.1 bounds OPPO’s regret in the tabular setting.The supplied passages do not include the bound’s expression; the corollary assumes specified algorithm parameters, including λ = 1.Source: E OPPO in the Tabular Setting · p. 47

E.1 A Variant of OPPO for the Tabular Setting

This section extends OPPO’s regret-decomposition framework to a count-based tabular variant under optimism and boundedness conditions, establishing a regret upper bound. It concludes the proof of Theorem E.2, with the result holding with probability at least 1 − ζ.

E.1 A Variant of OPPO for the Tabular Setting

  • The OPPO regret-decomposition framework extends beyond linear MDPs when optimism is ensured and the relevant quantity is bounded, permitting alternative optimistic policy-evaluation methods.Source: §E.1 · pp. 47–48
  • h(x,a) counts observations of state-action pairs, and h(x,a,x′) counts observed transitions; bP_h is defined as an estimator of P_h with h(x,a)+λ appearing in its definition.Source: §E.1 · p. 48
  • Policy evaluation uses the estimated transition kernels in an optimistic dynamic-programming procedure.Algorithm 2 presents the tabular variant.Source: §E.1 · pp. 48–49
  • Algorithm 2’s tabular OPPO variant has a regret upper bound with probability at least 1−ζ (Theorem E.2).Lemma E.3 also bounds the model prediction error under the theorem’s conditions.Source: §E.1 · pp. 49–51
  • The proof combines (E.12), (E.13), (E.14), and (E.29) to conclude Theorem E.2 with probability at least 1 − ζ and an absolute constant C′′.The supplied passages do not include the complete bound.Source: §E.1 · p. 55

Related papers

Loading 1912.05830v4…