Provably Efficient Exploration in Reward Machines with Low Regret
We study reinforcement learning (RL) for decision processes with non-Markovian reward, in which high-level knowledge of the task in the form of reward machines is available to the learner. We consider probabilistic reward machines with initially unknown dynamics, and investigate RL under the average-reward criterion, where the learning performance is assessed through the notion of regret. Our main algorithmic contribution is a model-based RL algorithm for decision processes involving probabilistic reward machines that is capable of exploiting the structure induced by such machines. We further derive high-probability and non-asymptotic bounds on its regret and demonstrate the gain in terms of regret over existing algorithms that could be applied, but obliviously to the structure. We also present a regret lower bound for the studied setting. To the best of our knowledge, the proposed algorithm constitutes the first attempt to tailor and analyze regret specifically for RL with probabilistic reward machines.
Code (0)
등록된 구현이 없습니다.
Tasks
Efficient ExplorationReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Exploration in Model-based Reinforcement Learning with Randomized Reward
Model-based Reinforcement Learning (MBRL) has been widely adapted due to its sample efficiency. However, existing worst-case regret analysis typically requires optimistic planning, which is not realistic in general. In c…
Efficient ExplorationModel-based Reinforcement Learningreinforcement-learningReinforcement Learning+1Efficient Reinforcement Learning in Probabilistic Reward Machines
In this paper, we study reinforcement learning in Markov Decision Processes with Probabilistic Reward Machines (PRMs), a form of non-Markovian reward commonly found in robotics tasks. We design an algorithm for PRMs that…
LEMMAreinforcement-learningReinforcement LearningNew Insights into Bootstrapping for Bandits
We investigate the use of bootstrapping in the bandit setting. We first show that the commonly used non-parametric bootstrapping (NPB) procedure can be provably inefficient and establish a near-linear lower bound on the …
Thompson SamplingOptimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning
We study the problem of reinforcement learning in infinite-horizon discounted linear Markov decision processes (MDPs), and propose the first computationally efficient algorithm achieving near-optimal regret guarantees in…
Imitation LearningProvably Efficient Exploration in Policy Optimization
While policy-based reinforcement learning (RL) achieves tremendous successes in practice, it is significantly less understood in theory, especially compared with value-based RL. In particular, it remains elusive how to d…
Efficient ExplorationReinforcement LearningReinforcement Learning (RL)