PAC Reinforcement Learning with Rich Observations

By Akshay Krishnamurthy, Alekh Agarwal, J. Langford. 2016

172 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

Information-Theoretic Considerations in Batch Reinforcement Learning (2019, methodology): “Example in problems with rich observations We ﬁnd answers to the above problem in recent development of PAC exploration in rich-observation problems (Krishnamurthy et al., 2016; Jiang et al., 2017; Dann et al., 2018), where a general low-rank condition (a.k.a. Bellman rank (Jiang et al., 2017)) has…”
Mapping Instructions and Visual Observations to Actions with Reinforcement Learning (2017, background): “…is much tighter sample complexity bounds when comparing upper bounds for contextual bandits (Langford and Zhang, 2007) even with an adversarial sequence of contexts (Auer et al., 2002) to lower bounds (Krishnamurthy et al., 2016) or upper bounds (Kearns et al., 1999) for total reward maximization.”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, background): “This is weaker than the realizability assumption made in the value-based RL literature, that F contains the optimal Q-value function of an MDP Q (cid:63) [Antos et al., 2008, Krishnamurthy et al., 2016].”
On Oracle-Efficient PAC RL with Rich Observations (2018, methodology): “On the statistical side, recent important progress was made by showing that contextual decision processes (CDPs) with rich stochastic observations and deterministic dynamics over M hidden states can be learned with a sample complexity polynomial in M [17].”
Provably efficient RL with Rich Observations via Latent State Decoding (2019, methodology): “The BMDP model is assumed in several prior works (e.g., Krishnamurthy et al., 2016; Azizzadenesheli et al., 2016a; Dann et al., 2018), without the explicit name.”
Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, unknown): “1 (Best arm identification lower bound Krishnamurthy et al. (2016)).”
Provable Rich Observation Reinforcement Learning with Combinatorial Latent States (2021, background): “, 2017) have achieved inspiring performance on several RL benchmarks, while theoretical works (Krishnamurthy et al., 2016; Jiang et al., 2017) show that it is information-theoretically possible to explore these environments.”
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? (2020, background): “Assumption 3.2 (Bounded Total Reward e.g. Krishnamurthy et al. [2016]) .”
Reinforcement Learning in Rich-Observation MDPs using Spectral Methods (2016, methodology): “ROMDPs have been studied in [16] in the PAC-MDP setting and episodic deterministic environments using an algorithm searching the best Q -function in a given function space.”
What are the Statistical Limits of Offline RL with Linear Function Approximation? (2020, background): “Existing (information-theoretic) exponential lower bounds [Krishnamurthy et al., 2016, Sun et al., 2017, Chen and Jiang, 2019] usually construct unstructured MDPs with an exponentially large state space.”
PAC Reinforcement Learning With an Imperfect Model (2018, background): “…analyses forward to a practical scenario may require satisfying theoretical solutions to exploration in large state spaces, an important research direction that is relatively understudied by itself despite a few very recent advances (Krishnamurthy, Agarwal, and Langford 2016; Jiang et al. 2017).”
Towards Understanding Linear Value Decomposition in Cooperative Multi-Agent Q-Learning (2020, background): “Assumption 1 considers an environment with deterministic transitions, which is a common simplification for facilitating theoretical analysis (Krishnamurthy et al., 2016).”
Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning? (2019, background): “Existing exponential lower bounds, to our knowledge, construct unstructured MDPs with an exponentially large state space and reduce a bandit problem with exponentially many arms to an MDP (Krishnamurthy et al., 2016; Sun et al., 2017).”
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”
Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle (2019, background): “Finally, a recent series of work introduced contextual decision processes (CDPs) [22, 17, 9, 31, 11] and developed algorithms with polynomial sample complexity guarantees.”
Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches (2018, methodology): “As concrete instances of such methods, the lower bound applies to several recent value-based algorithms for CDPs (Krishnamurthy et al., 2016; Jiang et al., 2017; Dann et al., 2018) as well as any future algorithms developed assuming just realizable optimal value functions.”
Ranking Policy Gradient (2019, methodology): “Most existing studies on sample complexity analysis (Kakade et al., 2003; Strehl et al., 2006; Kearns et al., 2000; Strehl et al., 2009; Krishnamurthy et al., 2016; Jiang et al., 2017; Jiang and Agarwal, 2018; Zanette and Brunskill, 2019) are established on the value function estimation.”
Reinforcement Learning: Theory and Algorithms (2019, methodology): “The next result, adapted from Krishnamurthy et al. [2016] shows that this is not possible.”