Provably Efficient Exploration in Policy Optimization

By Qi Cai, Zhuoran Yang, Chi Jin, Zhaoran Wang. International Conference on Machine Learning, 2019

306 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/d0cf6bc0d44e2af3135d238a54c58dcd5c2d4e84

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms (2021, background): “A recent line of work studies RL with linear function approximation (see, e.g., Jin et al., 2020; Wang et al., 2019; Cai et al., 2019; Zanette et al., 2020a;b; Agarwal et al., 2020; Neu and Pike-Burke, 2020; Sun et al., 2019) These papers assume certain completeness conditions, as well as the optima”
Bellman-consistent Pessimism for Offline Reinforcement Learning (2021, methodology): “We define the value-function class Note that, when the feature mapping ϕ ( · , · ) is the one induced by the linear MDP [Jin et al., 2020], it automatically ensures that F Φ satisfies Assumptions 3.”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, methodology): “…using linear function approximators (Abbasi-Yadkori et al., 2019a,b; Jin et al., 2019; Yang and Wang, 2019a; Zanette et al., 2019; Du et al., 2019b; Cai et al., 2019; Wang et al., 2019), as well as nonlinear ones (Wen and Van Roy, 2017; Jiang et al., 2017; Dann et al., 2018; Du et al., 2019b;…”
Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, background): “…focused on the online setting [Azar et al., 2017, Jin et al., 2018, Zanette and Brunskill, 2019, Simchowitz and Jamieson, 2019, Efroni et al., 2019, Cai et al., 2019] or the generative model (simulator) setting [Azar et al., 2013, Sidford et al., 2018a,b, Yang and Wang, 2019, Agarwal et al., 2020,…”
On Reward-Free Reinforcement Learning with Linear Function Approximation (2020, methodology): “Recently, in the standard RL setting, many works [Yang and Wang, 2019, Jin et al., 2019, Cai et al., 2020, Zanette et al., 2019] have provided polynomial sample complexity guarantees for diﬀerent algorithms in linear MDPs. Technically, our algorithm, which works in the reward-free setting, combines…”
FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs (2020, background): “Turning to reinforcement learning with function approximation and exploration, a large body of effort focuses on (essentially) linear methods (Yang and Wang, 2019b; Jin et al., 2019; Cai et al., 2019; Modi et al., 2020; Du et al., 2019c; Wang et al., 2019).”
Is Pessimism Provably Efficient for Offline RL? (2020, background): “…for promoting exploration in online RL (Jaksch et al., 2010; Abbasi-Yadkori et al., 2011; Russo and Van Roy, 2013; Osband and Van Roy, 2014; Chowdhury and Gopalan, 2017; Azar et al., 2017; Jin et al., 2018; 2020; Cai et al., 2020; Yang et al., 2020b; Ayoub et al., 2020; Wang et al., 2020b).”
Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint (2023, methodology): “The analysis techniques are most similar to the policy gradient literature since they also consider the soft-max policies (Agarwal et al., 2021; Cai et al., 2020; Zanette et al., 2021b; Zhong & Zhang, 2023).”
Sample-Efficient Reinforcement Learning for POMDPs with Linear Function Approximations (2022, methodology): “In the contexture of RL with function approximations, our work is also related to a vast body of recent progress (Yang and Wang, 2020; Jin et al., 2020b; Cai et al., 2020; Du et al., 2021; Kakade et al., 2020; Agarwal et al., 2020; Zhou et al., 2021; Ayoub et al., 2020) on the sample efficiency of R”
Provably efficient representation selection in Low-rank Markov Decision Processes: from online to offline RL (2021, methodology): “Similarly to its online counterpart, we start with a coverage assumption for offline RL, which suggests that the representation function class Φ can provide a good representation for all possible state-action pairs in the offline training data.”
Reward-Free Exploration for Reinforcement Learning (2020, background): “The convergence of NPG is well studied in Agarwal et al. [2019] (tabluar & inﬁnite horizon) and Cai et al. [2019] (linear approximation).”
Efficient Learning in Non-Stationary Linear Markov Decision Processes (2020, background): “In the full-information setting, Cai et al. (2019) propose an optimistic policy optimization algo-rithm that achieves O ( dH 2 K 1 / 2 ) providing that the transition kernel has a linear structure P h ( s ′ | s, a ) = ψ ( s, a, s ′ ) ⊤ θ h . e In the bandit feedback setting, Neu and Olkhovskaya…”