Contextual Decision Processes with low Bellman rank are PAC-Learnable

By Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, J. Langford, Robert E. Schapire. 2016

462 citations recorded by the source corpus.

This paper studies systematic exploration for reinforcement learning (RL) with rich observations and function approximation. We introduce contextual decision processes (CDPs), that unify most prior RL settings. Our first contribution is a complexity measure, the Bellman rank, that we show enables tractable learning of near-optimal behavior in CDPs and is naturally small for many well-studied RL models. Our second contribution is a new RL algorithm that does systematic exploration to learn near-optimal behavior in CDPs with low Bellman rank. The algorithm requires a number of samples that is polynomial in all relevant parameters but independent of the number of unique contexts. Our approach uses Bellman error minimization with optimistic exploration and provides new insights into efficient exploration for RL with function approximation.

Subfields: Artificial Intelligence, Control and Systems Engineering, Reinforcement Learning, Statistical Learning Theory

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 Control and Systems Engineering

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Search (2019, methodology): “ error { so there is no explicit need to maintain a state and transition function, and this approach may require evaluating a larger number of architectues to achieve the same result as other methods [17, 6, 14]. Alternatively, Bayesian optimization with a Gaussian process model is a leading method ”
Neural Architecture Search with Bayesian Optimisation and Optimal Transport (2018, background): “Since RL is a fundamentally more difficult problem than optimisation [16], these approaches need to try a very large number of architectures to find the optimum.”
Information-Theoretic Considerations in Batch Reinforcement Learning (2019, methodology): “Let M be a reactive POMDP as deﬁned in Jiang et al. (2017), where the underlying hidden state space Z is ﬁnite but the (Markov) observation space S can be arbitrarily large.”
A Study on Overfitting in Deep Reinforcement Learning (2018, background): “…and adversarial bandits (Auer, 2000; Bubeck & Cesa-Bianchi, 2012), for contextual bandits (Agarwal et al., 2014), contextual decision processes (Jiang et al., 2017) and RL (Jaksch et al., 2010; Azar et al., 2017), as well as Probably Approximately Correct (PAC) (Strehl et al., 2009; Lattimore…”
Efficient Exploration Through Bayesian Deep Q-Networks (2018, background): “ion theoretic lower bound. We also plan to extend the analysis in Abeille and Lazaric (2017) and develop Thompson sampling methods with a performance guarantee and ﬁnally go beyond the linear models (Jiang et al., 2016). While ﬁnding optimal continuous action given a Q function can be computationall”
Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning (2017, neutral): “PAC: [2, 3, 4, 5], (uniform) high-probability regret: [6, 7, 8]; expected regret: [9, 10, 11, 12]).”
On Oracle-Efficient PAC RL with Rich Observations (2018, methodology): “Working toward this goal, we study the computational aspects of the OLIVE algorithm [1], which applies to a wide range of environments.”
Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle (2019, methodology): “This is a widely used assumption in the theoretical reinforcement learning literature [17].”
Offline Meta Reinforcement Learning (2020, unknown): “Related to this approach are contextual-MDPs [20, 23].”
On the Sample Complexity of the Linear Quadratic Regulator (2017, background): “[31] propose a general exploration algorithm for contextual decision processes (CDPs) and show that CDPs with low Bellman rank are PAC-learnable; in the LQR setting, they show the Bellman rank is bounded by n2.”
Provably Efficient Exploration in Policy Optimization (2019, background): “, 2020), as well as nonlinear settings involving general function approximators (Wen & Van Roy, 2017; Jiang et al., 2017; Du et al., 2019b; Dong et al., 2019).”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, background): “, 2019), as well as nonlinear ones (Wen and Van Roy, 2017; Jiang et al., 2017; Dann et al., 2018; Du et al., 2019b; Dong et al., 2019; Du et al., 2019a).”
On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift (2019, background): “As such, they permit a number of special cases to have statistical and iteration complexities which are independent of the size of the state space; we give one such example later on, with regards to the linear MDP model of Jin et al. [2019], Yang and Wang [2019], Jiang et al.”
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? (2020, background): “…for Q -functions, etc, the sample complexity does not depend on |S| [Li et al., 2011, Wen and Van Roy, 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.,…”
Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, background): “(2017)) assumes Pt ≡ P is identical at different time steps, and the non-stationary transition setting (Jiang et al., 2017; Xie et al., 2019) allows Pt to be different for”
Sample-Optimal Parametric Q-Learning Using Linearly Additive Features (2019, methodology): “This idea originates from the phased Q-learning Kearns and Singh [1999] and the fitted value iteration Munos and Szepesvári [2008], Antos et al.”
Representation Learning for Online and Offline RL in Low-rank MDPs (2021, methodology): “Following prior work (Jiang et al., 2017; Sun et al., 2019), we assume trajectory reward is normalized, i.”
Reinforcement Learning: Theory and Algorithms (2019, methodology): “The original definition in Jiang et al. [2017] allows non-Markovian contexts as well, but we omit this generalization for ease of presentation.”
Provably efficient RL with Rich Observations via Latent State Decoding (2019, background): “The recent line of work on contextual decision processes (Kr-ishnamurthy et al., 2016; Jiang et al., 2017; Dann et al., 2018) identiﬁed certain low-rank structures that enable exploration algorithms with sample complexity polynomial in the rank parameter.”