Foundations of Reinforcement Learning and Interactive Decision Making

Abstract: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.

Machine Learning (cs.LG); Optimization and Control (math.OC); Statistics Theory (math.ST); Machine Learning (stat.ML)

arXiv:2312.16730 [cs.LG]

(or arXiv:2312.16730v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2312.16730 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.