# Foundations of Reinforcement Learning and Interactive Decision Making

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Dec 2023.

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

- [Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF](https://mlsanity.com/paper/2405.21046/) (2024)
- [Self-Improvement in Language Models: The Sharpening Mechanism](https://mlsanity.com/paper/2412.01951/) (2024)
- [Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimization](https://mlsanity.com/paper/2407.13399/) (2024)
- [Applied Causal Inference Powered by ML and AI](https://mlsanity.com/paper/2403.02467/) (2024)
- [Logarithmic Regret for Online KL-Regularized Reinforcement Learning](https://mlsanity.com/paper/2502.07460/) (2025)
- [Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective](https://mlsanity.com/paper/2502.10581/) (2025)
- [Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification](https://mlsanity.com/paper/2502.12465/) (2025)
- [Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Bandits](https://mlsanity.com/paper/2502.06051/) (2025)
- [Scalable Multi-Objective and Meta Reinforcement Learning via Gradient Estimation](https://mlsanity.com/paper/2511.12779/) (2025)
- [Learning to Answer from Correct Demonstrations](https://mlsanity.com/paper/2510.15464/) (2025)
- [SOMBRL: Scalable and Optimistic Model-Based RL](https://mlsanity.com/paper/2511.20066/) (2025)
- [Hybrid Preference Optimization for Alignment: Provably Faster Convergence Rates by Combining Offline Preferences with Online Exploration](https://mlsanity.com/paper/2412.10616/) (2024)
- [The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective](https://mlsanity.com/paper/2501.15910/) (2025)
- [Improved Bounds for Private and Robust Alignment](https://mlsanity.com/paper/2512.23816/) (2025)
- [Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability](https://mlsanity.com/paper/2605.09214/) (2026)
- [When Does Online Imitation Learning Help in LLM Post-Training? The Role of (Non-)Realizability Beyond Horizon](https://mlsanity.com/paper/2606.30445/) (2026)
- [FlowRL: Flow-Augmented Few-Shot Reinforcement Learning for Semi-Structured Sensor Data](https://mlsanity.com/paper/2409.14178/) (2024)
- [Minimax Optimal Reinforcement Learning with Quasi-Optimism](https://mlsanity.com/paper/2503.00810/) (2025)
- [Direct Preference Optimization with Rating Information: Practical Algorithms and Provable Gains](https://mlsanity.com/paper/2602.00603/) (2026)
- [Enhancing Quantum Memory Lifetime with Measurement-Free Local Error Correction and Reinforcement Learning](https://mlsanity.com/paper/2408.09524/) (2024)
- [A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2602.10971/) (2026)
- [Data-driven Error Estimation: Excess Risk Bounds without Class Complexity as Input](https://mlsanity.com/paper/2405.04636/) (2024)
- [A conversion theorem and minimax optimality for continuum contextual bandits](https://mlsanity.com/paper/2406.05714/) (2024)
- [Perturbing the Derivative: Wild Refitting for Model-Free Evaluation of Machine Learning Models under Bregman Losses](https://mlsanity.com/paper/2509.02476/) (2025)
- [Improved Training Mechanism for Reinforcement Learning via Online Model Selection](https://mlsanity.com/paper/2512.02214/) (2025)
- [Statistical analysis of Inverse Entropy-regularized Reinforcement Learning](https://mlsanity.com/paper/2512.06956/) (2025)
- [A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regression](https://mlsanity.com/paper/2602.05019/) (2026)
- [Approximation of Log-Partition Function in Policy Mirror Descent Induces Implicit Regularization for LLM Post-Training](https://mlsanity.com/paper/2602.05933/) (2026)
- [Bayesian Online Model Selection](https://mlsanity.com/paper/2602.17958/) (2026)
- [Constrained Contextual Bandits with Adversarial Contexts](https://mlsanity.com/paper/2605.06190/) (2026)

## Abstract (arXiv)

Interactive decision making is the problem of learning to act well in an unknown environment, using the data that one's own actions generate to continuously improve, and arises in situations ranging from online platforms and robotics to medical treatments. This monograph gives a statistical perspective on algorithm design and complexity for interactive decision making, building from multi-armed bandits through contextual and structured bandits to reinforcement learning with function approximation within a single, unified framework. Special attention is paid to function approximation and flexible models such as neural networks, and to the connection between supervised learning and decision making: the reader will learn how to turn any supervised learning method into a decision making algorithm, how to analyze the result, and how to determine whether a given problem can be solved with few interactions. A unifying theme is that for interactive problems, unlike supervised learning, the question of how hard a problem is cannot be separated from the question of how to solve it. We develop this theme through two recent ideas, which complement classical approaches such as optimism and posterior sampling: the Estimation-to-Decisions principle, which reduces decision making to supervised estimation combined with an exploration rule, and the Decision-Estimation Coefficient, a complexity measure that both determines the exploration rule and lower bounds the regret of any algorithm. For contextual bandits, the resulting theory is essentially complete and its algorithms are widely deployed; for reinforcement learning, it represents the current frontier.