A unifying framework for computational reinforcement learning theory

By Michael L. Littman, Lihong Li. 2009

85 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research

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

Information-Theoretic Considerations in Batch Reinforcement Learning (2019, background): “It is known that certaintyequivalence with Q-irrelevant abstraction is consistent and enjoys polynomial sample complexity when each stateaction pair receives enough data (Li, 2009; Hutter, 2014; Jiang et al., 2015; Abel et al., 2016; Jiang, 2018).”
Fairness in Learning: Classic and Contextual Bandits (2016, background): “The impossibility of non-trivial KWIK-learning of conjunctions [Li, 2009, Li et al., 2011] implies that no fair learner in the contextual bandit setting can achieve non-trivial regret before exponentially many (in d ) rounds.”
Reinforcement learning with multi-fidelity simulators (2014, methodology): “Also, based on the analysis of KWIK-Rmax (Theorem 4 of [14]), if m known known states in a row are encountered, then with high probability we have identiﬁed the optimal policy at the current level.”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, methodology): “A related model introduced by Li [2009] for extending tabular PAC-MDP methods to large MDPs using a form of state abstractions also has low Bellman rank (See Appendix B.2).”
Recent advances in reinforcement learning in finance (2021, methodology): “The R-MAX algorithm was proved to achieve a sample complexity of exploration of order ̃( ||2|| (1−𝜆)6𝜀3 ) by Li (2009).”
Knows what it knows: a framework for self-aware learning (2008, background): “A full derivation of this KWIK bound is provided in Li (2009).”
Convex Optimization: Algorithms and Complexity (2015, unknown): “, Marbach [1998], Baxter and Bartlett [2001]).”
Sample Complexity Bounds of Exploration (2012, methodology): “The intuition above is formalized in the following generic theorem (Li, 2009), which slightly improves the original result (Strehl et al, 2006a).”
Exploring compact reinforcement-learning representations with linear regression (2009, methodology): “f, with high (1 − δ) probability, ||ybt − yt|| < ǫ and the number of ⊥s returned over the agent’s lifetime is bounded by a polynomial function over the size of the input problem. It has been shown [10] that in the model-based reinforcement-learningsetting, if the underlying model learner is KWIK,”
PAC Optimal Exploration in Continuous Space Markov Decision Processes (2013, unknown): “1 in Williams and Baird (1993)).”
Concurrent PAC RL (2015, methodology): “We use Lemma 56 from (Li 2009) to yield”
Model-based reinforcement learning with nearly tight exploration complexity bounds (2010, background): “bound is by Li (2009): at least Ω( NKR max 2 log N δ ) exploratory moves are necessary for any deterministic algorithm that learns from samples.”
Off-policy Model-based Learning under Unknown Factored Dynamics (2015, methodology): “We will make use of the following Proposition proved in Li (2009).”