Provably Efficient Exploration in Policy Optimization

Qi Cai; Zhuoran Yang; Chi Jin; Zhaoran Wang

Source-linked AI summary

Provably Efficient Exploration in Policy Optimization

Qi Cai, Zhuoran Yang, Chi Jin, Zhaoran Wang

arXiv:1912.05830v4Dec 12, 2019cs.LGmath.OCstat.ML

TL;DR

Policy optimization lacks a provably efficient way to explore without assuming prior coverage or simulator access. The paper proposes OPPO, an optimistic PPO variant for linear episodic MDPs with unknown transitions and adversarial rewards, and proves Õ(√(d^2 H^3 T)) regret up to logarithmic factors. The authors state that OPPO is the first provably efficient policy optimization algorithm that explicitly incorporates exploration.

Problem
Policy optimization remains theoretically limited in settings where exploration must be learned online rather than assumed through a simulator or state-space coverage condition.
Method
OPPO uses an optimistic policy-gradient direction by adding an uncertainty bonus to the action-value function within a PPO-style policy optimization update.
Results
Õ(√(d^2 H^3 T)) regret up to logarithmic factors is achieved in episodic MDPs with linear transitions, unknown dynamics, full-information feedback, and adversarial rewards.
Takeaways & Limitations
OPPO provides a provably sample-efficient exploratory policy optimization method without transition knowledge or simulator access.
Takeaways & Limitations
The guarantees are established for episodic MDPs with linear transition dynamics and full-information feedback.

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

Policy optimization has strong computational results but lacks comparable statistical guarantees when exploration must be learned online. The paper introduces OPPO, an optimistic PPO variant that adds uncertainty bonuses and achieves provable regret in linear episodic MDPs.

Motivation: Existing policy optimization methods can converge efficiently, but their guarantees assume the state space is already well explored or that a simulator or concentrability condition is available.These assumptions are often unavailable in practice, leaving exploration and sample efficiency insufficiently understood.
Motivation: Policy optimization faces unresolved statistical challenges because exploration must balance information gathering against actions with higher expected total rewards.The paper frames this as a regret or sample-complexity question, beyond the computational question of convergence.
OPPO: OPPO is an optimistic variant of PPO that incorporates exploration by augmenting the action-value function with an uncertainty bonus.The bonus quantifies uncertainty from finite historical data and promotes conservative optimism in the updated policy.
OPPO: OPPO performs KL-regularized policy optimization, corresponding to an infinite-dimensional mirror-descent or dual-averaging step whose gradient is the action-value function.The bonus is added to the action-value function, preserving the connection to NPG, TRPO, and PPO while remaining implementable.
Guarantees: The same regret guarantee holds against adversarially chosen rewards while competing with the globally optimal policy in hindsight, making OPPO the first provably efficient exploratory policy optimization algorithm to the authors’ knowledge.The paper positions this result as combining computational and sample efficiency in the linear setting.

2 Preliminaries

The paper studies episodic MDPs with unknown transitions, potentially adversarial rewards, and linear transition dynamics represented by a known feature map. Regret is measured against the globally optimal policy in hindsight over T=HK steps.

The environment is an episodic MDP with state space S, action space A, horizon H, transition kernels P_h, and reward functions r_h.
Rewards are deterministic and may be chosen adversarially at the beginning of each episode based on previous trajectories.The analysis also extends to stochastic reward functions.
The agent selects a policy at each episode’s beginning, interacts for H steps, observes rewards after acting, and accumulates T=HK total steps.
Regret compares the agent with the globally optimal policy in hindsight under the sequence of episode-specific reward functions.
The transition dynamics are linear in a known feature map ψ:S×A×S→R^d, with bounded unknown parameter vectors θ_h.
Tabular MDPs are included as a special case using the canonical basis, while this linear-MDP definition differs from another feature-map formulation in prior work.

3 Algorithm and Theory

OPPO combines KL-regularized policy improvement with bonus-based least-squares policy evaluation. Its optimism supports regret guarantees for linear MDPs with adversarial rewards, including a tabular specialization.

Algorithm and Theory: OPPO updates each policy using a KL-regularized improvement step based on the previous policy and an estimated Q-function.The KL term keeps the new policy close to π^{k−1}, while the Q-function acts as the policy-gradient direction.
Algorithm and Theory: The policy evaluation step applies least-squares temporal difference estimation to historical trajectories and adds a bonus quantifying uncertainty.
Algorithm and Theory: The estimated Q-function is an upper confidence bound with high probability, making the policy evaluation optimistic uniformly over episodes, steps, states, and actions.
Algorithm and Theory: Theorem 3.1 gives OPPO d^2H^3T-regret up to logarithmic factors, with optimal dependence on the total number of steps T.
Algorithm and Theory: In the stationary setting, the regret yields d^2H^4/ε^2 sample complexity up to logarithmic factors.
Algorithm and Theory: OPPO accommodates adversarially chosen rewards without worsening the regret guarantee, providing a notion of robustness.
Algorithm and Theory: In the linear setting, OPPO attains the lower bound in terms of T, while conservative greediness suffices for sample efficiency in the stationary setting.

4 Proof Sketch

The proof decomposes regret into policy-improvement, martingale, and model-prediction-error terms. Optimistic confidence bounds control the model error, while concentration and elliptical-potential arguments bound the remaining contributions.

4 Proof Sketch: The model prediction error arises from estimating transition dynamics using finite historical data.
4 Proof Sketch: The regret decomposition contains three terms: policy-improvement error, a martingale contribution, and model prediction error.
4 Proof Sketch: The martingale term is controlled by Azuma-Hoeffding concentration over T_M=2T timesteps with difference bound B_M=2H.
4 Proof Sketch: The regret decomposition itself is independent of the linear-MDP assumption and can extend beyond linear settings when the prediction-error term is bounded.
4 Proof Sketch: Lemma 4.3 establishes that the bonus makes the estimated Q-function optimistic with high probability, including for less-visited or unseen state-action pairs.
4 Proof Sketch: The remaining cumulative prediction-error contribution is bounded using an elliptical-potential lemma.
4 Proof Sketch: The transition-estimation error enters regret only through the model prediction error, allowing OPPO to avoid explicitly estimating transition dynamics.

5 Conclusion

The paper studies sample efficiency for policy-based reinforcement learning in episodic linear MDPs with full-information feedback. It introduces OPPO, an optimistic PPO variant, and reports a near-optimal regret guarantee while identifying it as the first provably efficient policy optimization algorithm that explicitly explores.

The paper studies sample efficiency of policy-based reinforcement learning in episodic linear MDPs with full-information feedback.
OPPO is an optimistic variant of proximal policy optimization that incorporates optimism in the face of uncertainty into policy optimization.
√d^2H^3T-regret up to logarithmic factors is achieved for episodic MDPs with unknown transitions and adversarial rewards.
The paper describes OPPO's regret guarantee as near-optimal.
OPPO is identified as the first provably efficient policy optimization algorithm that explicitly incorporates exploration.

A.1 Proof of Lemma 3.2

This proof section defines Bellman evaluation under a policy and uses the value-function definition and operator linearity to establish Lemma 3.2.

The Bellman evaluation operator averages immediate reward and next-state value under a policy and transition kernel.
The proof invokes the value-function definition with the zero function as a boundary condition.
For two policies, the argument compares compositions of Bellman evaluation operators.
Linearity of the Bellman evaluation operator, together with equations (A.3)–(A.5), yields the displayed result.
The resulting identity concludes the proof of Lemma 3.2.

A.2 Proof of Lemma 3.3

This proof develops a distributional inequality using inner-product decomposition and Pinsker's inequality, then concludes Lemma 3.3.

The argument begins with an inequality for a function and three action distributions satisfying the stated conditions.
The proof uses the simplex constraint to show that the inner product with z vanishes.
The relevant policy difference is decomposed into a reference-distribution term and a correction term.
Pinsker's inequality is applied to relate the distributional terms before bounding them using the uniform bound on Q.
The combined inequalities establish Lemma 3.3.

B.1 Proof of Lemma 4.2

This proof decomposes episode regret, propagates model-prediction terms across the horizon, and controls resulting stochastic quantities with martingale arguments.

The instantaneous regret at episode k is decomposed into two terms.
The transition definitions and operator definitions are combined to obtain intermediate equalities for the regret analysis.
The proof uses estimated value functions, operators J_h and J_k,h, and model prediction error terms.
A recursive expansion across h ∈ [H] propagates the decomposition through the episode horizon.
The proof defines filtration-adapted martingale terms from variables with conditional mean zero.
Combining the intermediate bounds and martingale relation concludes Lemma 4.2.

B.2 Proof of Lemma 4.3

The proof of Lemma 4.3 bounds model-prediction and policy-evaluation errors under a high-probability event, combining intermediate inequalities with the assumed parameter bounds.

The bounds apply uniformly over episodes, steps, states, and actions under event E, which occurs with probability at least 1 −ζ/2.
Cauchy-Schwarz, the structure of Λk, and Assumption 2.1 provide the inequalities needed to control the error terms.
Combining the intermediate bounds and setting λ = 1 completes the proof of Lemma 4.3.
The proof bounds terms arising in the model-prediction error using the definitions of the estimated Q-function and policy-evaluation quantities.

C Proof of Theorem 3.1

The proof of Theorem 3.1 decomposes regret into three terms and controls them using policy improvement, martingale concentration, and the model-prediction bound.

The regret decomposition separates the analysis into terms (i)–(iii), which are bounded individually before being recombined.
Policy improvement and Lemma 3.3 control term (i), while the initialized policy is uniform over actions.
Azuma-Hoeffding concentration controls martingale term (ii) after truncating Qk_h so the differences satisfy |Dk,h,1| ≤2H and |Dk,h,2| ≤2H.
The model-prediction bound controls term (iii) with probability at least 1 −ζ/2.
With probability at least 1 −ζ, combining the three bounds yields the theorem’s regret inequality, using log |A| = O(d^2 · [log(dT/ζ)]^2).

D Supporting Lemmas

This section supplies concentration and elliptical-potential lemmas, then specializes the linear-MDP framework and OPPO guarantees to tabular MDPs.

Supporting lemmas: Lemma D.1 establishes a high-probability event used to control the policy-evaluation analysis.
Supporting lemmas: Lemma D.2 provides concentration for conditionally zero-mean, σ-sub-Gaussian noise in a self-normalized process.
Supporting lemmas: Lemma D.3 bounds cumulative feature-dependent uncertainty through the elliptical potential of positive-definite covariance matrices.
Tabular specialization: A tabular MDP is a special case of the linear MDP with d = |S|^2|A|, using canonical-basis features and transition parameters θh = Ph(· | ·, ·).
Tabular specialization: In the tabular setting, OPPO uses least-squares policy evaluation and exponential policy updates, with parameters λ = 1 and β selected according to the stated confidence bound.
Tabular specialization: Corollary E.1 applies Theorem 3.1 to obtain a tabular regret guarantee with probability at least 1 −ζ.

E.1 A Variant of OPPO for the Tabular Setting

The tabular OPPO variant estimates transitions from counts, adds a count-based optimism bonus, and performs optimistic dynamic programming alongside policy updates.

The optimism property requires the model estimate and cumulative bonus to satisfy the stated upper-confidence conditions.
The algorithm estimates each transition kernel using observed state-action-transition counts with regularization parameter λ > 0.
Its bonus function is count-based and is used with optimistic dynamic programming for policy evaluation.
Algorithm 2 alternates policy updates, trajectory interaction, reward observation, transition observation, and backward value-function computation.
Lemma E.3 establishes an upper-confidence bound for the tabular model-prediction error uniformly over steps, episodes, states, and actions.