Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback

• URL: http://arxiv.org/abs/2201.13172v1
• Date: Mon, 31 Jan 2022 12:34:26 GMT
• Title: Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback
• Authors: Tiancheng Jin and Tal Lancewicki and Haipeng Luo and Yishay Mansour and Aviv Rosenberg
• Abstract summary: We study online learning in episodic Markov decision process (MDP) with unknown transitions, adversarially changing costs, and unrestricted delayed bandit feedback. We present the first algorithms that achieve near-optimal $sqrtK + D$ regret, where $K$ is the number of episodes and $D = sum_k=1K dk$ is the total delay.
• Score: 67.63049551992816
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The standard assumption in reinforcement learning (RL) is that agents observe feedback for their actions immediately. However, in practice feedback is often observed in delay. This paper studies online learning in episodic Markov decision process (MDP) with unknown transitions, adversarially changing costs, and unrestricted delayed bandit feedback. More precisely, the feedback for the agent in episode $k$ is revealed only in the end of episode $k + d^k$, where the delay $d^k$ can be changing over episodes and chosen by an oblivious adversary. We present the first algorithms that achieve near-optimal $\sqrt{K + D}$ regret, where $K$ is the number of episodes and $D = \sum_{k=1}^K d^k$ is the total delay, significantly improving upon the best known regret bound of $(K + D)^{2/3}$.

Related papers

• Delay as Payoff in MAB [40.65658965074464]
  We investigate a variant of the classical Multi-armed Bandit (MAB) problem, where the payoff received by an agent is both delayed, and directly corresponds to the magnitude of the delay. Our main contributions are tight upper and lower bounds for both the cost and reward settings. Our regret bounds highlight the difference between the cost and reward scenarios, showing that the improvement in the cost scenario is more significant than for the reward.
  arXiv  Detail & Related papers  (2024-08-27T15:52:52Z)
• Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
  bandit convex optimization (BCO) with delayed feedback, where only the loss value of the action is revealed under a delay. We develop a novel algorithm, and prove that it enjoys a regret bound of $O(sqrtnT3/4+sqrtdT)$ in general. We show that the proposed algorithm can improve the regret bound to $O((nT)2/3log/3T+dlog T)$ for strongly convex functions.
  arXiv  Detail & Related papers  (2024-02-14T13:08:26Z)
• Adversarial Bandits with Multi-User Delayed Feedback: Theory and Application [17.64363983613468]
  We formulate an adversarial MAB problem with multi-user delayed feedback and design a modified EXP3 algorithm MUD-EXP3. In this paper, we consider that the delayed feedback results are from multiple users and are unrestricted on internal distribution.
  arXiv  Detail & Related papers  (2023-10-17T12:08:15Z)
• The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition [49.78053380710322]
  We consider the best-of-both-worlds problem for learning an episodic Markov Decision Process through $T$ episodes. Recent work by [Jin and Luo, 2020] achieves this goal when the fixed transition is known. In this work, we resolve this open problem by using the same Follow-the-Regularized-Leader ($textFTRL$) framework together with a set of new techniques.
  arXiv  Detail & Related papers  (2021-06-08T05:46:35Z)
• Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case [29.99619764839178]
  We make significant progress toward the shortest path problem with adversarial costs and unknown transition. Specifically, we develop algorithms that achieve $widetildeO(sqrtS3A2DT_star K)$ regret for the full-information setting. We are also the first to consider the most challenging combination: bandit feedback with adversarial costs and unknown transition.
  arXiv  Detail & Related papers  (2021-02-10T06:33:04Z)
• Learning Adversarial Markov Decision Processes with Delayed Feedback [45.86354980347581]
  We consider online learning in episodic Markov decision processes (MDPs) with unknown transitions, adversarially changing costs and unrestricted delayed feedback. We present novel algorithms that achieve near-optimal high-probability regret of $widetilde O ( sqrtK + sqrtD )$ under full-information feedback.
  arXiv  Detail & Related papers  (2020-12-29T16:47:42Z)
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition [37.6975819766632]
  We study the shortest path problem with adversarial costs and known transition. We show that the minimax regret is $widetildeO(sqrtDTstar K)$ and $widetildeO(sqrtDTstar SA K)$ for the full-information setting and the bandit feedback setting.
  arXiv  Detail & Related papers  (2020-12-07T20:55:28Z)
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition [59.34067736545355]
  We study the reinforcement learning problem in finite-horizon episodic Markov Decision Processes (MDPs) with $S$ states, $A$ actions, and episode length $H$. We propose a model-free algorithm UCB-Advantage and prove that it achieves $tildeO(sqrtH2SAT)$ regret where $T = KH$ and $K$ is the number of episodes to play.
  arXiv  Detail & Related papers  (2020-04-21T14:00:06Z)
• Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
  shortest path (SSP) is a well-known problem in planning and control, in which an agent has to reach a goal state in minimum total expected cost. We show that any learning algorithm must have at least $Omega(B_star sqrt|S| |A| K)$ regret in the worst case.
  arXiv  Detail & Related papers  (2020-02-23T09:10:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.