Contextual Decision Processes with Low Bellman Rank are PAC-Learnable

2016-10-29 · ICML 2017 8 · Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, Robert E. Schapire

This paper studies systematic exploration for reinforcement learning with rich observations and function approximation. We introduce a new model called contextual decision processes, that unifies and generalizes most prior settings. Our first contribution is a complexity measure, the Bellman rank, that we show enables tractable learning of near-optimal behavior in these processes and is naturally small for many well-studied reinforcement learning settings. Our second contribution is a new reinforcement learning algorithm that engages in systematic exploration to learn contextual decision processes with low Bellman rank. Our algorithm provably learns near-optimal behavior with a number of samples that is polynomial in all relevant parameters but independent of the number of unique observations. The approach uses Bellman error minimization with optimistic exploration and provides new insights into efficient exploration for reinforcement learning with function approximation.

📄 PDF Abstract BibTeX arXiv:1610.09512

Code (0)

등록된 구현이 없습니다.

Tasks

Efficient Explorationreinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

$\sqrt{n}$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank

2019-09-05 · Kefan Dong, Jian Peng, Yining Wang, Yuan Zhou

In this paper, we consider the problem of online learning of Markov decision processes (MDPs) with very large state spaces. Under the assumptions of realizable function approximation and low Bellman ranks, we develop an …

Efficient Exploration Reinforcement Learning

Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches

2018-11-21 · Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal 외

We study the sample complexity of model-based reinforcement learning (henceforth RL) in general contextual decision processes that require strategic exploration to find a near-optimal policy. We design new algorithms for…

model Model-based Reinforcement Learning Reinforcement Learning

Classical Policy Gradient: Preserving Bellman's Principle of Optimality

2019-06-06 · Philip S. Thomas, Scott M. Jordan, Yash Chandak, Chris Nota 외

We propose a new objective function for finite-horizon episodic Markov decision processes that better captures Bellman's principle of optimality, and provide an expression for the gradient of the objective.

Contextual Bandits with Arm Request Costs and Delays

2024-10-17 · Lai Wei, Ambuj Tewari, Michael A. Cianfrocco

We introduce a novel extension of the contextual bandit problem, where new sets of arms can be requested with stochastic time delays and associated costs. In this setting, the learner can select multiple arms from a deci…

Movie Recommendation Multi-Armed Bandits

Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection

2021-10-27 · NeurIPS 2021 12 · Matteo Papini, Andrea Tirinzoni, Aldo Pacchiano, Marcello Restelli 외

We study the role of the representation of state-action value functions in regret minimization in finite-horizon Markov Decision Processes (MDPs) with linear structure. We first derive a necessary condition on the repres…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)