Problem Dependent Reinforcement Learning Bounds Which Can Identify Bandit Structure in MDPs
In order to make good decision under uncertainty an agent must learn from observations. To do so, two of the most common frameworks are Contextual Bandits and Markov Decision Processes (MDPs). In this paper, we study whether there exist algorithms for the more general framework (MDP) which automatically provide the best performance bounds for the specific problem at hand without user intervention and without modifying the algorithm. In particular, it is found that a very minor variant of a recently proposed reinforcement learning algorithm for MDPs already matches the best possible regret bound $\tilde O (\sqrt{SAT})$ in the dominant term if deployed on a tabular Contextual Bandit problem despite the agent being agnostic to such setting.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Armed Banditsreinforcement-learningReinforcement LearningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Cascaded Gaps: Towards Gap-Dependent Regret for Risk-Sensitive Reinforcement Learning
In this paper, we study gap-dependent regret guarantees for risk-sensitive reinforcement learning based on the entropic risk measure. We propose a novel definition of sub-optimality gaps, which we call cascaded gaps, and…
reinforcement-learningReinforcement Learning (RL)On Gap-dependent Bounds for Offline Reinforcement Learning
This paper presents a systematic study on gap-dependent sample complexity in offline reinforcement learning. Prior work showed when the density ratio between an optimal policy and the behavior policy is upper bounded (th…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs
In probably approximately correct (PAC) reinforcement learning (RL), an agent is required to identify an $\epsilon$-optimal policy with probability $1-\delta$. While minimax optimal algorithms exist for this problem, its…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
The theory of reinforcement learning has focused on two fundamental problems: achieving low regret, and identifying $\epsilon$-optimal policies. While a simple reduction allows one to apply a low-regret algorithm to obta…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Regret Analysis in Deterministic Reinforcement Learning
We consider Markov Decision Processes (MDPs) with deterministic transitions and study the problem of regret minimization, which is central to the analysis and design of optimal learning algorithms. We present logarithmic…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)