Reinforcement Learning with Delayed, Composite, and Partially Anonymous Reward
Authors: Washim Uddin Mondal
Vaneet Aggarwal
Venue: Accepted by TMLR ()

Abstract: 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 $\mathrm{DUCRL2}$ to obtain a near-optimal policy for this setting and show that it achieves a regret bound of $\tilde{\mathcal{O}}\left(DS\sqrt{AT} + d (SA)^3\right)$ 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.

Published in Transactions on Machine Learning Research (08/2023)
Reinforcement Learning with Delayed, Composite, and Par- tially Anonymous Reward
Washim Uddin Mondal
umondal8purdue.co edu
School of IE and CE, Purdue University
Vanect Aggarwal
wanectSppurdue... edu
School of IE and ECE, Purduc Universily
Reviewed on OpenReview: https: // openreview. net/ formfo id= ubCo ubCoTAynPy
Abstract
We investigate an infmite-horizon average reward Markov Decision Process (MDP) with delayed, compasite, 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 instances. The partial anonymity aftribute implies that learner, for each state, only observes the aggregate of past reward components generated as result of different actions laken at that stale, but realized at the observation instance. We propose named DUCRL2 to obtain a near-optimal policy for this setting and show that it achieves regret bound of Ô (DSVA) AT + d(SA))) where and A are the sizes the state and action spaces, respectively, D is the diameter of the MDP, d is parameter upper bounded by the maximum reward delay, and T denotes the time horizon. This detonsttrate the optimality of the bound in the order of T, and an additive impact of the delay.
delayed time
algorithm
1 Introduction
Reinforcement learning (RL) enables agent to learn policy in unknown environment by repeatedly interacting with it. The environment has state that changes as a result of the actions executed by the agent. In this setup, a policy is a collection of rules that guides the agent to take action based on the observed state the environment. Several algorithms exist in the literature that learn a policy with near- optimal regret (Jaksch et al., 20100; Azar et al. 2017 Jin et al.j 2018 Fruit el al. 2018). However, all of the above frameworks assume that the reward is instantly fed back to the learner after executing an action. Unfortunately, this assumption of instantancity may not hold in many practical scenarios. For instance, in the online advertisement industry, customer may purchase product several days after seeing the advertisement. In medical trials, the effect of medicine may take several hours to manifest. In road networks, it might take a few minutes to notice the impact of a traffic light change. In many of these cases, the effect an action is not entirely realized in a single instant, but rather fragmented into smaller components that are sequentially materialived over a long interval. Reward feedback that satisfies this property is referred as delayed and composite reward. In several applications, the learner cannot directly observe each delayed component of composite reward but only an aggregate of the components realized the observation instance. For example, in the case of multiple advertisements, the advertiser can only see the total number of purchases at given time but is completely unaware of which advertisement resulted in what fraction of the total purchase. Such feedback is referred to as anonymous reward.
Learning with delayed, composite, and anonymous rewards is gaining popularity in the RL community, While most of the thcoretical analysis has been directed towards the multi-arm bandit (MAB) framework (Wang et al. 2021 Zhou al. 2019 Vernade et al. 2020 Pike-Burke al.) 2018 Pedramfar and Aggarwal, 2023), recent studies have also analyzed Markov Decision Processes (MDPs) with delayed feedback (Howson

---

Published in Transactions on Machine Learning Research (08/2023)
et al. 2023
Jin et al. 2022: Lancewicki et al. 2022). However, none of these studies have incorporated both composite and anonymous rewards, which is the focus of this paper.
1.1 The Challenge and Our Contribution
Learning with delayed, composite, and anonymous rewards has gained popularity in the RL community, While there has been extensive theoretical analysis of these types of rewards in the multi-arm bandit (MAB) framework, extending these ideas to the full Markov decision process (MDP) setting poses significant chal- lenges. For example, one the main ideas used in the MAB framework can be stated as follows (Wang et al., 2021j. The learning algorithm proceeds in multiple epochs with the sizes of the epochs increasing exponen- tially. At the beginning of each epoch, an action is chosen and it is applied at all instances within that epoch. Due to multiple occurrences of the chosen action, and exponentially increasing epoch lengths, the learner progressively obtains better estimates of the associated rewards despite the composite and anonymous na- ture of the feedback. In an MDP setting, however, it is impossible to ensure that any state-action pair (s. a) appears contiguously over a given stretch of time. The most that one can hope to ensure is that cach state, 8, when it appears in an epoch (defined appropriately), is always paired with a unique action, a. In this way, if the state in consideration is visited sufficiently frequently in that epoch, the learner would obtain an accurate estimate of the reward associated with the pair a). Unfortunately, in general, there is no way ensure high enough visitation frequency for all states. Unlike the MAB setup, it is, therefore, unclear how to develop regret optimal learning algorithms for MDPs with delayed, composite, and anonymous rewards.
Our article provides a partial resolution to this problem. In particular, we demonstrate that if the rewards are delayed, composite, and partially anonymous, then an algorithm can be designed to achieve mear-optimal regret. In a fully anonymous setting, a learner observes the aggregate of the (delayed) reward components generated as a result of all state-action pairs visited in the past. In contrast, a partially anonymous setup allows a learner to observe the sum of (delayed) reward components generated as a result of all past visitations to any specified state. Our proposed algorithm, DUCRL2, is built upon the UCRL2 algorithm of (Jaksch) ct al. 2010) and works in multiple epochs. Unlike the bandit setting, however, the epoch lengths are not guaranteed to be exponentially increasing. Our primary innovation lies in demonstrating how an accurate reward function estimate can be obtained using the partially anonymous feedback. DUCRL2 yields a regret bound of O(SSVA + A(S)))) where S, A denote the sizes of the state and action spaces respectively, T is the time horizon, D denotes the diameter of the MDP, and the parameter d is bounded by the maximum delay the reward generation process. The obtained result. matches well-known lower bound in T.
1.2 Relevant Literature
Bclow we describe in detail the relevant literature.
Regret Bounds in Non-delayed RL: The framework of regret minimization RT. with immediate feedback is well-investigated in the literature. In particular, this topic has been explored in the settings of
both stochastic (Jaksch et al., 2010 Zanette et al. 20200] Agarwal and Aggarwal 2023 Agarwal et al. 2022;
2023) and adversarial (Jin and Luo. 2020 Rosenberg and Mansour 2019 Shani et al. 2020 MDPs Our setup can be considered to be the generalization of the stochastic MDPs with immediate feedback.
Delay in Bandit: Delayed feedback is a well-researched topic in the bandit literature, with numerous studies conducted both stochastic (Vernade et al.] 20200 Pike-Burke et al., 20188] Zhou et al. 2019 Gael
ct al.
2020
Lancewicki et al. 2021 Podramfar and Aggar 2023) and adversarial scttings (Quanrud and
Khashabi, 2015 Cesa-Biaanchi et al. 2016 Thhue et al., 2019 Zimmert and Seldin] 2020 Bistritz et al.,
2019
Ito et al.) 2020). However, as previously discussed, applying the insights of bandit learning to the setting with composite and anonymous rewards is challenging.
MDP
Delay in MDP: A number of recent papers have explored the incorporation of delayed feedback into the MDP framework. For example, (Lancewicki et al. 2022 Jin et al. 2022) consider adversarial MDPs, while Howson et al.] (023) analyzes a stochastic setting. However, all of these articles focus on episodic MDPs with non-composite and non-anonymous rewards, which is distinct from our work on infinite-horize MDPs with delayed, composite, and partially anonymous rewards. It is worthh noting that while delayed reward is
2

---

Published in Transactions on Machine Learning Research (08/2023)
commonly studied topic in the literature, some works also consider delays in the state information (Agaraal and Aggarwal 2021: Bouteiller et al., 2021 Additionally, the impact of delay has also been explored in the context of multi-agent learning to characterize coarse correlated equilibrium (Zhang et al. 2022).
2 Problem Setting
We consider an infinite-horizon average-reward Markov Decision Process (MDP) defined as, M - AS, r,p) where S.A A denote the state, and action spaces respectively, r : x A - [0, the reward function, and p: A -> ((S) indicates the state transition function. The function, 4(.) defines the probability simplex over its argument set. The cardinality of the sets S and A are denoted S, A respectively. Both the reward function, r, and the transition function, p assumed to be unknown.
A Caaner/agent interacts with an environment governed by the MDP stated above as follows. The interaction proceeds in discrete time steps, & E 21, ...... At the time i, the state occupied by the environment is denoted as 8, E S. The learner observes the state, $,, and chooses an action a, E AA following predefined protocol, A. As a result, a sequence rewards Te( a²) _ (ri, (St, az) ) } is generated where (1, a,) is interpreted as the non-negative component the vector r re(St, at) that rcalised at instant t+ The following assumption is made regarding the reward generation process.
Assumption It assumed that Vt E {1,2. }, V(s,a) 8 A, the following holds.
(a) ||r((,)))l ~ (s) E 10,
(b) Bl)r((s, = r(s 10,
(c) (r((s,a)) are mutually independent,
where ||: denotes the 1-norm.
Assumption aa) dictates that the reward sequences generated from (s,a) a) are such that the sum of their components can be thought of samples taken from certain distribution, D(s, a), over [0, 1]. Note that the distribution, D(s, a), is independent of t. Assumption [b) of the reward components generated from (s, a) equals r(s, a) E [0, I]. Finally, Assumption [[e] clarifies that the reward sequences generated at different instances (either by the same or distinct state-action pairs) are presumed to be independent of cach other.
(b) explains that the expected value of the sum
At the time instant I, the learner observes a reward vector St E R.S whose 8-th element is expressed as follows.
(1) = Σ (3))) =
Oc
where 1(-) defines the indicator function. Note that the learner only has access to the lump-sum reward (s),,, not its individual components contributed by past actions. This explains why the reward is termed as partially anonymous. In a fully anonymous setting, the learner can only access ||æı||ı, not its elements. Although full anonymity might be desirable for many practical scenarios, from a theoretical standpoint, it is notoriously difficult to analyze. We discuss this topic in detail section 4.2 reward generated up to time T can be computed as,
The expected accumulatod
T
R(s1, A, M,T) = Σ (r((s,)))))
(1)
We would like emphasize that R(s1, A, M, T) is not the sum of the observed rewards up time T. Rather, it equates to the sun of all the reward components that are generated consequence of the actions taken up to lime T. We define the quantity expressed below
1 E| A, M,T))
p(si, A lim T-500
(2)
3

---

Published in Transactions on Machine Learning Research (08/2023)
the average reward of the MDP M for a given protocol A and an initial state 81 S. Here the expectation is obtained over all possible T-length trajectories generated from the initial state 81 following the protocol A. and the randomness associated with the reward generation process for any given state-action pair. It is well known that (Puterman 2014) there exists a stationary deterministic policy π² : - A that maximizes the average reward V81 S it D(M), the diameter of M (defined below) is finite. Also, that case, p(81, T², .)) becomes independent of $1 and thus can be simply denoted as (M().. The diamcter D(M) defined as follows.
max min sT, (MM)
sfs' U.S -AA
where T(s'ss, s. nT, M) denotes the time needed for the MDP M to reach the state s' from the state s following the stationary deterministic policy, n. Mathematically, Pr(T(s'|s, n, M) - 1) - Pr(s; =|s1 = 8, 8y + 8, < T < f,, 87 ~ p(8-11, a7-1), 1), 0, ~ x (s+)). In simple words, given two arbitrary distinct states, one can always find a stationary deterministic policy such that the MDP, M, on average, takes at most D(M) time steps to transition from one state to the other.
We define the performance of protocol, A by the regret it accumulates over a horizon, T which is mathe- matically expressed as,
Reg(s1, M,T) = (M) -
(3)
where (M) is the maximum of the average reward given in (2) and the second term is defined in ( We would like mention that in order to define regret, we use R(s1, A, M, rather than the expected sum of the observed rewards up to time T. The rationale behind this definition is that all the components of the rewards that are generated as consequence of the actions taken up to time T would eventually be realized if we allow the system to evolve for a long enough time. Our goal in this article is to come up with an algorithm that achieves sublinear regret for the delayed, composite, and anonymous reward MDP described above.
Before concluding, we would like to provide an example of an MDP with partially anonymous rewards. Tet consider the T' round of interaction of a potential consumer with a website that advertises S categories of products. At round t, the state, 8t E f1,... ,S} obscrved by the website is the category of product scarched by the consumer. The s-th calegory where E (1,... S} has N,, number of potential advertisements, and the total number of advertisements is N = =,, Ny. The website, in response to the observed state, 8t, shows an ordered list of K < N advertisements (denoted by a,), some of which may not directly correspond to the searched category, 8t. This may cause the consumer, with some probability, to switch to a new state, $t+1 in the next. round. For example, if the consumer searching for "Computers", then showing advertisements related to " "Mouse" or "Keyboard" may incentivize the consumer to search for those categories of products. After 7 rounds, 0 < T, the consumer ends up spending r=(s) amount of money for the s-th category of product consequence of previous advertisements. Note that if the same state s appears in two different rounds 1 < t2 < t, the website can potentially show two different ordered lists of advertisements, at, Ot, to the consumer. However, it is impossible to segregate the portions of the reward r=(s) contributed by each of those actions. Hence, the system described above can be modeled by an MDP with delayed, composite, and partially anonymous rewards.
3 DUCRL2 Algorithm
In this section, we develop Delayed UCRL2 (DUCRL2) algorithm to achieve the overarching goal of our paper. It is inspired by the UCRL2 algorithm suggested by (Jaksch et al. 2010) for MDPs with immediate rewards (no delay). Before going into the details of the DUCRL2 algorithm, we would like to introduce the following assumption.
Assumption 2 There ezists a finite positive number d such that, Vt E (1,2...},
Σ
max (x.
Σ
(4)
7 20
12
4

---

Published in Transactions on Machine Learning Research (08/2023)
Algorithm DUCRL2 Algorithm Input: 8 (0, d, S,A
Initialization: Observe the initial state $1 and set 1, to +-0.
3: for episodes k E (.. do
Computing empirical estimates
4: fx ++
5: for (s,a) E x A do
6:
(x(s,)) +
{,8,, t (( E
(l.......
(s(s, Locjeh Ey(s,0)
(x(s,a) Locrety 110 8,
fx(s,a) Lociek Eocjet Lis (s) a)/ (ax,
10:
11:
for S'ESdo
12:
p ( 1(s, a, a, a,8+ 5 ((ss
13: end for
14: end for
15:
end for
16: Let Mr be the set of MDPs with state space S, action space A, transition probability p, and reward
function F such that
7 7log(25 + d Ex(s,
(((saa) (x) S
(5)
V
2 max (Na a), (s))
14S log (2Atx/8)
(6)
max No(5,a))
17:
Using extended value function iteration (Algorithm 2 an MDP Mr E M, such that,
obtain a stationary deterministic policy म and
Pk - min pls, Th. M&) 2
max P(s', TI, M') Vbk
(7)
SES
M' M.M
18:
while (8 #*(())) < max (s,,,, (8)))) do Execute at = (st)
19:
20:
Observe the reward r, and the next state S1+1 ()) + 1x (st, a:)
21:
22:
t 1
23:
end while
with probability 1 where (s, is the reward sequence generated by (s, a) at time t.
Note that if the maximum delay is dmax, then using Assumption [ a), one can show that d S dmax- Therefore, can be thought of as proxy for the maximum delay. To better understand the intuition behind Assumption
2 consider an interval (1,..., T Clearly, the reward sequence generated at 4 Ti -1, TI E (0..... ,T, 1 is re, (St, at,). The portion of this reward that is realized after Tj expressod by the following quantity: Eren Teg.r (8t ar,) which upper bounded by max(s.a) Σren Tt a). Therefore, the total amount of reward that is generated in {1. ,Ti) but realized after Ti is bounded by Σn, 20 max(s.a) Eren, (s, a). As the distribution of the reward sequence rt, is the same for all t (Assumption [a]): one can replace the dependent term l with a generic quantity, t. Thus, Assumption 2 essentially states that the spillover of the rewards generated within any finite interval (1...., (T) can be bounded by the term d.
We would also like emphasize that if dmax infinito, then may or may not be infinite depending on the reward sequence. For example, consider a deterministic sequence whose components are tt, (s, a) 2 2-1-T (8, a) S x A, VI ..,,...) VT (0, ..... }. It. is easy to show that one can choose d though dmax is
5

---

Published in Transactions on Machine Learning Research (08/2023)
infinite. On the other hand, if rt, (s, = 1(T 7)) (s, Vt, Vr where r' is random variable with the distribution Pr(r'= = k) = (1 p)r², wk E 10, < p 1, then one can show that 44 is violated with probability at least p". In other words, Assumption 2 is not satisfied for any finite d.
The DUCRL2 algorithm (Algorithm proceeds in multiple epochs. At the beginning of epoch k i.,, at time instant. 1 fs, we compute two measures for all state-action pairs. The first measure is indicated as a) which counts the number of times the pair (s,a) appears before the onset of the kth epoch. The second measure is (,, a) which is binary random variable that indicates whether the pair (s, a) appears at least once in the jth epoch, 0 < j <. k. Due to the very nature of our algorithm (elaborated later), in given epoch J, if as) = 1, then E's,,'' = O, va' E A \ {a). Taking sum over {Ej(s, a) Jo we obtain Es(s, a) which counts the number of epochs where (3, appears at least once before 4,, the start of the kth episode.
Next, we obtain the reward estimate (x, a) by computing the sum of the s-th element of the observed reward over all epochs where as, appears at least once and dividing it by (x(s, a). Also, the transition probability estimate (s(s'ss, a) is calculated by taking ratio of the number of times the transition (s, s') occurs before the kth episode and Nu(s, a). It is to be clarified that, due to the delayed composite nature of the reward, the observed reward values that are used for computing fx(s, a) may be contaminated by the components generated by previous actions which could potentially be different from a. Consequently, it might appear that the empirical estimates (x(s, a) may not serve as a good proxy for r(s, a). However, the analysis of our algorithm exhibits that by judiciously steering the exploration, it is still possible to obtain a near-optimal regret.
Using the estimates fx(s,,), a), P& (-(ss))), now define confidence set M& of MDPs that is characterized by 5), (6.. The confidence radius given in (5) is one of the main differences between our algorithm and the UCRL2 algorithm given by (Jaksch et al. 2010). Applying extended value iteration (Appendix A we then derive a policy Rx, and an MDP Mj E MM that are near-optimal within the set MM in the sense of We keep on executing the policy i& until for at least one state-action pair a), its total number of occurrences within the current epoch, (s(s,,) a) becomes at least as large as (s, the number of its occurrences before the onset of the current epoch. When this criterion is achieved, a new epoch begins and the process described above starts all over again. Observe that, as the executed policies are deterministic, no two distinct pairs (s, a), (s, a') can appear in the same epoch for given state,
We would like to conclude with the remark that all the quantities used in our algorithm can be computed in a recursive manner. Consequently, similar to UCRL2, the space complexity of our algorithm turns out to be O(52 A) which is independent. T.
4 Regret Analysis
Below we state our main result.
Thcorem 1 Let D A D(M). With probability at least 1 - 8, 5 E (0, for arbitrory initial state s, the regret accumulated by the algorithm DUCRL2 over T >> 1 steps can be bounded above as follows.
T ( + 2d(SA)s
8T
Reg(s, DUCRL2, M,T) & 34DS AT
10g2
(8)
SA
Substäluling 8 1/T, we can therefore bound the expected regrel as,
8T
E [Reg(s, DUCRLU M,T)] < 68DS AT log (T)) + 2d(SA)3
log
(9)
SA
Theorem states that the regret accumulated by algorithm DUCRL2 O AT + d(SA)3) where Ö(-)
hides the logarithmic factors. (Jaksch et al., (2010) showed that the lower bound on the regret is D(VDSAT). As our setup is generalization of the setup considered in (Jaksch et al. 2010), the same lower bound must
6

---

Published in Transactions on Machine Learning Research (08/2023)
also apply to model. Morcover, if we consider an MDP instance where the rewards arrive with constant delay, d, then in the first d steps, due to lack of any feedback, each algorithm must obey the regret lower bound (()).. We conclude that the regret lower bound of our setup is [mmax (almax(DDSAA DSAT, d)) = +d) Although it matches the orders T, and of our regret upper bound, there is still room for improvement in the orders of D, and A.
4.1 Proof Sketch of Theorem
In this section, we provide brief sketch of the proof of Theorem
Step 1: The first step is rewrite the total regret as the sum of regrets accumulated over various epochs. Particularly, we show that with probability at least 1 - 8/1276/1 5 0 the following bound holds.
5T
87
Reg(s, DUCRL2, <
Rega +
log
8
Jom
AQ=
The term, Reg, can be defined the regret accumulated over epoch k (a precise definition is given in the appendix), and m is such that T lies in the (m - 1)th epoch. The additional term, Q2 appears due to the stochasticity of the observed reward instances. We now divide Q1 into two parts as follows.
Q
Reg, (M & M&) +
Rega 1M E MM)
2Q12
In order to bound Qu, it is important to have estimate of Pr(M _M&) which we obtain in Lemma 1 We would like to claborate that although the bound given in Lemma 1 is similar to that given in JJaksch et al. 2010), the proof techniques are different. In particular, here we account for the fact that the reward estimates, (*x(a))) ()) of the kth epoch, are potentially corrupted by delayed effects of past actions. We resolve this problem by proving the following inequality (see 32
Step 2:
(s a)
a)) a)(s,a) Oct<t
Σ (1:(s,)))l21(s =, =a) s (ax
(10)
Here the second term in the LHS denotes an estimate r(s, a) that the learner would have obtained had there been no delay in the observation of the reward instances. In other words, inequality (10 estimates the gap between an MDP with delayed observations, and hypothetical MDP without any delayed effects. Observe that the RHS of (10) also appears in the confidence radius (5 Therefore, the cost of incorporating delay is looser confidence in the reward estimates.
Step 3: Using Lemma Qu1 is bounded by VT with high probability (Lemma
+ J where the precise definition of the terms {JE)ee1,,2,) are given in the appendix B.2 Furthermore, also proves that the following bound holds with high probability.
Step 4: We now focus on bounding the other term, Q12- Lemma 3 shows that Reg, S JJ+ +
m JIIMM M =
VV+ (V
Σ
Dk (s. a) V /max (Nr (s,
kml (x.0)ESxA
where Ō(-) hides logarithmic factors and terms related to S.S.A. The other notations are identical that given in section g

---

Published in Transactions on Machine Learning Research (08/2023)
Step 5: The second term, J is bounded as follows.
S - Σ
(s,a)ESxA
Σ
(=(s,0))/((s,C)
fx(s,
Σ (s,0)E8xA
-
(8.4)E5xA
Notice that the first term can be bounded by invoking 55 The saine inequality also be used to bound the second term provided that M E MM which, as we have stated before, is a high probability event (Lemma) ! Using this logic, and some algebraic manipulations, we finally obtain the following high probability bound.
m
m E
(xss, a)
53(MeMa))+
(a + 2dSAA
(x,
Step 6: Finally, we obtain the following inequality related to the third term.
RI(M E Ma) 2 m
( a) V Nx
Σ
Σ
(a.0)ESXA
Step 7: Combining, we derive the bound stated below with high probability.
Q = Qn + Q12 S
J (1(M
R=1
vk(s, a)
=
VT
Vmax (N, + 2dS
k= (s,0)ESxA
Step 8: We conclude the proof using Lemma which states that,
8T
mmx (N) vx(s,a) S (V2+ 1)
m S SA Soloz
and
Σ
SA
k= (s.0)ESxA
4.2 Limitation
It is important to understand why approach works with partial anonymity but not with full anonymity, Fix state E S and epoch Recall from section 3 that no two distinct pairs (s,a), a), (s, a') can appear in the same epoch. Utilizing this property, we can write down the following relation for a pair (s, a) that appears in the jth epoch.
Σ 45TK
x+(s)
Σ DcTRt n22--r
Σ
Frmm (St, ar) =s)
Σ GSTcty41
||r(s, =s)
&
A &
(11)
Σ
Σ
Fr. (-))5 =
OCTSt
12:1111
The term, Ro denotes the sum of s-th components of all observed reward vectors within epoch j. Some portion of Ro is due to actions taken before the onset of the jth epoch. This past contribution denoted by the term, Ri. The rest of Rg is entirely contributed by the actions taken within epoch j. The term, R₂

---

Eq. 12 the first step in establishing (10 We would like to emphasize the fact that the term, R2 entirely contributed by (s,a) pairs appearing in epoch j (i.e., contamination from actions other than a). In other words, although our estimation, f(s, a) is based the contaminated observation Ro, we demonstrate that it Published in Transactions on Machine Learning Research (08/2023)
denotes the sum of all the rewards generated result of actions taken within epoch j. However, due to the delayed nature of the reward, some portion of R2 will be realized after the jth epoch. This spillover part is termed as R3. Using Assumption 2 we can write 0 & R1, Rs S d with high probability which leads to the following relation.
d S Ro R2 <d
(12)
is not far away from uncontaminated estimations. This key feature makes DUCRL2 successful despite having partial anonymity On the other hand, if rewards were fully anonymous, then 11 would have changed as follows.
Σ
EE (z)(s)=
E UCtRly nan--
E
Fram (s),
Σ
||r 0+)ll1
U SES
Ro
R
RR
(13)
Σ OCT
Σ
Tr. (8,
224 1-
Note that in 13 This makes algorithm ineffective in the presence of full anonymity.
the term, R2 mixer of contributions from various state-action pairs, unlike Rg in
11
Another limitation of our approach is that the delay parameter d is used as an input to Algorithm | One can therefore ask how the regret bound changes if an incorrect estimate, d of d is used in the algorithm. One can casily prove that d > d, then the regret bound changes to ODDV + d(SA)3). However, d < d, then Lemma no longer works, and consequently, the analysis does not yield any sub-linear regret.
5 Conclusion
In this work, we addressed the challenging problem of designing learning algorithms for infinite-horizon Markov Decision Processes with delayed, composite, and partially anonymous rewards. We propose algorithm that achieves near-optimal performance and derive a regret bound that matches the existing lower bound in the time horizon while demonstrating an additive impact of delay on the regret. Our work is the first to consider partially anonymous rewards in the MDP setting with delayed feedback.
Possible future work includes extending the analysis to the more general scenario of fully anonymous, delayed, and composite rewards, which has important applications in many domains. This extension poses theoretical challenges, and believe it is exciting direction for future rescarch. Overall, hope our work provides useful contribution to the reinforcement learning community and inspires further research on this important topic.
References
Mridul Agarwal and Vaneet Aggarwal. Blind decision making: Reinforcement learning with delayed obser- vations. Pattern Recognition Letters, 150:176-1888 2021.
Mridul Agarwal and Vaneet Aggarwal. Reinforcement learning for joint optimization of multiple rewards.
J. Mach. Learn. Res., 24:49:1 49:41, 2023. URL http::://jial..oorr/pppsss/////s .tmll
Mridul Agarwal, Qinbo Bai, and Vaneet Aggarwal. Regret guarantees for model-based reinforcement learning with long-term average constraints. In Uncertainly in Artificial Intelligence, pages 22 22-31. PMLR, 2022.

---

Published in Transactions on Machine Learning Research (08/2023)
Mridul Agarwal, Qinbo Bai, and Vaneet Aggarwal. Concave utility reinforcement learning with zero- constraint violations. Transactions on Machine Learning Research, 2023.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272. PMIR, 2017.
Ilai Bistritz, Zhengynan Zhou, Xi Chen, Nicholas Bambos, and Jose Blanchet Online exp3 learning in adversarial bandits with delayed feedback. Advances in neural information processing systems, 32, 2019.
Yann Bouteiller, Simon Ramstedt, Giovanni Beltrame, Christopher Pal, and Jonathan Binas. Reinforcement lcarning with random delays. In International conference on learning representations, 2021.
Nicol'o Cesa-Bianchi, Claudio Gentile, Yishay Mansour, and Alberto Minora. Delay and cooperation in nonstochastic bandits. In Conference Learning Theory, pages 605-622. PMLR, 2016.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-span-constrained exploration-eeppbitaaionn reinforcement learning. In International Conference on Machine Leurning, pages 1578 1586. PMLR, 2018
Manegueu Anne Gael, Claire Vernade, Alexandra Carpentier, and Michal Valko. Stochastic bandits with arm-dependent delays. In International Conference on Machine Learning, pages
PMLR, 2020.
Benjamin Howson, Ciara Pike-Burke, and Sarah Filippi. Optimism and delays in episodic reinforcement lcarning. In International Conference on Artificial Intelligence and Statistics, pages 6061-6094. PMLR, 2023.
Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, and Ken- Ichi Kawarabayashi. Delay and cooperation in nonstochastic linear bandits. Advances in Neural Informa- tion Processing Systems, 13:4872-4888 2020.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning.
Journal of Machine Learning Research, 11:1563 1600, 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
Tiancheng Jin and Haipeng Luo. Simultaneously learning stochastic and adversarial episodic mdps with known transition. Advances in neural information processing systems, 33:16557-16566, 2020.
Tiancheng Jin, Tal Lancewicki, Haipeng Luo, Yishay Mansour, and Aviv Rosenberg. Near-optimal regret for adversarial mdp with delayed bandit feedback. In Advances in Neural Information Processing Systems, 2022.
Tal Lancewicki, Shahar Segal, Tomer Koren, and Yishay Mansour. Stochastic multi-armed bandits with unrestricted delay distributions. In International Conference on Machine Learning, pages 5969-5978. PMLR, 2021.
Tal Lancewicki, Aviv Rosenberg, and Yishay Mansour. Learning adversarial markov decision processcs with delayed feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7281-7289, 2022.
Mohammad Pedramfar and Vaneet Aggarwal, Stochastic submodular bandits with delayed composite anony- mous bandit. foodback. arXiv preprint arXix:2303. 19604, 2023.
Ciara Pike-Burke, Shipra Agrawal, Csaba Szepesvari, and Steffen Grunewalder. Bandits with delayed, aggregated anonymous feedback. In International Conference Machine Learning, pages 4105 4113. PMLR, 2018.
Martin L Puterman. Markow decision processes: discrete stochastic dynomic programming. John Wiley & Sons, 2014.
10

---

Published in Transactions on Machine Learning Research (08/2023)
Kent Quanrud and Daniel Khashabi. Online learning with adversarial delays. Advonces in neural information processing systems, 28, 2015.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial markov decision processes. PMLR, 2019.
In International Conference on Machine Learning, pages
Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, pages 8604 8613. PMLR, 2020.
Tobias Sommer Thune, Nicolò Cesa-Bianchi, and Yevgeny Seldin. Nonstochastic multiarmed bandits with unrestricted delays. Advances in Neural Information Processing Systems, 32, 2019.
Claire Vernade, Alexandra Carpentier, Tor Lattimore, Giovanni Zappella, Beyza Ermis, and Michael Brueck- Linear bandits with stochastic delayed feedback. In International Conference on Machine Learning, PMLR, 2020.
pages
Siwei Wang, Haoyun Wang, and Longbo Huang. Adaptive algorithms for multi-armed bandit with composite and anonymous feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pagos 10210-10217, 2021.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo Weinberger. Inequalities for the deviation the empirical distribution. Hewlett-Pachee Packard Labs, Tech. Rep, 2003.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978 10989. PMLR, 2020.
Yuyang Zhang, Runyu Zhang, Gen Li, Yuantao Gu, and Na Li. Multi-agent reinforcement learning with reward delays. arXiv preprint arXiv:2212.011 01441, 2022.
Zhengyuan Zhou, Renyuan Xu, and Jose Blanchet. Learning in generalized linear contextual bandits with stochastic delays. Advances in Neural Information Processing Systems, 32, 2019.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for adversarial bandits with arbitrary delays. In International Conference on Artificial Intelligence and Statistics, pages 3285 3294. PMLR, 2020.
11

---

Published in Transactions on Machine Learning Research (08/2023)
A Extended Value Iteration
Algorithm Extended Value Iteration
Input: {d(s, a), a(s,a),f(s, P(s, (a)))E)))) 6>
Initialization: ug & fes +- 0, i it O, error
while error < do for S do
u++1(s) max aEA f(,, a) d(s,a)+
max E p( p()EP((.a) d'8
end for error max (s+1(s) us(ss} min (1 us,)s
.5S
.ES
i 1+1
end while
Here d(s, a) can be though of as the confidence radius as depicted in (5 whereas P(s,a) is the set of probability vectors that satisfy 6 Note that the stopping critoria for Algorithm is the following.
max(u:+1s)) [s(s)} - min minf4441(8) -s)) <E
(14)
In the context Algorithm we can take e ==1//t Theorem of (Jaksch et al. 2010) guarantees that the greedy policy deduced from the terminal utility vector u, of Algorithm 2 c-optimal in the sense of (7) if the of MDPs whose transition probability distribution p(-|s, a) lies in the confidence set P(s, a), and the reward function, a(s,a) lies at most d(s, a) distance away from the estimate f(s,a), comprises at least one MDP with finite diameter. As a consequence of this result, we can write the following corollary.
Corollary 1 Let, M be the collection of MDPs whose reward function r(.,)) and transition function, p(-),,) salisfy the following for given (f(s, ((s a), ((s, a) ())(sxx)
(r(s, f(s, a)l < d(s,a),
p(-1s,a) P(s,a) a)
If the true MDP, M lies in M, then Algorithm g always converges. Moreover, if indicates the terminal utility vector for a given > O, and V(s,a) E S SSS44 A,
(#()), ((1s,,()13.)))
arg max a.A, p(s)E((s.a)
(1s,a)+d(s,) + + Entdlos
(15)
S'ES
then the following incquality holds.
min p(s, #.. M) #ES
2
max MEM.Ees
p(s', T, M') Ad''-< -
where M an MDP with transition function, -) defined by 15 and reward function that obeys F(s,a) f(8, a) d(s. a), V(s, a) S A.
Corollary 1 casily established by observing that the true MDP, M is assumed to have finite diameter. It is also worthwhile to state that the complexity of updating the vector u; is O(S²A) as discussed in section 3.1.2 of (Jaksch et al. 2010
B Proof of Theorem
Let be such that fm-1 < T < tmm Clearly,
T fm
Σ
am
vx(s,a) (2.0)SSAA
Σ
(s.0)ESxA
12

---

Published in Transactions on Machine Learning Research (08/2023)
Using the above relation, the regret given in (3)
can be rewritten as,
T
Reg(s, DUCRL2 (M)
at)ll1
E
T Nm(s,a)r(s,a)
Σ
- -MM
Σ
Σ
(s),
(e,a)ESxA
(s,0)ESxA
1=1
T
r(s,))++
Σ
(m
(r((s), a))l
k= (e,a)ESxA
(8,0)E8xA
Regs
The term Regg be interpreted the regret accumulated epoch k. Observe that, for given history of state-action evolution Hy & {(s,, ((s,,,)))+ up to time T, the collection of random variables (st, 1 are mutually independent. Morcover,
T r(s,a) a) (s.))SxA
Σ at) = Σ
Σ
1(s = 8,
Σ
Nm(s,a)r(B,a))
(s.0)SxAA
Using Hoeffding 's inequality, we therefore obtain,
Pr Σ Nm(s,a)r(s,o))
Ellre(sa
5T log
8T
Hx
5
127
(s.a)SxAA
This implies that, with probability least 1 5/12T the following holds.
57
87
Reg(s, DUCRL2 M,T) Reg + + log
(16)
B.1 Regret bound on episodes where M lie outside the confidence set
Recall that M& is defined to be collection of MDPs that obey the confidence bounds 5 and G In this subsection, we calculate the regret contribution of the episodes where the true MDP M does not satisfy these bounds. The following lemma provides upper bound estimate of the probability that the true MDP, M does not lie in the confidence set, Mr.
8
Lemma 1 Pr (M M&)
15th
The proof of Lemma is relegated to Appendix C Although the final result in Lemma is the same as in (Jaksch et al., 2010), the proof techniques are quite different. In particular, we need to account for the lact. that reward estimates might be corrupted by contributions originating from various past actions. Using Lemma I the following bound can be obtained.
Lemma 2 Jaksch et al. 2010) With probability at least 1 - 8
Reg,1(M) $ MR) VT
(17)
We would like to mention here that although the definition of M₁ used our article different from that given (Jaksch et al.) (2010p, the above result still holds. This is mainly because the only property of Mg that is invoked to prove Lemma is provided in Lemma which is the same in (Jaksch et al. 2010
13

---

Published in Transactions on Machine Learning Research (08/2023)
B.2 Regret bound episodes where M lie inside the confidence set
Let & be the index of an episode where M E Ma and {ux {*) be the terminal utility vector obtained via extended value iteration at the kth episode. Define, WE {wx (s.ss)
wh (8) (8) maxses uk(s) + min.es (x(s)
2
Lemma 3
Jaksch et al. 2010) If l is such that M E Ma, then,
Reg S Σ
(s,s, #x(s))
Σ
(u (x())ux((()) (s(s)
SES
L'ES
Vx(s,))
Σ (s.a)ESxA
-(s. +2
E
vtx
(s,a)ESXA
where nk. Pk. Re are the reward, transition function, and policy of the MDP, Mg. Moreover,
8T + loga
8T SA
MMM e M&) < D
-
Tlg
2
(18)
2AAT
V12
(4 a) (s,0)E5xA (8, a8)
+D1
145 log
with probability at least 1- 8/
The only propertics of MMs that are used in the proof of Lemma are 16 and 7 which are the same as given (Jaksch et al., 2010). Note that, the term Jh defined Lemma can be bounded as follows,
J < Σ
(e(s,a))Fa(ssa)) a)(s
Σ (s,0)SSAA
() r(s,a))
(x.0)ESxA
(19)
7log 28AT
2dv a)
Σ
2vk(s, a)
Σ
max(NN((s,a).1) Es(s
(s,0)SSxA
(8.0)ESxA
where (a) applies the facts that M, M, .Ms and tx <T. Note that our algorithm enforces vx(s,a) S max(Na(s, a), 1}. Therefore, J can be further bounded as,
a)
2SAT
J Σ
14log
2d
Σ
Ex(s,a)
(20)
(s,0)ESxA V /
(8.0)
Observe that, Es(s, a) s m, v(s,a) ES X Therefore,
2SAT 8
(s 0) (s.a)eSxA V (aax(Na(s,a).1)
Σ H E Ma)
14log
Ad
(21)
Finally, injecting the inequality, max(NN a), tv. we obtain the following bound,
E M2) 2
E
Vk (x, a)
(22)
k= (x.a)ESXA V Ma
We the following lemma to simplify the upper bounds.
14

---

Published in Transactions on Machine Learning Research (08/2023)
Lemma 4
Jaksch et al. 2010)
The following inequalities hold true,
87
Σ SA log2
(23)
SA
Vk(ss, a)
S (v2 1)VSAT
(24)
(s.0)ESxA V (axx(N(
Using Lemmaa and combining least 1 8/127'.
18
20
22
we conclude that the following satisfies with probability at
5 DV
8T
87
Rega 1M E MA) &
T log
+ DSA log,
8
SA
(25)
(AT
87
7
=2(2++1) PV 14Slog
+
VSAT + 2d(5A)
loga
SA
B.3 Obtaining the Total Regret
Combining 16
27. and 25 we now establish that the following inequality is satisfied with at least
- 8/1276/ 6/1276/1 8/1276/1 = 5/47 probability.
T 7
8T 2
]²
DUCRL2, M,T) s 34DS, AT
2d(SA)
loga
SA
Taking a union bound on and noting that _r-2 5/4T < 8, we conclude the theorem.
C Proof of Lemma 1
The probability that the Lı-dcviation between the true and the empirical distributions of events over n
independent sample exceeds e can be bounded (Weissman al., 2003).
ne
(1B(() - p(-)li c) S (2' - exp (-2
(26)
2
Presume, without loss of generality that, aa(s, 1. In our case, inequality 26 can be utilised to obtain the following bound a)s A.
14S log (2Atz/0)
Pr
[[āx(118, p(-1s,))ll1
(8 a)
14S (2Alz/0)
Σ Pr -1((((1),)))(((ss))))
(27)
Denett
2x (-75 (2At+/0)) <
Σ
205
20S
O<nnct
O<tnctt
Inequality (a) is application of the union bound. Recall that E,(8, a) indicates whether the pair (s, a)
appears in the jth episode. Using this notation, we deduce that, if (s, a) for some (s, E S x A, then,
Σ
(s)
Σ 45T30
[|rr(s, a) =)
Σ
Σ
Fr.m (st, (1) =s)
GSTety
OcT T:21--7
(28)
Σ
Σ
Trim (8,, =))
12
15

---

Published in Transactions on Machine Learning Research (08/2023)
Using Assumption now write the following Vj.
Σ
Σ
Tr. (87, a=)1(s, = 3) - with probability
(29)
act<ty n
Combining 28
29
we can now write the following with probability 1,
Σ (+)
E
[|r = =) S
(30)
4STEE
Taking a sum over all episodes j E (1,... k- 1) where (s(,, = 1, we get the following inequality that is satisfied with probability 1.
Σ D
{=)))
E (r)(ss)))l11(s, a, = a) s dE
(31)
Using the definition of Fx (s, the above inequality can be rephrased as,
a, =a) d Es
as (s)
E ocrRre
(32)
NA (x(
Using Assumption [b), we can show that,
E
Σ
(1r((s a, = a) = r(8,a)
(33)
a)
oercte
Therefore, the following sequence of inequalities can be derived.
> d ax(s,a)
7 Llgg(2S
Pr (f)(s, - -r(s -
(s) +
(s,
(0)
Flog(2SAlx/9)
Pr
Σ
||r((s,))li11) 8, a, a) r(s,a)
(x( a)
2Nx(s,
octeR
(
7 7log (ttg(2AAt/0))
Σ Pr
I' (8. r(s,a) >
11
2n
O<nete
28
8
120SAt7
60S
Oenete
Inequality (a) is consequence 32 while (b) follows from the union bound. Finally, (c) utilizes Hoeffding's 's inequality together with Assumption Taa and [[c). Conjoining (27) and the above result, we establish the lemma.
16


Reviews:
[{"review_id": "zZjrVjdzza", "reviewer": "Reviewer_zAJN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper appears to consider a problem that was not previously studied in the RL literature;\n2. The presentation of the model and the algorithm is crystal clear.\n\nWeaknesses:\n1. I am not entirely convinced by the motivation of the problem. Isn't the introduction of \"states\" exactly for the purpose of addressing long-term/delayed feedback? For example, in advertisement, the user may make additional clicks before purchasing anything. It appears to me that the additional clicks can be encapsulated by the \"states\". Delay and composite feedback would be a problem in bandit because bandit does not have states. But for MDP, I do not understand why a better characterization of the states cannot resolve this issue.\n2. What is the technical novelty of the paper compared to existing works? Right now, the algorithm seems to be UCRL2 + bandit with delayed feedback. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper consider infinite horizon average reward RL with delay, composite, and anonymous feedback. The authors propose the DUCRL2 algorithm to address this problem and analyze its regret bound.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Following the above comments, the authors need to add the following elements:\n1. Give a concrete and detailed example where this model could apply, but usual MDP (possibly with function approximation) cannot. \n2. The paper needs to do a better job in stating the technical novelty. Otherwise, it reads like the technique is a simple combination of existing ones.", "broader_impact_concerns": "This paper is a theory paper and I am not immediately aware of any such concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lVcIffkEPa", "reviewer": "Reviewer_2tkA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The problem of delayed feedback is interesting and well-motivated, yet has received relatively little attention in the RL community.\n- The upper bound scales sublinearly in $T$ and linearly in the length of the delay. The former is known to be tight (although this work inherits suboptimal dependence on other parameters in the leading order term from [Jaksh et al., 2010]), and the scaling in delay is also likely not improvable.\n\nWeaknesses:\n- No lower bound is given showing the dependence on the delay is tight. While it does seem intuitively like the linear scaling is necessary, ideally this should be shown formally.\n- The algorithm requires knowledge of the maximum delay (or an upper bound on it) and no discussion is given as to how one should remove this assumption.\n- The analysis is very standard. The majority of it follows from [Jaksh et al., 2010], with the only modification being to handle the delayed feedback in bounding the reward estimation error. However, given that the algorithm has knowledge of the maximum delay, it is relatively straightforward to bound this.\n- While the problem of delayed feedback is well-motivated, it is not clear how well-motivated the model of feedback considered (partially anonymous feedback), and the feedback model feels rather strong.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies the problem of tabular reinforcement learning with delayed feedback. In particular, it considers the infinite-horizon setting, and “partially anonymous” feedback (where the learner can observe the total reward generated by any given state, but is not told which visitations to the state resulted in this reward). They propose a variant of the UCRL2 algorithm to handle this feedback, and prove a bound on its regret with leading-order term scaling similarly to the standard UCRL2 algorithm, and lower-order term scaling with the maximum delay. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical requested changes:\n- I believe it is important to provide a lower bound showing that linear scaling in $d$ is unavoidable. I suspect this should not be too hard to show (if the learner has no feedback after the first $d$ steps, they will be unable to learn anything, and so it should be straightforward to construct a family of instances for which any algorithm must suffer linear regret until $T > d$ on some instance).\n- I believe it is critical that the algorithm be extended to handle unknown $d$. Without this, as noted, the algorithm and result are almost immediate from the analysis given in [Jaksh et al., 2010]. Existing work on the problem of delayed feedback (for example, [Howson et al., 2023]) propose algorithms that do not require knowledge of the delay, so I believe it should be possible. If it is not possible, some discussion on why it is not possible should be given.\n- The related work section is very short and should be expanded. In particular, it should include some references covering the tabular RL literature more broadly.\n- Some discussion should be given justifying the partially anonymous feedback setting. In the examples used to motivate delayed feedback, is it reasonable to assume partially anonymous feedback is available?\n- In addition, while it is argued that partially anonymous feedback is necessary for the proposed algorithm, it is not argued that partially anonymous feedback is necessary for any algorithm. Some discussion of this should be provided.\n\nImportant but less critical requested changes:\n- The definition of $d$ is somewhat hard to parse and it is not clear where it comes from. I would suggest either adding additional discussion interpreting this quantity, or just stating all results in terms of $d_{\\max}$, and putting the result in terms of $d$ in the appendix. \n- $T(s’ | s,\\pi,M)$, used in the definition of $D(M)$, should be precisely defined.\n- I believe the references should go before the appendix.\n\nSeveral small notational things and typos:\n- Is there a reason that “$| \\cdot |_1$” is used for the $\\ell_1$ norm and not $|| \\cdot ||_1$, as is standard in the literature? Similarly, is there a reason that $\\Delta$ is used for regret instead of, e.g. $\\mathcal{R}$ or $\\mathrm{Reg}$? Neither of these are major issues and could be left as is, but it might improve readability if more standard notation is used.\n- Assumption 2 uses different notation for the reward than is used in the preliminary section (e.g. $r_{\\tau}(s,a)$ instead of $r_{t,\\tau}(s,a)$). It would be helpful if these could be made consistent. \n- After Assumption 2, I believe “the maximum delay is $d_m$” should be “the maximum delay is $d_{\\max}$”. Later in this same paragraph, “though” should be “thought”. \n- The line before equation (11) should end in a “:” not a “.”.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "LH2jq4WWCF", "reviewer": "Reviewer_tkbK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think this paper is an overall interesting paper and provides enough contribution.\n\n#### Strengths\n\n- The paper is well-written and easy to follow. The related works are adequately discussed. \n- The assumption of composite, delayed reward is interesting. The algorithm design is intuitive thus it can be extended to related tasks. \n\n#### Weakness\n\n- There lacks some intuition behind Assumption 2 (delayed reward). It's true that a constant delay $d_m$ satisfies this assumption, but it might be better to discuss why this assumption is defined by a double summation.\n- I wonder about the space efficiency of the algorithm since the algorithm needs to maintain several composite rewards (e.g. $\\bm x_\\tau$) in the history. In contrast, In UCRL2, we can reduce the space complexity by only maintaining the summation of the reward $r$.\n- The algorithm needs to know the delay $d$, which might be hard to estimate unless the delay is a constant.\n- I found the definition of the delayed reward confusing, or maybe the authors missed some definitions of the notations. For example, $r_{t, \\tau}$ is defined but $r_\\tau$ in Assumption 2 is not defined, should it be something like $r_{0, \\tau}$ or do I miss some definitions? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the MDPs with delayed and composite rewards. In such a setting, the agent can only observe an aggregate of the historical rewards (on a specific state, in this paper). The author provides a new algorithm based on the UCRL2 for tabular MDPs. The new algorithm consists of a larger confidence bonus regards the delay $d$. The authors provide a sublinear regret bound for averaged MDPs with infinite horizons.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please see the aforementioned weakness.\n- It will be beneficial to understand the delayed reward setting if the authors can provide some counter-examples regards Assumption 2.\n- What if the algorithm has a wrong delay parameter $d$?\n- Typos: Right after Assumption 2: $d_m$ or $d_\\max$?", "broader_impact_concerns": "I do not have any concerns regarding the broader impact of this paper", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all agree that the claim is well supported and the paper is of interest to some of the TMLR readers.

The main concern is about the assumptions made in the work, notably the partially anonymous reward feedback and the knowledge of delay. Some of the reviewer argues that with the current assumptions, the extension reduces the overall technical interest of the work. It is encouraged that the authors dedicate more discussions around this aspect.
 
Given the overall comments and recommendations from the reviewers, I am happy to support an accept decision.
Decision: Accept (poster)