Optimism and delays in episodic reinforcement learning
File(s)
Author(s)
Howson, Benjamin
Pike-Burke, Ciara
Filippi, Sarah
Type
Conference Paper
Abstract
There are many algorithms for regret minimisation in episodic reinforcement learning. This problem is well-understood from a theoretical perspective, providing that the sequences of states, actions and rewards associated with each episode are available to the algorithm updating
the policy immediately after every interaction with the environment. However, feedback is almost always delayed in practice. In this paper, we study the impact of delayed feedback in episodic reinforcement learning from a
theoretical perspective and propose two general-purpose
approaches to handling the delays. The first involves updating as soon as new information becomes available, whereas the second waits before using newly observed information to update the policy. For the class of optimistic algorithms and either approach, we show that the regret in-
creases by an additive term involving the number of states, actions, episode length, the expected delay and an algorithm-dependent constant. We empirically investigate the impact of various delay distributions on the regret of optimistic algorithms to validate our theoretical results.
the policy immediately after every interaction with the environment. However, feedback is almost always delayed in practice. In this paper, we study the impact of delayed feedback in episodic reinforcement learning from a
theoretical perspective and propose two general-purpose
approaches to handling the delays. The first involves updating as soon as new information becomes available, whereas the second waits before using newly observed information to update the policy. For the class of optimistic algorithms and either approach, we show that the regret in-
creases by an additive term involving the number of states, actions, episode length, the expected delay and an algorithm-dependent constant. We empirically investigate the impact of various delay distributions on the regret of optimistic algorithms to validate our theoretical results.
Date Issued
2023-06-04
Date Acceptance
2023-01-20
Citation
Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS) 2023, 2023, pp.1-34
Publisher
PMLR
Start Page
1
End Page
34
Journal / Book Title
Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS) 2023
Copyright Statement
Copyright © 2023 by the author(s). This work is published under a CC BY licence.
License URL
Identifier
https://proceedings.mlr.press/v206/howson23a.html
Source
Artificial Intelligence and Statistics (AISTATS 2023)
Publication Status
Published
Start Date
2023-04-25
Finish Date
2023-04-27
Coverage Spatial
Valencia, Spain
Date Publish Online
2023-06-04