Provably Efficient Exploration in Reward Machines with Low Regret
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929648669032448 |
|---|---|
| author | Bourel, Hippolyte Jonsson, Anders Maillard, Odalric-Ambrym Ma, Chenxiao Talebi, Mohammad Sadegh |
| author_facet | Bourel, Hippolyte Jonsson, Anders Maillard, Odalric-Ambrym Ma, Chenxiao Talebi, Mohammad Sadegh |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_19194 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Provably Efficient Exploration in Reward Machines with Low Regret Bourel, Hippolyte Jonsson, Anders Maillard, Odalric-Ambrym Ma, Chenxiao Talebi, Mohammad Sadegh Machine Learning Artificial Intelligence 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. |
| title | Provably Efficient Exploration in Reward Machines with Low Regret |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2412.19194 |