Information-Theoretic Considerations in Batch Reinforcement Learning
By Jinglin Chen, Nan Jiang. 2019
421 citations recorded by the source corpus.
Value-function approximation methods that operate in batch mode have foundational importance to reinforcement learning (RL). Finite sample guarantees for these methods often crucially rely on two types of assumptions: (1) mild distribution shift, and (2) representation conditions that are stronger than realizability. However, the necessity ("why do we need them?") and the naturalness ("when do they hold?") of such assumptions have largely eluded the literature. In this paper, we revisit these assumptions and provide theoretical results towards answering the above questions, and make steps towards a deeper understanding of value-function approximation.
Subfields: Artificial Intelligence, Computer Networks and Communications, Industrial and Manufacturing Engineering, Reinforcement Learning, Information 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
- Sergey Levine
- Sham M. Kakade
- Ruslan Salakhutdinov
- Nan Jiang
- Yoshua Bengio
- Pieter Abbeel
- Qiang Liu
- Lihong Li
In Computer Networks and Communications
- Masatoshi Uehara
- Nan Jiang
- Andrea Zanette
- Thorsten Joachims
- Jiawei Huang
- Yisong Yue
- Emma Brunskill
- Lihong Li
In Industrial and Manufacturing Engineering
- Tiancheng Yu
- Akshay Krishnamurthy
- Chi Jin
- Ruosong Wang
- Sham M. Kakade
- Tengyang Xie
- Alekh Agarwal
- Yu Bai
In Reinforcement Learning
- Sergey Levine
- Nan Jiang
- Masatoshi Uehara
- Lihong Li
- Emma Brunskill
- Nathan Kallus
- Jiawei Huang
- Ofir Nachum
In Information Theory
- Ruosong Wang
- Sham M. Kakade
- Tengyang Xie
- Alekh Agarwal
- Emma Brunskill
- Ruslan Salakhutdinov
- Zhuoran Yang
- Zhaoran Wang
Citations in the corpus
- MOReL : Model-Based Offline Reinforcement Learning (2020, background): “ADP-based offline RL has also be studied theoretically [26, 52].”
- Learning When-to-Treat Policies (2019, methodology): “…is typically referred to as a “finite horizon” setting, and there is also a large literature on the “infinite horizon” setting where T is not bounded (see, e.g., Antos, Szepesvári, and Munos 2008a, 2008b; Munos and Szepesvári 2008; Q. Liu et al. 2018; Uehara and Jiang 2019; Luckett et al. 2020).”
- Offline RL Without Off-Policy Evaluation (2021, background): “Upper bounds generally require very strong assumptions on both the representation and limits on the distribution shift [Wang et al., 2021, Duan et al., 2020, Chen and Jiang, 2019].”
- Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning (2019, background): “• Misspecified but good generalization: Function classes such as neural networks have powerful generalization ability, but may introduce bias and inherent Bellman error5 [38, 9] (see linear vs.”
- A Kernel Loss for Solving the Bellman Equation (2019, background): “Our work is also related to a line of interesting work on Bellman residual minimization (BRM) based on nested optimization (Antos et al., 2008; Farahmand et al., 2008, 2016; Hoffman et al., 2011; Chen & Jiang, 2019).”
- On Reward-Free Reinforcement Learning with Linear Function Approximation (2020, methodology): “…this framework is to collect a dataset with sufficiently good coverage over the state space during the exploration phase, so that one can apply a batch RL algorithm on the dataset [Chen and Jiang, 2019, Agarwal et al., 2019, Antos et al., 2008, Munos and Szepesvári, 2008] during the planning phase.”
- Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL (2020, background): “In particular, (Chen & Jiang, 2019) provide a generic lower bound in absence of concentrability; such lower bound does not apply to our setting as we further assume a linear structure.”
- Recent advances in reinforcement learning in finance (2021, background): “This is closely related to the translation of online learning to offline regression [207] and RL with batch data [45, 87, 88, 192].”
- Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison (2020, methodology): “…2014]: first one is to observe that FQI has quadratic dependence on horizon and our bound for MSBO has a 1 / (1 − γ ) net improvement over FQI [Chen and Jiang, 2019]. second one is to read the expression, and count the explicit dependence; while the statistical error depends on V max = R max / (1…”
- Bellman-consistent Pessimism for Offline Reinforcement Learning (2021, methodology): “We remark that both of these two measurements are weaker then traditional density-ratio definitions (e.g., [Munos and Szepesvári, 2008; Chen and Jiang, 2019; Xie and Jiang, 2020]) as we demonstrated before, as the dependence of C on π is relatively secondary.”
- Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism (2021, background): “In this regime, a widely-adopted requirement is the bounded uniform concentrability coefficient which assumes that the ratio of the state-action occupancy density of any policy and the data distribution is bounded uniformly over all states and actions [32, 9, 6, 52].”
- Provably Good Batch Reinforcement Learning Without Great Exploration (2020, methodology): “, the hardness of exploration in [5]).”
- Representation Learning for Online and Offline RL in Low-rank MDPs (2021, background): “Note that assuming offline data covers π (cid:63) is still a weaker assumption than the global coverage such as sup π sup ( s,a ) d πP ( s, a ) /ρ ( s, a ) in prior offline RL works (Antos et al., 2008; Chen and Jiang, 2019).”