# Reinforcement Learning, Bit by Bit

arXiv: https://arxiv.org/abs/2103.04047 · HTML: https://mlsanity.com/paper/2103.04047/

## Key facts

- Cited by 59 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 103 references that are in the map.
- First posted on arXiv 6 Mar 2021.

## Builds on (most cited first, 30 of 45)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Large-Scale Study of Curiosity-Driven Learning](https://mlsanity.com/paper/1808.04355/) (2018)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Randomized Prior Functions for Deep Reinforcement Learning](https://mlsanity.com/paper/1806.03335/) (2018)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Behaviour Suite for Reinforcement Learning](https://mlsanity.com/paper/1908.03568/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [The Value Equivalence Principle for Model-Based Reinforcement Learning](https://mlsanity.com/paper/2011.03506/) (2020)
- [The Uncertainty Bellman Equation and Exploration](https://mlsanity.com/paper/1709.05380/) (2017)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Hybrid Reward Architecture for Reinforcement Learning](https://mlsanity.com/paper/1706.04208/) (2017)
- [Information-Directed Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1812.07544/) (2018)
- [Information-Theoretic Confidence Bounds for Reinforcement Learning](https://mlsanity.com/paper/1911.09724/) (2019)
- [Discovery of Useful Questions as Auxiliary Tasks](https://mlsanity.com/paper/1909.04607/) (2019)
- [An Information-Theoretic Approach to Minimax Regret in Partial Monitoring](https://mlsanity.com/paper/1902.00470/) (2019)
- [Information Directed Sampling for Linear Partial Monitoring](https://mlsanity.com/paper/2002.11182/) (2020)
- [Mirror Descent and the Information Ratio](https://mlsanity.com/paper/2009.12228/) (2020)
- [Satisficing in Time-Sensitive Bandit Learning](https://mlsanity.com/paper/1803.02855/) (2018)

## Built on by (most cited first, 30 of 59)

- [Epistemic Neural Networks](https://mlsanity.com/paper/2107.08924/) (2021)
- [A Definition of Continual Reinforcement Learning](https://mlsanity.com/paper/2307.11046/) (2023)
- [Continual Learning as Computationally Constrained Reinforcement Learning](https://mlsanity.com/paper/2307.04345/) (2023)
- [Settling the Reward Hypothesis](https://mlsanity.com/paper/2212.10420/) (2022)
- [Approximate Thompson Sampling via Epistemic Neural Networks](https://mlsanity.com/paper/2302.09205/) (2023)
- [From Predictions to Decisions: The Importance of Joint Predictive Distributions](https://mlsanity.com/paper/2107.09224/) (2021)
- [Regret Bounds for Information-Directed Reinforcement Learning](https://mlsanity.com/paper/2206.04640/) (2022)
- [The Neural Testbed: Evaluating Joint Predictions](https://mlsanity.com/paper/2110.04629/) (2021)
- [Fine-Tuning Language Models via Epistemic Neural Networks](https://mlsanity.com/paper/2211.01568/) (2022)
- [Non-Stationary Bandit Learning via Predictive Sampling](https://mlsanity.com/paper/2205.01970/) (2022)
- [Information Directed Sampling for Sparse Linear Bandits](https://mlsanity.com/paper/2105.14267/) (2021)
- [Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/2205.13924/) (2022)
- [Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learning](https://mlsanity.com/paper/2206.02072/) (2022)
- [Collect & Infer -- a fresh look at data-efficient Reinforcement Learning](https://mlsanity.com/paper/2108.10273/) (2021)
- [Toward Efficient Exploration by Large Language Model Agents](https://mlsanity.com/paper/2504.20997/) (2025)
- [Contextual Information-Directed Sampling](https://mlsanity.com/paper/2205.10895/) (2022)
- [The Value of Information When Deciding What to Learn](https://mlsanity.com/paper/2110.13973/) (2021)
- [Three Dogmas of Reinforcement Learning](https://mlsanity.com/paper/2407.10583/) (2024)
- [Formalizing Learning from Language Feedback with Provable Guarantees](https://mlsanity.com/paper/2506.10341/) (2025)
- [Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications](https://mlsanity.com/paper/2302.03683/) (2023)
- [Plasticity as the Mirror of Empowerment](https://mlsanity.com/paper/2505.10361/) (2025)
- [Probabilistic Inference in Reinforcement Learning Done Right](https://mlsanity.com/paper/2311.13294/) (2023)
- [Reinforcement Learning in Non-Markovian Environments](https://mlsanity.com/paper/2211.01595/) (2022)
- [Exploring through Random Curiosity with General Value Functions](https://mlsanity.com/paper/2211.10282/) (2022)
- [Efficient Exploration via Epistemic-Risk-Seeking Policy Optimization](https://mlsanity.com/paper/2302.09339/) (2023)
- [On Rollouts in Model-Based Reinforcement Learning](https://mlsanity.com/paper/2501.16918/) (2025)
- [BOFormer: Learning to Solve Multi-Objective Bayesian Optimization via Non-Markovian RL](https://mlsanity.com/paper/2505.21974/) (2025)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [Agent-state based policies in POMDPs: Beyond belief-state MDPs](https://mlsanity.com/paper/2409.15703/) (2024)
- [Learning and Information in Stochastic Networks and Queues](https://mlsanity.com/paper/2105.08769/) (2021)

## Abstract (arXiv)

Reinforcement learning agents have demonstrated remarkable achievements in simulated environments. Data efficiency poses an impediment to carrying this success over to real environments. The design of data-efficient agents calls for a deeper understanding of information acquisition and representation. We discuss concepts and regret analysis that together offer principled guidance. This line of thinking sheds light on questions of what information to seek, how to seek that information, and what information to retain. To illustrate concepts, we design simple agents that build on them and present computational results that highlight data efficiency.