mlsanityData to 7 Oct 2026

Reinforcement Learning with Delayed, Composite, and Partially Anonymous Reward

arXiv 2305.02527 ↗First posted 4 May 2023cs.LG cs.AIcited by 2

Not on the map. Why?

Abstract (arXiv)

We investigate an infinite-horizon average reward Markov Decision Process (MDP) with delayed, composite, and partially anonymous reward feedback. The delay and compositeness of rewards mean that rewards generated as a result of taking an action at a given state are fragmented into different components, and they are sequentially realized at delayed time instances. The partial anonymity attribute implies that a learner, for each state, only observes the aggregate of past reward components generated as a result of different actions taken at that state, but realized at the observation instance. We propose an algorithm named DUCRL2 to obtain a near-optimal policy for this setting and show that it achieves a regret bound of tildeOleft(DS√AT + d (SA)3right) where S and A are the sizes of the state and action spaces, respectively, D is the diameter of the MDP, d is a parameter upper bounded by the maximum reward delay, and T denotes the time horizon. This demonstrates the optimality of the bound in the order of T, and an additive impact of the delay.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 23 of its 33 references that are in the map. First posted on arXiv 4 May 2023.

Builds on

23 of 33 references.

References · 23

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  4. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  5. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  6. 2016Delay and Cooperation in Nonstochastic Banditscited by 71
  7. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  8. 2020Reinforcement Learning with Random Delayscited by 56
  9. 2018Linear Bandits with Stochastic Delayed Feedbackcited by 55
  10. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  11. 2019Nonstochastic Multiarmed Bandits with Unrestricted Delayscited by 46
  12. 2019An Optimal Algorithm for Adversarial Bandits with Arbitrary Delayscited by 44
11 more
  1. 2020Stochastic bandits with arm-dependent delayscited by 36
  2. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  3. 2021Stochastic Multi-Armed Bandits with Unrestricted Delay Distributionscited by 33
  4. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  5. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
  6. 2019Reinforcement Learning for Joint Optimization of Multiple Rewardscited by 15
  7. 2020Blind Decision Making: Reinforcement Learning with Delayed Observationscited by 14
  8. 2020Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedbackcited by 9
  9. 2022Multi-Agent Reinforcement Learning with Reward Delayscited by 9
  10. 2021Optimism and Delays in Episodic Reinforcement Learningcited by 4
  11. 2023Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit Feedbackcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 0; 2025: 0; 2026: 1.

2 papers.

  1. 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
  2. 2026Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learningcited by 0