Foundations of Reinforcement Learning and Interactive Decision Making

arXiv:2312.16730 · cs.LG, math.OC, math.ST, stat.ML, stat.TH · Submitted 2023-12-27 · Read on arXiv

cs.LG, math.OC, math.ST, stat.ML, stat.TH

Submitted: 2023-12-27

Updated: 2026-09-24

Comments: V2 changes: General writing and organization improvements, technical fixes, additional content on lower bounds

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Regret — 266× in this paper · explained in 3 episodes
• Reinforcement Learning — 63× in this paper · explained in 4 episodes
• Decision-Estimation Coefficient — 52× in this paper
• Contextual Bandits — 36× in this paper · explained in 3 episodes
• Reward Function — 24× in this paper · explained in 4 episodes
• Generalization — 22× in this paper · explained in 13 episodes
• Action Space — 14× in this paper · explained in 1 episode
• Sample Complexity — 13× in this paper · explained in 19 episodes
• Information Gain — 12× in this paper · explained in 2 episodes
• Minimax Regret — 12× in this paper · explained in 4 episodes
• Loss Function — 8× in this paper · explained in 2 episodes
• Contextual Bandit Problem — 7× in this paper · explained in 2 episodes
• Online Reinforcement Learning — 7× in this paper · explained in 2 episodes
• Upper Confidence Bound — 7× in this paper
• In Conference on Learning Theory — 6× in this paper
• Empirical Risk Minimization — 5× in this paper
• Credit assignment — 4× in this paper · explained in 3 episodes
• Decoupling — 4× in this paper · explained in 2 episodes
• Minimax optimality — 4× in this paper · explained in 3 episodes
• Benchmark — 3× in this paper · explained in 2 episodes
• Embeddings — 3× in this paper · explained in 2 episodes
• Abstraction — 2× in this paper · explained in 1 episode
• Consistency — 2× in this paper · explained in 3 episodes
• Core — 2× in this paper · explained in 2 episodes
• Distribution Shift — 2× in this paper · explained in 9 episodes
• Adaptivity — 1× in this paper · explained in 1 episode
• Adversarial Context — 1× in this paper · explained in 1 episode
• Adversarial Model — 1× in this paper · explained in 1 episode
• Curse of Dimensionality — 1× in this paper · explained in 6 episodes
• Error Decomposition — 1× in this paper · explained in 3 episodes
• Generalization Bounds — 1× in this paper · explained in 2 episodes
• Latent Space — 1× in this paper · explained in 7 episodes
• Markov Decision Process — 1× in this paper
• Markov Decision Process (MDP) — 1× in this paper · explained in 15 episodes
• Q-learning — 1× in this paper · explained in 3 episodes
• Representation Learning — 1× in this paper · explained in 3 episodes
• Sample Efficiency — 1× in this paper · explained in 6 episodes
• Self-consistency — 1× in this paper · explained in 2 episodes
• Unified Framework — 1× in this paper · explained in 5 episodes

Sources

• Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity
• Provably Efficient Reinforcement Learning with Aggregated States
• The Statistical Complexity of Interactive Decision Making
• Model-Free Reinforcement Learning with the Decision-Estimation Coefficient
• On the Complexity of Adversarial Decision Making
• Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient
• Understanding the Eluder Dimension
• GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond

Related papers

• Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
• AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
• Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
• Convergence issues in Relational Concept Analysis based on AOC-posets
• Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
• Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks