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, John Langford

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 RL with a generic model class and analyze their statistical properties. Our algorithms have sample complexity governed by a new structural parameter called the witness rank, which we show to be small in several settings of interest, including factored MDPs. We also show that the witness rank is never larger than the recently proposed Bellman rank parameter governing the sample complexity of the model-free algorithm OLIVE (Jiang et al., 2017), the only other provably sample-efficient algorithm for global exploration at this level of generality. Focusing on the special case of factored MDPs, we prove an exponential lower bound for a general class of model-free approaches, including OLIVE, which, when combined with our algorithmic results, demonstrates exponential separation between model-based and model-free RL in some rich-observation settings.

📄 PDF Abstract BibTeX arXiv:1811.08540

Code (0)

등록된 구현이 없습니다.

Tasks

modelModel-based Reinforcement LearningReinforcement Learning

Markov Decision Processes with Continuous Side Information

2017-11-15 · Aditya Modi, Nan Jiang, Satinder Singh, Ambuj Tewari

We consider a reinforcement learning (RL) setting in which the agent interacts with a sequence of episodic MDPs. At the start of each episode the agent has access to some side-information or context that determines the d…

PAC learning Reinforcement Learning Reinforcement Learning (RL)

Reinforcement Learning with History-Dependent Dynamic Contexts

2023-02-04 · Guy Tennenholtz, Nadav Merlis, Lior Shani, Martin Mladenov 외

We introduce Dynamic Contextual Markov Decision Processes (DCMDPs), a novel reinforcement learning framework for history-dependent environments that generalizes the contextual MDP framework to handle non-Markov environme…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Logarithmic regret bounds for continuous-time average-reward Markov decision processes

2022-05-23 · Xuefeng Gao, Xun Yu Zhou

We consider reinforcement learning for continuous-time Markov decision processes (MDPs) in the infinite-horizon, average-reward setting. In contrast to discrete-time MDPs, a continuous-time process moves to a state and s…

Point Processes reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

PAC Bounds for Imitation and Model-based Batch Learning of Contextual Markov Decision Processes

2020-06-11 · Yash Nair, Finale Doshi-Velez

We consider the problem of batch multi-task reinforcement learning with observed context descriptors, motivated by its application to personalized medical treatment. In particular, we study two general classes of learnin…

Imitation Learning

Square-root regret bounds for continuous-time episodic Markov decision processes

2022-10-03 · Xuefeng Gao, Xun Yu Zhou

We study reinforcement learning for continuous-time Markov decision processes (MDPs) in the finite-horizon episodic setting. In contrast to discrete-time MDPs, the inter-transition times of a continuous-time MDP are expo…

reinforcement-learning Reinforcement Learning (RL)