mlsanityData to 7 Oct 2026

Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning

arXiv 2603.03480 ↗First posted 3 Mar 2026cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We study reinforcement learning with delayed state observation, where the agent observes the current state after some random number of time steps. We propose an algorithm that combines the augmentation method and the upper confidence bound approach. For tabular Markov decision processes (MDPs), we derive a regret bound of tildeO(H √Dmax SAK), where S and A are the cardinalities of the state and action spaces, H is the time horizon, K is the number of episodes, and Dmax is the maximum length of the delay. We also provide a matching lower bound up to logarithmic factors, showing the optimality of our approach. Our analytical framework formulates this problem as a special case of a broader class of MDPs, where their transition dynamics decompose into a known component and an unknown but structured component. We establish general results for this abstract setting, which may be of independent interest.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 25 of its 40 references that are in the map. First posted on arXiv 3 Mar 2026.

Builds on

25 of 40 references.

References · 25

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  4. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  5. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  6. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  7. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  8. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  9. 2018Linear Bandits with Stochastic Delayed Feedbackcited by 55
  10. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  11. 2020Stochastic bandits with arm-dependent delayscited by 36
  12. 2021Stochastic Multi-Armed Bandits with Unrestricted Delay Distributionscited by 33
13 more
  1. 2022A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedbackcited by 23
  2. 2022Delayed Feedback in Generalised Linear Bandits Revisitedcited by 23
  3. 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
  4. 2020Blind Decision Making: Reinforcement Learning with Delayed Observationscited by 14
  5. 2024Boosting Reinforcement Learning with Strongly Delayed Feedback Through Auxiliary Short Delayscited by 10
  6. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  7. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 7
  8. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  9. 2021Optimism and Delays in Episodic Reinforcement Learningcited by 4
  10. 2025Directly Forecasting Belief for Reinforcement Learning with Delayscited by 4
  11. 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
  12. 2023Reinforcement Learning with Delayed, Composite, and Partially Anonymous Rewardcited by 2
  13. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2

Built on by

Not cited yet.