Provably Efficient Reinforcement Learning with Linear Function Approximation

By Chi Jin, Zhuoran Yang, Zhaoran Wang, Michael I. Jordan. Annual Conference Computational Learning Theory, 2019

700 citations recorded by the source corpus.

Modern reinforcement learning (RL) is commonly applied to practical problems with an enormous number of states, where function approximation must be deployed to approximate either the value function or the policy. The introduction of function approximation raises a fundamental set of challenges involving computational and statistical efficiency, especially given the need to manage the exploration/exploitation trade-off. As a result, a core RL question remains open: how can we design provably efficient RL algorithms that incorporate function approximation? This question persists even in a basic setting with linear dynamics and linear rewards, for which only linear function approximation is needed. This paper presents the first provable RL algorithm with both polynomial run time and polynomial sample complexity in this linear setting, without requiring a “simulator” or additional assumptions. Concretely, we prove that an optimistic modification of least-squares value iteration—a classical algorithm frequently studied in the linear setting—achieves [Formula: see text] regret, where d is the ambient dimension of feature space, H is the length of each episode, and T is the total number of steps. Importantly, such regret is independent of the number of states and actions. Funding: This work was supported by the Defense Advanced Research Projects Agency program on Lifelong Learning Machines.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research

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

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 Computational Theory and Mathematics

In Management Science and Operations Research

Citations in the corpus

Sample-Efficient Reinforcement Learning for POMDPs with Linear Function Approximations (2022, methodology): “In contrast, similar results for POMDPs are established only when the observation and latent state spaces are ﬁnite (Jin et al., 2020a).”
Representation Learning for Online and Offline RL in Low-rank MDPs (2021, methodology): “The representation φ in a low-rank MDP not only linearizes the optimal state-action value function of the MDP (Jin et al., 2020a), but also linearizes the transition operator.”
FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs (2020, methodology): “This can be solved efficiently with access to the sampling oracle, essentially by running the algorithm of Jin et al. (2019) (See Lemma 6 in the appendix).”
Reinforcement Learning: Theory and Algorithms (2019, methodology): “This chapter follows largely follows the model and analysis first provided in [Jin et al., 2020].”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, methodology): “Our linear Markov game model generalizes the MDP model considered in these papers, and our OMNI-VI algorithm can be viewed as a generalization of the optimistic LSVI method proposed in (Jin et al., 2019).”
Efficient Learning in Non-Stationary Linear Markov Decision Processes (2020, methodology): “When we go from a bandit setting to MDPs, the work of Jin et al. (2020) in the stationary case and our work in the non-stationary case incur an extra d factor and d respectively. Zanette et al. (2020b) achieve a linear dependence on d in the stationary case but their proposed algorithm is computatio”
A Review of Safe Reinforcement Learning: Methods, Theories, and Applications (2024, unknown): “ApartfromLyapunovfunctionsandMPC-safeRLap-proaches,controlbarrierfunctions(CBFs)basedapproaches arealsoproposedtoensurelearningsafety[33],[127],[128], [129].”
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? (2020, unknown): “…2017, Krishnamurthy et al., 2016, Jiang et al., 2017, Dann et al., 2018, Du et al., 2019b, Feng et al., 2020, Du et al., 2019c, Zhong et al., 2019, Yang and Wang, 2019, Jin et al., 2019, Du et al., 2019a, Roy and Dong, 2019, Lattimore and Szepesvari, 2019, Du et al., 2020, Zanette et al., 2020].”
Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms (2021, background): “To begin with, Jiang et al. [1] introduces a generic complexity notion—Bellman rank, which can be proved small for many RL problems including linear MDPs [7], reactive POMDPs [16], etc. [1] further propose an hypothesis elimination-based algorithm— OLIVE for sample-efficient learning of problems wit”
On Reward-Free Reinforcement Learning with Linear Function Approximation (2020, methodology): “Jin et al. [2020] showed that in the tabular setting, the agent only needs to collect polynomial number of samples (in terms of the number states, the number of actions, and the planning horizon) for reward-free RL.”
Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation (2021, background): “provable RL algorithms with linear function approximation, linear MDPs [10] is probably the most widely assumed MDP model, where both the transition kernel and the reward function are linear functions of a given feature mapping.”
Provably Efficient Exploration in Policy Optimization (2019, methodology): “In particular, compared with optimistic LSVI (Jin et al., 2019), OPPO attains the same regret even in the presence of adversarially chosen reward functions.”
Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning? (2019, background): “Recently, Yang & Wang (2019b) proposed the linear transition assumption which was later studied in Yang & Wang (2019a); Jin et al. (2019). Again, we assume the agent is given a feature extractor φ : S ×A → R, and now we state the assumption formally as follow.”