Reinforcement Learning with Segment Feedback
Authors: Yihan Du
Anna Winnicki
Gal Dalal
Shie Mannor
R. Srikant
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement learning (RL)
segment feedback
binary feedback
sum feedback
Primary area: reinforcement_learning

Abstract: Standard reinforcement learning (RL) assumes that an agent can observe a reward for each state-action pair. However, in practical applications, it is often difficult and costly to collect a reward for each state-action pair. While there have been several works considering RL with trajectory feedback, it is unclear if trajectory feedback is inefficient for learning when trajectories are long. In this work, we consider a model named RL with segment feedback, which offers a general paradigm filling the gap between per-state-action feedback and trajectory feedback. In this model, we consider an episodic Markov decision process (MDP), where each episode is divided into $m$ segments, and the agent observes reward feedback only at the end of each segment. Under this model, we study two popular feedback settings: binary feedback and sum feedback, where the agent observes a binary outcome and a reward sum according to the underlying reward function, respectively. To investigate the impact of the number of segments $m$ on learning performance, we design efficient algorithms and establish regret upper and lower bounds for both feedback settings. Our theoretical and experimental results show that: under binary feedback, increasing the number of segments $m$ decreases the regret at an exponential rate; in contrast, surprisingly, under sum feedback, increasing $m$ does not reduce the regret significantly.

Reinforcement Learning with Segment Feedback
Yihan Du Anna Winnicki?
Gal Dalal
Shie Mannor 43
R. Srikant
Abstract
In classic RL, when the agent takes an action in state, the environment will provide a reward for this state-action pair. However, in real-world applications, it is often difficult and costly to collect a reward for each state-action pair. For example, in robotics, when instruct robot to scramble eggs, it is hard to specify reward for each individual action. In autonomous driving, it is difficult and onerous to evaluate each action, considering multiple criteria including safety, comfort and speed.
Standard reinforcement learning (RL) assumes that an agent can observe a reward for each state- action pair. However, in practical applications, is often difficult and costly to collect a reward for each acttin pair. While there have been sev- eral works considering RL with trajectory feed- back, it is unclear if trajectory feedback is in- efficient for learning when trajectories are long. In this work, we consider a model named RL with segment feedback, which offers a general paradigm filling the gap between per-state-action feedback and trajectory feedback. In this model, consider episodic Markov decision process (MDP), where each episode is divided into m segments, and the agent observes reward feed- back only at the end of each segment. Under this model, we study two popular feedback settings: binary feedback and sum feedback, where the agent observes binary outcome and reward sum according to the underlying reward function, respectively. To investigate the impact of the num- ber of segments m on learning performance, we design efficient algorithms and establish regret upper and lower bounds for both feedback set- tings. Our theoretical and experimental results show that: under binary feedback, increasing the number of segments m decreases the regret an exponential rate; in contrast, surprisingly, under sum feedback, increasing m does not reduce the regret significantly.
Motivated by this fact, there have been several works that consider RL with trajectory feedback (Efroni al., 2021; Chatterji et al., 2021). In these works, the agent observes reward signal only at the end of each episode, instead of at each step, with the signal indicating the quality of the trajectory generated during the episode. While these works mitigate the issue of impractical per-step reward feedback in classic RL, the relationship between the frequency of feedback and the performance of RL algorithms is unknown. In particular, if for example get feedback twice in each trajectory, does that significantly improve performance over once per trajectory feedback?
To answer this question, we study a general model called RL with segment feedback, which bridges the gap between per-state-action feedback in classic RL (Sutton & Barto, 2018) and trajectory feedback in recent works (Efroni et al., 2021; Chatterji et al., 2021). In this model, we consider an episodic Markov decision process (MDP), where episode is equally divided into m segments. In each episode, at each step, the agent first observes the current state, and takes an action, and then transitions to a next state according to the transition distribution. The agent observes a reward signal at the end of each segment. Under this model, we consider two reward feedback settings: binary feedback and sum feedback. In the binary feedback setting, the agent observes binary outcome (c.g., thumbs up/down) generated by a sigmoid function of the reward on this segment. In the sum feedback setting, the agent observes the sum of the rewards over this segment. our model, the agent needs to learn the underlying reward function (i.e., the expected reward as a function of states and actions) from binary or sum segment feedback, and maximize the expected reward achieved. While Tang et al. (2024) also studied this segment model before (they called it RL from bagged reward), their work is mostly empirical, and does not provide theoretical
Reinforcement learning (RL) is class of sequential decision-making algorithms, where agent interacts with an unknown environment through time with the goal of max- imizing the obtained reward. RL has variant applications such as robotics, autonomous driving and game playing.
Universitty of Illinois at Jrbana-Champaiin "Stanford University 'NVIDIA Research "Technion. Correspondence to: Yihan Du <duyihan 1996 gomil.com>, R. Srikant
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Reinforcement Learning with Segment Feedback
guarantees for algorithms and rigorously reveal the influence of segments on learning.
SegBiTS-Tran for known and unknown transitions, re- spectively. We provide regret upper and lower bounds which depend on exp( Hemes), ), where H is the length 2m
This model is applicable to many scenarios involving hu- man queries. For instance, in autonomous driving, driving trajectory is often divided into several segments, and human annotators are asked to provide feedback for each segment, e.g.. thumbs up/down. Compared to state-action pairs or whole trajectories, segments are casier and more efficient to evaluate, since human annotators can focus on and rate be- haviors in each segment, e.g., passing through intersections, reversing the car and parking.
of each episode, and T'ax is a universal upper bound of rewards. Our results exhibit that under binary feed- back, increasing the number of segments m signifi- cantly helps accelerate learning.
3. For sum feedback, we devise algorithms E-LinUCB and LinUCB-Tran which achieve near-optimal regrets in terms of И and m. We also establish lower bounds to validate the optimality, and show that optimal regrets do not depend on m. Our results reveal that surpris- ingly, under sum feedback, increasing the number of segments does not help expedite learning much.
In this segment model, there is an interesting balance be- tween the number of segments (queries to humans) and the collected observations, i.e. we desire more observations, but
we also want to reduce the number of queries. Therefore, in
4. We develop novel techniques which can be of indepen- dent interest, including the KL divergence analysis to derive exponential lower bound under binary feed- back, and the use of E-optimal experimental design in algorithm E-LinUCB to refine the eigenvalue of the covariance matrix and reduce the regret.
this problem, it is critical to investigate the trade-off between the benefits brought by segments and the increase of queries, which essentially comes down to a question: How does the number of segments m impact learning performance?
To answer this question, we design efficient algorithms for binary and sum feedback settings in both known and un- known transition cases. Regret upper and lower bounds provided to rigorously show the influence of the num- ber of segments on learning performance. We also present experiments to validate our theoretical results.
1. Related Work
In this section, we briefly review prior related works.
Algorithms and analysis for classic RL were well studied in the literature (Sutton & Barto, 2018: Jaksch et al., 2010; Azar et al., 2017; Jin et al., 2018: Zanette & Brunskill, 2019). Tang et al. (2024) proposed the RL with segment feedback problem (they called it RL from bagged rewards), and de- signed a transformer-
Note that studying RL with equal segments is an impor- tant starting point and serves as a foundation for further investigation on more general models and analysis for RL with unequal segments. Even under equal segments, this problem is already very challenging: (i) This problem can- not be solved by applying prior trajectory feedback works, e.g., (Efroni et al., 2021), since they use the martingale property of subsequent trajectories in analysis, while sub- sequent segments are not a martingale due to dependency among segments within a trajectory. (ii) In prior trajectory feedback works (Efroni et al., 2021; Chatterji et al., 2021), there exists gap between upper and lower bounds for sum feedback, and there is no lower bound for binary feedback. This fact poses a significant challenge for us when trying to understand the influence of the number of segments m on learning performance.
algorithm. However, their work is mostly empirical and does not provide theoretical guaran- tees. Gao et al. (2025) considers RL with bagged decision times, where the state transitions are non- Mon-Maaoov within bag, and a reward is observed at the end of the bag. But the focus of (Gao et al., 2025) is to handle the non-Marke non-Markovian state transitions within a bag using a causal directed acyclic graph, instead of investigating how to infer the reward func- tion of state-action pairs from bagged rewards like us. In addition, the best of our knowledge, there is no existing work that rigorously quantifies the influence of segments on learning performance.
Our work overcomes the above challenges and makes con- tributions as follows.
There are two prior works (Efroni et al.. 2021; Chatterji et al., 2021) studying RL. with trajectory feedback, which are most related to our work. Efroni et al. (2021) investi- gated RL with sum trajectory feedback, and designed up- per confidence bound (UCB)-type and Thompson sampling (TS)-type algorithms with regret guarantees. Chatterji et al. (2021) studied RL with binary trajectory feedback, but con- sidered a different formulation for binary feedback from ours. Specifically, in their formulation, the objective is to find the policy that maximizes the expected probability of generating feedback 1, and their optimal policy can be non-
1. We study a general model called RL with segment feed- back, which bridges the gap between per-state-action feedback in classic RL and trajectory feedback seem- lessly. Under this model, we consider two feedback settings: binary feedback and sum feedback.
2. For binary feedback, we design computationally- efficient and sample-efficient algorithms SegBiTs and
2

---

Reinforeement Learning with Segment Feedback
Markovian due to the non-linearity of the sigmoid function; In our formulation, our objective is to find the optimal pol- icy under the standard MDP definition by inferring rewards from binary feedback, and thus we consider Markovian poli- cies. The algorithms in (Chatterji et al., 2021) are either computationally inefficient or have suboptimal regret order due to the non-linearity of their objective and direct maxi- mization over all non-Marte non-Markovian policies. Our algorithms computationally efficient by adopting the TS algorithmic style and efficient MDP planning under Markovian policies. Our regret results cannot be directly compared to those in (Chatterji et al., 2021) due to the difference in formulation.
The optimal policy is defined as x² argmax, all 8 and h E [HT]. For any S and h (H). denote V V (8).
x (s) for
The process of RL with segment feedback is as follows. In each episode k, the agent chooses a policy xh at the beginning of this episode, and starts from of ~ p. At each step h E [H] the agent first observes the current state s%; and takes an action a = (s according to her policy, and then transitions to a next state s/+11 p(-1s% af,)
Each episode is equally divided into segments, and each segment is of length H. For convenience, assume that H mi is divisible by m. For any k > 0 and i E [m], let 7² = (s .e......8. 8/. af))) denote the trajectory episode k. and si
Moreover, different from (Efroni et al., 2021; Chatterji et al., 2021), we study RI. with segment feedback, which allows feedback from multiple segments within a trajectory, with per-state-action feedback and trajectory feedback as the two extremes. Under sum feedback, we improve the result in (Efroni et al., 2021) by factor of V H using experimental design, when the problem reduces to the trajectory feed- back setting. Under binary feedback, we propose Tsy-tyle algorithms which are computationally efficient, and build a lower bound to reveal an inevitable exponential factor in the regret bound, which is novel to the RL literature.
Tf (s
m (1-1))111' d i-th segment of the trajectory in episode k:
m 1' at denote the m
m (i-1))+)
For any trajectory or trajectory segment т, 0 E R|SIA|| denotes the vector where each entry Φ (s, a) is the number of times (s, a) is visited in T. For any policy nT, d" e R|S||A| denotes the vector where each entry 6" (s. a) is the expected number of times (s, a) is visited in an episode under policy n, i.c.
H Σ
Our work is also related to linear bandits (Abbasi-Yadkon et al., 2) and logistic bandits (Filippi et al., 2010; Faury et al., 2020; Russac et al., 2021), and uses analytical tech- niques from that literature.
('(8aa=== = E
1 1
8, a1)
In our model, the agent observes reward feedback only at the end of each segment, instead of each step as in classic RL. We consider two reward feedback settings as follows.
2. Formulation
In this section, we present the formulation of RL with binary and sum segment feedback.
Binary Segment Feedback. Denote the sigmoid function by ulz) := [+exp(-x) for any R. In the binary segment feedback setting, in each episode k. at the end of each segment i E [mm], the agent observes a binary outcome
episodic MDP denoted by Here is the state space, and A is the action space. H is the length of each episode. r : S x A + [-rmax maax] is an unknown reward function, where rmax > 0 is universal constant. Define the reward parameter 0= : [r(s, ()ss)))(e)))xxAAA E RRSSI--1. p: S x A - As is the transition distribution. For any (s, (s,a,s') E S x x S, p(s'ls, a) is the probability of transitioning to s' if action a is taken in state s. p E As is an initial state distribution.
We consider an
M(S,A, A, p).
f 1, 3 = 0,
w.p. =((
w.p. 1 - (1((((t)))T))
Note that our formulation is different from that in prior work for binary feedback (Chatterji et al., 2021). Chat- terji et al. (2021) aim to find the policy that maximizes the expected probability of generating feedback 1, i.c.. max, Ex-x,p ) (T()))"TT))))))))))")()) f")), where the optimal policy can be non-Markovian due to the non-linearity of x()). In con- trast, we aim to find the optimal policy under the standard MDP definition, i.e., max, E.<r",(("")) O'', by inferring reward 0r from binary feedback, and thus we consider Markovian policies. Both formulations have value and are applicable in different contexts. In particular, our formu- lation is better suited to situations where we want to solve an MDP but only get binary segment feedback. Under our formulation, we design TS-type algorithms with confidence
A policy π: : S x [H] + is defined as a mapping from the state space and step indices to the action space, that (s) specifies what action to take in state at step h. For any policy n, h E [H] and (s, a) E S x A. let VT (s) be the state value function, and (s, be the state-action value function, which denote the cumulative expected reward obtained under policy æ till the end of an episode, starting from and (s,a) at step h. respec- tively. Formally, VTT ;= E r(s,, de)s = s, and (x,a) == E| " r(se, 18) 8, = a, m..
3

---

Reinforcement Learning with Segment Feedback
bonuses added on 0* clement-wise to achieve computational efficiency, which cannot be done without sacrificing the re- gret order under the formulation of (Chatterji et al., 2021).
Algorithm 1 SegBiTS
1: Input: 6,8' = 3. a exp( Hrmax
+exp(
Hrmms + m
m
2, X.
2: for k = 1, K do
Sum Segment Feedback. In the sum segment feedback
3: Ōn-1
argming - -( E (up
setting, in each episode k, at each step h, the environment generates an underlying random reward R = r(sh. s%) + noise, and
log(u((0rt) TTO) + (1 1x') - log(1
u((Ø" #/ TB))) - 211101B3
Eh where sx is zero-mean and independent of transition. At the end of each segment e [m]. the agent observes the sum of random rewards
ΣK-1 t EK11 1 (Ø T + adI
4:
5: Sample EN ~ NN a - r(k - 1)2 -x-1), where
v(k 1) is defined in Eq. (1)
R
R(sE; at) = (05 TO
Σ
6:
0g + -
7: * + argmax ((=") (
H
17+1
1)+1
Play episode is with policy x². Observe trajectory /
and binary segment feedback (v² J/m
Under sum feedback, when m = H. our model degenerates to classic RL (Azar et al., 2017: Sutton & Barto, 2018). When m 1, the above two settings reduce to the problems of RL with binary (Chatterji et al., 2021) and sum trajectory feedback (Efroni et al., 2021), respectively.
9: end for
or have a O(K3) regret bound, SegBiTS is both computa- tionally efficient and has a O(vK) regret bound.
Algorithm 1 presents the procedure of SegBiTS. Specifi- cally, in each episode k. SegBiTs first employs MLE with past binary reward observations to obtain the estimated reward parameter 0--1 (Line 3). Then, SegBiTs calcu- lates the feature covariance matrix of past segments ΣŞ-1 (Line 4). After that, SegBiTs samples noise & from Gaus- sian distribution (N, a v(k- 1)2 xT-1) (Line 5). Here a is universal upper bound of the inverse of the sigmoid function's 's derivative. For any k > 0, we define
In our model, the agent needs to infer the reward function from sparse and implicit reward feedback. Let K denote the number of episodes played. The goal of the agent to minimize the cumulative regret, which is defined as
K R(K)= = (VT((s)) - (s1)). (s)).
We note that to the best of our knowledge, the fact that one gets extremely coarse information about the sum reward in the binary feedback case makes it impossible have common analysis for both feedback models.
v(k) = mvd
Hrmax v V
H mv
1+
H
H Hrmax VISIIA w(k) + m²x w())2
H²
+
(1)
3. Reinforcement Learning with Binary Segment Feedback
m
and
In this section, we investigate RL with binary segment feed- back. To isolate the effect of segment feedback from tran- sition model learning, we first design a computationally- efficient and sample-efficient algorithm SegBiTS for the known transition case, and establish a novel lower bound to exhibit the indispensable exponential dependency in the result under binary feedback. Then, we further develop an algorithm SegBiTS-Tree -rrn with carefully-designedd transition bonuses for the unknown transition case.
((k) = vX (T VISIIAA| (Tmaa///SSLA| +
7/1
1
2)
|S||A||
log 4
(1 1+ 8
H²k
(2)
VX
4[5]||||xm)
(k) is the confidence radius factor of the MIE estimate dg. With high probability, we have TØ - x 6ul <
Va- <<k))l where & is the visitation indicator of any trajectory (Lemma C.7 in Appendix C.I).
Adding noise &N to 0 SegBiTs obtains a posterior re- ward estimate 02 (Line 6). Then, it computes the optimal policy x² under reward 0x. i..., argmax, (
3.1. Algorithm SegBiTS for Known Transition
Building upon the Thompson sampling algorithm (Thomp- son, 1933), SegBiTS adopts the maximum likelihood esti- mator (MLE) to learn rewards from binary feedback, and performs posterior sampling to compute the optimal policy. Different from prior trajectory feedback algorithms (Chat- terji al.,, 2021) which are either computationally inefficient
(Ø*)TØe 6j (Line 7). Note that this step is computationally efficient, which can be casily solved by any MDP planning algorithm, e.g., value iteration, by taking 6/ as the reward function. After obtain- ing Th. SegBiTs plays episode k and observes trajectory * and binary feedback (vt ( 1m on each segment (Line 8).
4

---

Reinforcement Learning with Segment Feedback
Now we provide regret upper bound for SegBiTs.
small factor co in exp(-). Theorem 3.2 reveals that when the number of segments increases, the regret indeed de- creases at an exponential rate. In addition, this lower bound also holds for the unknown transition case, by constructing the same problem instance as in its proof.
Theorem 3.1. With probability least 1 for any K > 0, the regret of algorithm SegBiTS is bounded by
Hrmax 2m
R((K) = exp
v(K)
To the best of our knowledge, our lower bound for binary feedback and its analysis are novel in the RL literature. In the analysis, we calculate the KL divergence of Bernoulli distributions with the sigmoid function being in their pa- rameters. Then, we employ Pinsker's inequality and the fact that p'(x) μz (1=((z)) to build connection be- tween the calculated KL. divergence and μz( (Hrmax) ). Since I (z)
(V (VKm|SILA
H² mad
K at
Km||]|A) max
+ H 1
In this result, the dependency on (S], |A| and H are |S] [-418 and exp( (frma 2m )HF respectively. Our focus here is to reveal the exponential dependency on Hruus in the regret bound under binary feedback, instead of pursuing absolute tightness of every polynomial factor. Since the exponential factor is usually the dominating factor, this result implies that as the number of segments m increases, the regret decays rapidly. Thus, under binary feedback, increasing the number of segments significantly helps accelerate learning.
-epp= x)+ contains an exponential factor, we can finally derive an exponential dependency in the lower bound. Below we give a proof sketch of Theorem 3.2, and defer a full proof to Appendix C.2.
Proof Sketch. Consider an instance as follows: there are bandit states $ Sn (i.e., there is an optimal action and multiple suboptimal actions), a good absorbing state Sn+1 and bad absorbing state sn+2- The agent starts from 5n with equal probability π. For any i E [n]. in state 8;, under the optimal action a,, the agent tran- sitions to 8n+1 deterministically, and r(s;; az) = T'axi Under any subop- timal action a,"h, the agent transi- tions to 8n+2 de- terministically, and r( = (1
The intuition behind this exponential dependency is that when the reward scale x Hrnax is large, the binary feed- back is generated from the range where the sigmoid function u(z)= = [+oxp(-z)) =2) is flat, i.c., the derivative of the sigmoid function (1)) is small. Then, the generated binary feedback likely always or always and it is hard to distinguish between good action and a bad action, leading to higher regret; On the contrary, when the reward scale is small, the binary feedback is generated from the range where the sigmoid function μ(r) is steep, i.e., pxx is large. Then, the generated binary feedback is more dispersed to be or 1, and it is easier to distinguish between good action and a bad action, leading to a lower regret. In other words, the regret bound depends on the inverse of the sigmoid function's 's derivative yd (x) exp(x))exp(-a)))
m
r(s, a) mmax
r(s, ((s.aa"")) = (1 =) at transttion to 8,41 aidh transition to Sn+2
Hrmax m
+ wp
S1
8u+1
wpp 1
$2
r(w+1rr) -Faxx
m) where e E (0. 2) is a param- eter specified later. For all actions E
S
wpp
Sn
r(Sa2r)) = (1 - E)Fmax
Figure I. Lower bound instance.
A, r($,+1,0) = Tmax and r(5 =1 (1-E)) =)T
3.2. Regret Lower Bound for Known Transition
Then, the KL divergence of binary observations between the optimal action and suboptimal actions in an episode is
Below we provide a lower bound, which firstly demonstrates the inevitability of the exponential factor the regret bound for RL with binary feedback.
Σ
KL B
(1 - 8) HT
|
HT m
m
Theorem 3.2. Consider RL with binary segment feed- back and known transition. There exists a distribution
11
(1 (1-e)
11
(Trmax)) m
2
m
of instances where for any Cn E (0, when K Z exp( Hrmax) 415]|AAmm the regret of any algorithm must be "H
m
Hrusa Trc
n² (1 (1=E) Hrmus
(a Mrans
(b) S m
s a( (eexp (G= %0)
HT Hrmax
VISI|Amk)
pl HTmax
-0)
m
Here B(p) denotes the Bernoulli distribution with parameter
p. Incquality (a) uses the facts that (L() [B(g)) <
Theorem 3.2 shows that under binary feedback, the expo- nential dependency on Hraax in the result is indispensable,
(p-g)² and p'(x)) ((=))(1 ====)) Inequality (b) is due
9(1g)
m
to that μ (zxz) is monotonically decreasing when x > 0.
and the exp( Mrmus) ) factor in Theorem 3.1 nearly matches 2m
the exponential factor in the lower bound up to an arbitrarily
Furthermore, we consider the reward scale H max in each
5

---

Reinforcement Learning with Segment Feedback
episode, and the enumeration over each bandit state sy (i E (nl) and each possible optimal action oj E A in the lower bound derivation. Then, following the analysis in (Auer et al., 2002), to learn the difference between the optimal action and suboptimal actions, the agent must suffer a regret
the regret of SegBiTS-Trai significantly decreases. Com- pared to SegBiTs, the regret of BegBiTs-Tran has ad- ditional polynomial term in [S], |A], H and vK, which is incurred due to learning the unknown transition distribution.
4. Reinforcement Learning with Sum Segment Feedback
Hr Hmmax m|Ai
VEq. (3)
v ViAlrem
jel (Hrmax) m
In this section, we turn to RL with sum segment feed- back. Different from prior sum trajectory feedback algo- rithm (Efroni et al., 2021), which directly uses the least squares estimator and has a suboptimal regret bound, we develop an algorithm E-LinUCB for the known transition case, which adopts experimental design perform an initial exploration and achieves a near-optimal regret with respect to H and m. To validate the optimality. we further establish regret lower bound. Moreover, we design an algorithm LinUCB- Tran equipped with a variance-aware transition bonus to handle the unknown transition case.
= Ω
1l ((1 - E) Hrmox)
Recall that n² (x)
Let = O (
For any constant co E (0, 2 ), letting K large enough (s small enough) to satisfy e S co, then the regret is
Hrmax
Ω
V K A Almmy exp (1-22) 2s)
= (=(KKK/]AA exp (2 co
Hrmax m
))- 0
4.1. Algorithm E-LinUCB for Known Transition
If we regard visitation indicators o= as feature vectors and 0 as the reward parameter, RL with sum segment feedback and known transition is similar to linear bandits.
3.3. Algorithm SegBiTS-Tran for Unknown Transition
Now we extend our results to the unknown transition case.
We develop an efficient algorithm SegBiTS-Tran for binary segment feedback and unknown transition. SegBiTS-TVe includes a transition bonus ph-11 in posterior reward esti- mate 02. and replaces visitation indicator ot by its estimate 2ズ-z. For any (s, a), ( a) is the expected number of times (s, a) is visited in an episode under policy on empirical MDP Px-1. where Pk- is the empirical estimate of transition distribution p. Then, SegBiTS-Tran computes the optimal policy via argmax, 1 T 8%. which can be efficiently solved by any MDP planning algorithm with tran- sition distribution pk-1 and reward 0z. We defer the details of SegBiTs- -ran to Appendix C.3, and present its regret performance as follows.
Building upon the classic linear bandit algorithm LinUCB (Abbasi- Yadkori et al., 2011). our algorithm E-LinUCB performs the E-optimal design (Pukelsheim, 2006) to conduct an initial exploration. This scheme en- sures sufficient coverage of the covariance matrix and fur- ther sharpens the norm under the inverse of the covariance matrix, which enables an improved regret bound over prior trajectory feedback algorithm (Efroni et al., 2021).
Algorithm shows the procedure of E-LinUCB. Specif- ically, E-LinUCB first performs the E-optimal design to compute a distribution the minimum eigenvalue of the feature covariance matrix Exen (( Tm sume that there exists a policy distribution w under which this matrix is invertible. Then, E-LinUCB calculates the number of samples Ko for initial exploration according to the optimal value of the E-optimal design (Line 3).
policies w", which maximizes
[ ( (Line 2). We as-
anyaayyaaaao Theorem 3.3. With probability least 1 1 5. for any K >> O, the regret of algorithm SegBi Te-Trann is bounded by
HTmax
u(K) UIKKAS
exp
2m
Then, in Line 4, E-LinUCB calls a rounding procedure ROUND (Allen-Zhu et al., 2021) to transform sampling distri- bution w" into discrete sampling sequence (s'1...,, .....,,=Ko) =K)), which satisfies (see Appendix B for more details of ROUND)
H²
K
Km|S|iAA|
max
1
H
max'
ad
+ (M(K))
SIAA
+ Hr maxx
m
Σ
Br BRNER
(
Similar to algorithm SegBiTS (Theorem 3.1), the re- gret bound of algorithm SegBiTS-Tren also has a factor exp( Hrmax) ). When the number of segments m increases,
< <(++7)
Kr [1.
" (T)
Σ
E Eran 1 (dt))
FE
6

---

Reinforcement Learning with Segment Feedback
Algorithm 2 E-LinUCB
H 1: Input: 5,6' 3. i
rounding procedure ROUND, rounding approximation parameter y == 10 B(k)
I|S|IA| log(1 M|S||A|m ) 2 log( (v) + 'max v || Vk 0.
kH?
2: Let w E An and =" the optimal solution and optimal value the optimization:
min wEAn
Σ xEll
w(T)
Σ
E T 1 (0T)
(4)
3: Kg f [ma( + (=*) H* log( 215 (IIAA 17
4: br!,...,Tkk) t ROUND (>i=1 E Briw (OT
Teen ,,,, Ko)
5: Play Ka episodes with policies n ....., ,,. Observe trajectories rf ...... Ko and rewards {R; (m)) I {RR ===1
6: for k = Ko + +,,.... I....,K K do
7: Ox-1 + (A Et Ei=1 Serl (177" TT- E or R
8: E X Σ - Di=1 ot (ort) )
9: Th + argmax ((²*) 0k-1 + 3(k 1). | (())-)))))
10: Play episode l with policy x². Observe trajectory 7 and sum segment feedback {R ym
11: end for
After that, E-LinUCB plays Ko episodes with (T (mt,..., "....,,ko Ka) to perform initial exploration (Line 5). Owing to the E-optimal design, the covariance matrix of initial explo- ration Σx, has an optimized minimum eigenvalue, and then || I(())-))- has a sharp upper bound for any > Ko- This is the key to the optimality of E-LinUCB.
When the number of segments m increases, while we obtain more observations, the segment features Ø=. contributed to covariance matrix Σ3 shrink, which makes the reward estimation uncertainty (((,)))))) inflate. When we focus the estimation performance of the expected reward sum of an episode, these effects cancel out with each other, and the regret result is not influenced by distinctly.
In each episode k > Ko. E-LinUCB first calculates the least squares reward estimate 0 using past reward observa- tions and covariance matrix ΣĄ-1 (Lines 7-8). Then, it computes the optimal policy with reward estimate Ū2-1 and reward confidence bonus | (Line 9). E-LinUCB plays episode l with the computed optimal policy π², and collects trajectory n and reward observations on each seg- ment { im (Line 10). Below we present a regret upper bound for algorithm E-LinUCB.
When m 1, our problem reduces to RL with sum trajec- tory feedhack (Efroni et al., 2021), and our result improves theirs by a factor of / HH and achieves the optimality with respect to H. This improvement comes from the fact that we conduct the E-optimal design and perform an initial ex- ploration to guarantee that " (( S VX as used in (Efroni et al., 2021).
1, instead of
Next, we study the lower bound to see the number of segments m really does not influence the regret bound much.
Jny Theorem 4.1. With probability at least 1 8. for any K >> O, the regret of algorithm E-LinUCB is bounded by
4.2. Regret Lower Bound for Known Transition
((++
Hr Hrmax
1
S (SIAAVHH HK log
|S|
We establish lower bound for RL with sum segment feed- back and known transition as follows.
|S||A| 6
+ 2= log
+ |I|II|
Theorem 4.2. Consider RL with sum segment feedback and known transition. There exists a distribution of instances where the regret of any algorithm must be
Surprisingly, under sum feedback, when the number of segments m increases, the regret bound does not decrease significantly, e.g., at a rate of A or 1. While this looks sur- prising at the first glance, we discover an intuition through analysis: The performance in RL is measured by the ex- pected reward sum of an episode, namely, we only need to accurately estimate the expected reward sum of episode.
Ω (VIS)AAHHK
Theorem 4.2 demonstrates that our regret upper bound for algorithm E-LinUCB (Theorem 4. is optimal with respect to and m when ignoring logarithmic factors. addition, this lower bound corroborates that the number of segments

---

Reinforcement Learning with Segment Feedback
K Episodes
SegBiTS SegBiTS-Tran
Cumulative Regret K Episode
6931
E-LinUCa LinUCB-Tran
Cumulative Regret of K Episodes
700
LinUCB-Tran
1.30
1.3-
5900
5000
4000-
1300
1900
1000
Cumulaaive
0.92
0.31
The Number Segments
The Number Segments
The Length of Each Segment #
(a) Binary segment feedback
(b) Sum segment feedback
Figure 2. Experimental results for RL with binary or sum segment feedhack.
m does not impact the regret result essence.
SegBiTS and SegBiTs-Tran in known and unknown tran- sition cases, respectively, and we set |S| |-A| and K 30000. For the sum feedback setting, simi- our algorithms E-LinUCB and LinUCB-Tran in known and unknown transition cases, respectively. Since E- L-nnnC and LinUCB-Trees are computationally inefficient (mainly designed to reveal the optimal dependency on m), we use a small MDP with S| = 3 and [AA] = 5, and set K 1000. The details of the instances used in our experiments are described in Appendix A. In both set- tings, set Tmax 0.5, 5 0.005, H 100 and E {1, 2, 4, 10, 20, 25, 50, 100}. For each algorithm, we perform 20 independent runs, and plot the average cu- mulative regret up to episode K across runs with a 95% confidence interval.
4.3. Algorithm LinUCB-Tran for Unknown Transition
larly,
Now we investigate RL with sum segment feedback in the unknown transition case.
For unknown transition, we design an algorithm LinUCB-Tran, which establishes variance-aware uncer- tainty bound for the estimated visitation indicator oz. and incorporates this uncertainty bound into exploration bonuses. In analysis, we handle the estimation error of visitation in- dicators [ - 6" || by this variance-aware uncertainty bound, which enables us to achieve a near-optimal regret in terms of H. The details of LinUCB-Tre -rann are deferred to Appendix D.3, and state the regret performance of algorithm LinUCB-Tran below.
Figure 2(a) reports the regrets of algorithms SegBiTS and SegBiTS-Tran under binary feedback. One sees that as the number of segments increases, the regret decreases rapidly. Specifically, when decreases from 20 to 1, i.e., # 2m increases from exp(2.5) to exp(50), the regret grows explosively. This matches our theoretical results, i.e., Theo- rems 3.1 and 3.3, which show dependency on exp( Hr 2m
Theorem 4.3. With probability least 1 8. for any > O, the regret of algorithm LinUCB-Tran is bounded by
δ ((1 Tmax)
| AAHHVK)
Theorem 4.3 shows that similar algorithm E-LinUCE, the regret of LinUCB-Tran does not depend on the number of segments when ignoring logarithmic factors. The heavier dependency on (S), |A| and H is due to the estimation of the unknown transition distribution. We also provide a lower bound for the unknown transition case, which demonstrates that the optimal regret indeed does not depend on m and our upper bound is near-optimal with respect to H (see Appendix D.5).
Figure 2(b) plots the regrets of algorithms E-LinUCB and LinUCB-THE Tran under sum feedback. To the impact of segments regrets clearly, here we show the regrets with respect to the number of segments m and the length of each segment H in the left and right subfigures, respectively. In the left subfigure, when m increases, the regrets almost keep the same for small m and slightly decrease for large m. To see the dependency on m more clearly, we turn the right subfigure: When the length of each segment increases, the regrets slightly increase in logarithmic trend. This also matches our theoretical bounds in Theorems 4.1 and 4.3, which do not depend on m except for the log( # factor.
5. Experiments
Below we present experiments for RL with segment feed- back to validate our theoretical results.
For the binary feedback setting, we evaluate our algorithms
8

---

Reinforcement Learning with Segment Feedback
6. Conclusion
Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E.
The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77) 2002.
In this work, we formulate a model named RL with seg- ment feedback, which offers general paradigm for feed- back, bridging the gap between per-state-action feedback in classic RL and trajectory feedback. In the binary feed- back setting, we deign efficient algorithms SegBiTS and SegBiTS-Tran, and provide regret upper and lower bounds which show a dependency on exp( Hrmax) ). These results 2m
Azar, M. G., Oshand, I., and Munos, R. Minimax regret bounds for reinforcement learning. In International Con- ference Machine Learning, pp. 263-272. PMLR, 2017.
Borjesson, P. and Sundberg, C.-E. Simple approximations of the entor function q (x) for communications applications. IEEE Transactions on Communications, 27(3):639-644 1979.
reveal that under binary feedback, increasing the number of segments m greatly helps expedite learning. In the sum feed- back setting, we develop near-optimal algorithms E-LinUCB and LinUCB-Tres Craan in terms of H and m, where the regret re- sults do not depend on m when ignoring logarithmic factors. These results exhibit that under sum feedback, increasing m does not help accelerate learning much.
Chatterji, N., Pacchiano, A., Bartlett, P., and Jordan, M. On the theory of reinforcement learning with once-per- episode feedback. In Advances in Neural Information Processing Systems, volume 34, pp. 3401-3412, 2021.
There are several interesting directions worth further inves- tigation. One direction is to consider segments of unequal lengths and study how to divide segments to optimize learn- ing. The variable segment length will affect the noise variance of reward feedback, and the sum analysis of seg- ment visitation indicators. More advanced techniques are needed to handle these challenges. Another direction is to generalize the results to the function approximation setting. Since our analysis is based on the fact that segment reward feedback is generated linearly with respect to visitation in- dicators (ss, a), we believe that generalizing (ss a) from visitation indicator in the tabular setting to a feature vector in the linear function approximation setting is viable.
Dann, C., Lattimore, T., and Brunskill, E. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, volume 30, 2017.
Efroni, Y., Merlis, N., and Mannor, S. Reinforcement learning with trajectory feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7288-7295, 2021.
Faury, L.., Abeille, M., Calauzènes, C., and Fercoq, O. Im- proved optimistic algorithms for logistic bandits. In In- ternational Conference on Machine Learning, pp. 3052- 3060. PMLR, 2020.
Acknowledgements
Filippi, S., Cappe. O., Garivier, A., and Szepesvári, C. Para- metric bandits: The generalized linear case. In Advances in Neural Information Processing Systems, volume 23, 2010.
The work of Yihan Du and R. Srikant is supported by NSF grants CNS 23-12714, CCF 22-07547, CNS 21-06801 and AFOSR grant F49550-24-1-0002.
Gao, D., Lai, H.-Y., Klasnja, P., and Murphy, S. Harnessing causality in reinforcement learning with bagged decision times. In International Conference on Artificial Intelli- gence and Statistics, 2025.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Gheshlaghi Azar, M., Munos, R., and Kappen, H. J. Mini- max pac bounds on the sample complexity of reinforce- ment learning with a generative model. Machine Learn- ing. 91:325-349, 2013.
References
Jaksch, T., Ortner, R., and Auer, P. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1600, 2010.
Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24 2011.
Jin, C., Allen-Zhu, 7.., Bubeck, S., and Jordan, M. Is q-learning provably efficient? In Advances in Neural Information Processing Systems, volume 31, 2018.
Allen-Zhu, Z., Li, Y., Singh, A., and Wang, Y. Near-optimal discrete optimization for experimental design: A regret minimization approach. Mathematical Programming, 186:439-477 2021.
Lattimore, T. and Hutter, M. Pac bounds for discounted mdps. In International Conference on Algorithmic Learn ing Theory, pp. 320-334 Springer, 2012.

---

Reinforcement Learning with Segment Feedback
Laurent, B. and Massart, Adaptive estimation of quadratic functional by model selection. Annals of Statis- tics, pp. 1302-1338, 2000.
Ménard, P. Domingues, O. D., Jonsson, A., Kaufmann, E., Leurent, E., and Valko, M. Fast active learning for pure exploration in reinforcement learning. In Interna- tional Conference on Machine Learning, pp. 7599-7608. PMLR, 2021.
Munos, R. and Moore, A. Influence and variance of markov chain: Application to adaptive discretization in optimal control. In Proceedings of the IEEE Confer- ence on Decision and Control, volume 2, pp. 1464-1469.
IEEE, 1999.
Pukelsheim, F. Optimal design of experiments. SIAM, 2006.
Russac, Y., Faury, L., Cappé, O., and Garivier, A. Self- concordant analysis generalized linear bandits with forgetting. In International Conference on Artificial In- telligence and Statistics, pp. 658-666. PMLR, 2021.
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018.
Tang. Y. Cai, X.-Q., Ding, Y.-X., Wu, Q. Liu, G., and Sugiyama, M. Reinforcement learning from bagged re- ward. In JCML 2024 Workshop: Aligning Reinforcement Learning Experimentalists and Theorists, 2024.
Thompson, W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294, 1933.
Tropp, J. A. et al. An introduction matrix concentra- tion inequalities. Foundations and Trends@ in Machine Learning, 8(1-2):1-230, 2015.
Zanette, and Brunskill, E. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In Interna- tional Conference on Machine Learning, pp. 7314-7312. PMLR, 2019.
10

---

Reinforcement Learning with Segment Feedback
Appendix
A. Details of the Experimental Setup
In this section, we detail the instances used in our experiments.
For the binary segment feedback setting, we consider an MDP as in Figure 2(a): There are 9 states and 5 actions. For any E A. we have r(50 a) 0, r(8;, a) = Tmax for any i (1,3,5, 7] (called good states), and r(s;, a) = - -Tmax for any i {2, 4, 6, 8} (called bad states). There is an optimal action a" and four suboptimal actions a udh for all states. The agent starts from initial state sp. For any state and bad state the next horizon with probabilities 0.9 and 0.1, respectively; Under the suboptimal action ahhh the agent transitions to the good state and bad state at the next horizon with probabilities 0.1 and 0.9, respectively. In or 5g, under the optimal action a", the agent transitions to 51 and with probabilities 0.9 and 0.1, respectively; Under the suboptimal action a sub the agent transitions to $ and $2 with probabilities 0.1 and 0.9, respectively.
< 6, in state 8t, under the optimal action a", the agent transitions to the good
Optimal action a": w. 0.9 Suboptimal action: a suub
r(sp.) max (1,3,5,7)
0.1
S
$3
Ss
S7
r(so.) =
Optimal action a.: 0.1
S6
SB
Suboptimal action sub; W. w.p.ppp. 0.9
rs,,)
max
vi (2,4,6,8)
Figure 3. Instance used in the experiment for RL with binary segment feedback.
For the sum segment feedback setting, since algorithms E-LinUCB and LinUCB-Tran mainly designed for revealing the optimal dependency on // and m). we consider smaller MDP as in Figure 2(b): There are 3 states and 5 actions. For any E A, we have r(50, a) = 0, r(s1 a) = Tmax (called a good state), and r(32, a) = -Tmax (called bad state). There is an optimal action a" and four suboptimal actions a sa for all states. The agent starts from an initial state sy- In any state s E S, under the optimal action a", the agent transitions to $1 and 82 with probabilities 0.9 and 0.1, respectively; Under the suboptimal action sub the agent transitions to 81 and 82 with probabilities 0.1 and 0.9, respectively.
computationally inefficient (which
r(pp:) mmax
Optimal action a.:w.p:: w.ppp.r 0.9 0.9
Suboptimal action: a sub, w. p. 0.1
C
$
r (5o:)) =
So
O
Optimal action a d.: 0.1 Suboptimal action a sub, w. p. 0.9
52
r(s,.) Tmax
Figure 4. Instance used in the experiment for RL with sum segment feedback.

---

Reinforcement Learning with Segment Feedback
B. Rounding Procedure ROUND
Algorithm E-LinUCB calls a rounding procedure ROUND (Allen-Zhu et al., 2021) in the experimental design literature. Taking XI...., X,, E $4. distribution w (x).......)) rounding approximation error y >> 0 and the number of samples T 2 d as inputs, ROUND rounds sampling distribution w into discrete sampling sequence (YI....,, Yr) E ( ;,......,... Xn) ) that satisfies
7
(
Σ Yg
s
(1+
T T 20 (x))x)
KE(N)
In implementation, we can regard rx" T in (Allen-Zhh et al., 2021) as E E (0-=)) and regard sampling weight on x as the sampling weight on our work.
C. Proofs for RL with Binary Segment Feedback
In this section, we present the proofs for RL with binary segment feedback.
C.1. Proof for the Regret Upper Bound with Known Transition
First, we prove the regret upper bound (Theorem 3.1) of algorithm SegBiTS for known transition. For any k > 0 and 0 O define
E a 0if
7x =
k=1
122
(0) Σ
ul(o=t) u((ott)TO) (TO) ort +10,
(5)
k==1
i=1
k
(0)= = Σ
((o= TO)- + (ot T + XL.
(6)
W=1iml
Lemma C.1. For any and O we have
HH2 HH2ymaxth + x) |5||A|m
181141
dct(Ax(()) <
Proof. For any &>0 0, we have
(r((An())
[S]|A1
de)(Ax(0)) <
|S||A1
+ (ISIIL ) 1S|141
H 2
km Prmax
-
SS|A
m
H22 H'mach
(S|IAA)
+ A
|m
For any is > let F5 denote the filtration that includes all events up the end of episode k. and Fj denote the filtration that includes all events before playing = in episode Then, n F--measurable.
For any > 0 and E [m], let Ckii = D¹ ( T denote the noise of binary feedback, and of, E|c2, ( T (1 - ( ) = p'((=²?) TTt)) denote the variance of εk,s conditioning on Fe.
12

---

Reinforcement Learning with Segment Feedback
Then, have
h
Σ k "(O)t) (Tr) -0t (Øf) +
(x =
k
0 (6r) + XX.
Lemma C.2 (Concentration of Noises under Binary Feedback). With probability at least for any > 0,
||A
4 (1+ H (mazk)
Σ
Σ
log
[5)((A(m))
2
8
(0-
Proof. According Theorem 1 in (Faury al., 2020), we have that with probability at least 8', for any & > 0.
k
E
0T!
V
+
2
log
det(Ax(0*))
A
1811
+
2
|S||A| log(2)
2
V1
6'
k==1 1m
A 110)
VX
1
(
1 Pinax k
2
log
1
2
8'
|8]
|
VX
|A|
H² H' |S||A|mA)
+
log
|||| log
Vī
81
VX
Vī
|A|
H 1'mack
+
VX
log
8'
1
[S||A|mm)
where (a) uses Lemma C.I.
Define event
E = (l((00) su(0r)
1 S w(k), Wh > 0)
Lemma C.3. It holds that
Pr [8[ 2 8'
Proof. This proof is similar to that for Lemma 8 in (Faury et al., 2020)
Define
m
log ((((ot))T))) + +(1 )T0))+(1-5(") log (1-1((0=))TO)) -1113)
(=(0)==-
Recall that 0 argming L* (0). Using the facts that (Lx( = 0 and pl(x) u(z)(1 (1 -(()),, we have
m
b
u((o TT,)) x + 20=
#=1 1=1
9y (a,)
Hence, we have
k 9t (a() (x") =
④ ΣΣ H((ott TTy). 6xx + ^0
Σ
Vi
k
1=1
13

---

Reinforcement Learning with Segment Feedback
EM of 10"
Then, using Lemma C.2, we have that with probability at least 1 - 8', for any & >> 0,
k
| (0x) 0x(8))
+mmax AASIIA
22 (0-)
='=1=
1=1
|A|A
4 8
(1+
H2 Hmuakh
S||A|mm ) + mmax V A/S|i/V
-
log
2
VA
(b)).
For any Φ E RIS|IAA and 01,02 E θ, define
00,,0,02) = [" 1-- p'((1 - TT + + 02)dz.
For any k > 0 and 01, 0g E O define
02) = Σ (1001102)) o5 (0t TT + AI.
k=1 i=1
In the definitions of b(6), 01, 02) and (0 02). O1 and 02 have the same roles and can be interchanged.
Recall that
Hr Hruax Hrmax
== exp(
+ exp(
+ 2.
m
m
Then, have
sup p e He (( S a,
where 708 denotes the visitation indicator any possible trajectory segment.
Lemma C.4. For any k and O we have
Σg aAe((O.
Proof. We have
inf 1e ((
a 2 B
Then, holds that
m
( T + add
Σg
1=1
ΦF ( TT + +1))
Σ
(( TO) 0.th (ot ) -N)
a
(0).
14

---

Reinforcement Learning with Segment Feedback
Lemma C.S. For any & IR IRSSAA and 02,02 O have
u(6 01) u/o 82) (.0.0,.01) -0 02).
In addition, for any k > 0 and 01, 02 θ we have
||0 22 02llr, = (0.x - g1 (0(02)llr, -00000) (1)
Proof. The first statement follows from the mean-value theorem.
Then, using the first statement, we have that for any l > 0.
(u(cot) T - -ollottt (ob)) .ot + +A -02)
gh (0,) - (02) =
k==1 1=1
b( ,02,01) ttt ) [(: 82) A A01 02)
i=1i=1
(02, 01) (01 -0))
and thus
100 02 0211r((0,00)
(01 02) [Tx(0,, 01) (0) 02)
V (01 02) [O, 01) TT T==((8) (02, 01) I 01) (01 02)
= (1:)(01) go (ol2))lr,
which gives the second statement.
Recall that for any k > 0, Zk == Σt -=
E m
iil EWI - 6t!
Lemma C.6. For any k > 0, we have
Hr Hrmax v S|A
H
In(0", 2
1
2 (1,2(0r,bs)
As(07),
mvA
HTmax max 11+
S
H
Z (0- b.)
|Z (
+
1z 1Zll222000
mvx
m
Furthermore, assuming that event holds, we huve
V 1+ Hrmax v S|
H
7 7xllmz"
(kk) +
w())
mvX
Proof. This proof follows the analysis of Proposition 6 and Corollary 5 in (Russac et al., 2021).
From Eq. (7), we have that for any > 0,
(r( - gu (0*) = Zx - -0
Using Lemma 1. we have that for any & E R|SI|AA such that |10112 S Too
6( 0x) > o (0 (0-- 8z) (6))) 10 T0)
= (1 T 10" 0c)) (mn(00) (0())))) TT(
15

---

Reinforcement Learning with Segment Feedback
(r(2(or.aa)) (oo ) -1
+ || (0r, @n) [0xx - gl((2x)
n' 0*)
Le
(9x(0)) -aa(0e)) (2 (l(
Lo
1 - 10 10-11==(00066))
1 O'
T (2)l LooTmas /SSIAA
116 07).
VX
Using the above equation with Φ = /. and Ls
H. m
we have
1o 0n) =
bl 00 0,) ot +
k'
HT max v SS
A
H
-'(oTTM) - (ot 5 T
1+
1Zallr, 110 (c)
m
mvx X
k=li=1
Hrmax V S||A
H
1
|Z l1, (00 A2(0)).
m
mv
This implies
Hr max VSIAA
H
12lle,, 0z) S 1
mvd
which is equivalent to
H
Hr maxa v /
Z F, Ac)
| 1 (0.) (2-ll
1
|| 1zall3 S S.
my mvx
By analysis of quadratic functions, we have
Hrmax v S
H
1Z (2))
1 +
1 1Z +
| 12xll2z'000
m
mvd
Hrmax S|A
H wk)²
1
w(k)
m
mvÀ
Lemma C.7 (Concentration of Φ TTØ under Binary Feedback). Assume that event & holds. Then, for any le > and R (IAie
10b To 0r - -0all S Va. v(k) ||
Proof. We have
To - Tbl
100-600 8x 6 Ba)
=11ol1r,'(00 (w- )2)
16

---

Reinforcement Learning with Segment Feedback
(
Hr max v /
I1
|| 1 17 (0-,0x) (2) I1ollaz ((0)) (sa(00) g0((0x) (0-
m
mvx
Hr max V
[ ||
H
1 Ir. ((0-,02) Ilolla, ((00) 11 - 10 11, (00)
mvx
7
Hr max
/
H
| 1alllr--00 10- b.) 1lllAaition ( (1Z 2000 ((0,bb))) +rmax v (|S|[AA
m
mv
mvx
HT maxx
S
A
H
1z (0- (.) 11
=
H
m
mvx X
11
H Hrmax SIA
1 (z)
mvX
3
m
Hrmax
||A
H
1 llll 100 Oul ows)
1+
101
H1
77
mvA
)) 8
(h) mvax
1
Hr
SIA
H
Hrmax v |
w(k)
H +
mv w(()P)
1101
H
m
mvX X
m
Va- v(k) |,ll
where inequality (a) is due Lemmas C.5 and C.6, and inequality (b) follows from Lemmas C.4 and C.6.
Lemma C.8 (Gaussian (ati-toncentr.tion).. Assume that event holds. Then, for any > and Fk- measurable random variable X E [ISS|AA,, we have
1
Pr x On 1 XT
2
2/2me
Proof. This proof is originated from the analysis of Lemma 11 (Efroni et al., 2021).
Using Lemma C.7, we have that for any O,
X 0r X 0p-1l S Va.v(( | 1|
holds that
Pr
X 02 > X
8" TT Fx-1]
X T - X 0x
X - X A Va v(k 1|
Pr
F
Va- v(k ||||X||
Here given FE-1, XTO. - XTO = TT. is a Gaussian random variable with mean and standard deviation va v(k (|| بجاا
Since when event & holds,
g xT
Vā-v(k - 1)1lX E
va.u(k v(k - 1)||X||s ب|
Va. v(k - 1)|xX|12,1,
we have
XT - x 0
Pr x xTo Fx-1] 2 Pr
> 1 F
Va u(k 1)1 بلا
17

---

Reinforcement Learning with Segment Feedback
E
Pr
> 1 Fk-
u(k
2/2TT'
where inequality (a) comes from that if Z UTran (0, Pri
TF2z & (Borjesson & Sundberg, 1979).
22n
Lemma C.9. Let Ek: S/ E [|SSIA) be i..dd random variables given Fk-1. Let P be a Fk-1 meesurabee transition model, and 1k-1 E RISIIA be Fm-e-uuaurrable random variable. For any policy n, denote the visitationn indicator under policy T on MDP p by Φt. Let th == argmax, (6²) (Ix-1 + Ex). Then, we have
E ((a+)) TT (ar-11 + [k) - I (( (IX-1 Ex) Fa- 1)-1))
FR-1
< B ET + 1(0 T $sl Fa-1]
(
Proof. This proof is originated from Lemma 12 in (Efroni et al., 2021).
First, using the definition of r* and the fact that &N and 4 follow the same distribution, we have
E ( TT (#R-1 + Ex) Fk-1 =E [ (IR-1 + Ek) 1 F
(8)
Then, since given Fx-1, En and E are independent, we have
max( ( +6) Fx-1 mmax("") (x (6 Fa-1, Eu
2 E )( T (IR-1 + PR Exs Tk]
(9)
Hence, combining Eqs. (8) and (9), we have
E (()*)) (αk-1 + Et) E [(o (Ik-1 + Ex) | [])=1]) Fk-1
$ E
(( (Ik-1 + Ex) E [( T (Ik-1 + (k) FF Ex, #x])*
Fk-1
(E RT) (xk-1 + (x) - ) (Ik-1 + (k) FF Exs Txl) +
E
Fk-1
= E
( [() )T Ex - -(0* ) Thh. F Ek. #x])"
Fk-1
< E
E [10=2) ) Eu - ) T F , Ek. #k]|
Fk-1
< E
E [1( T Ex - ( Tel Fi Ek. =x]
Fx-1
E
[( - ( Tghl F
< E
[(0ft) Ex|
FE-1] + E
[(0ttt] ( E66
Ba-1
For any 1: > 0 and 6% E (0, 1), define event
Ma(6a) :- Ve E [|
T0T Eal S Va v(k va.u(k-1)
(VIST1A)
+ +2
1 fog Ōx
|| |
18

---

Reinforcement Learning with Segment Feedback
Lemma C.10. For any k > 0 and 6y (0, we have
(r[M&((k)) Fk-1] 2 1- ōz.
In addition, for random variable X &R(SIIA) such that || |xxxt S Lxx, we have
Eal Ekl [k-11 & Va v(k 1) [VISTAA|+2 + +2 (6))
E X
| || [Fa-1
+ Va - u(k - 1) LXVISIIA
Proof. This proof is similar to the analysis of Lemma 13 in (Efroni et al., 2021).
First, we prove the first statement.
For any & E RRSI|AA,, we have
10 T Exl
= 16 Σ 2 E 1
Ex
/b ||, | Ex
Va u(k 1) 1100l Va. vlk: 1) 2x Ex
(10)
2
Since given FR-1, Ja - Ex RISSAA is vector with each entry being standard Gaussian random variable, we have that (a= E
I Exlle is chi-distributed with parameter [S)]
Then, using Lemma 1 in (Laurent & Massart, 2000), have that with probability least 1 8g.
1 Vā v(k 1) 1z Ex
1
1
$\ |S||A|| +2 |S|| log
+ 2 2og
ÖN
(VI8IAA + V log
1
1
log
8x
5k
1
S VIS|IAI + 2 log
5k
Next, we prove the second statement.
For random variable X [RIS|AL have
||X & [ Pr[MM(B4]] (IXT IF
+ Pr [M[()(())]] E B[IX Exl M
(VIST-ATT + 22 log
S V vak - 1)
E
||
1F
0x
Pr [Ma(O))
E [XTTE Me.
Va. u(k: 1)
VIS|IAAi + 2/
log
E
||
[Pa-1]
tz
V ulk -11/
dAL | 2
v(k - 1) 2ا مو Ex
FF--1
Va
19

---

Reinforcement Learning with Segment Feedback
Va.vvl 1)
VIS||AA + +2 log
E
|| xx
+ Vā. u(k 1 1 ||
Va Ilva u(k - 1)
St
Pk-1
(b)
Va. 1/ 1) (VISTLA1 + 3 log
1 5x
E
| ||||ا;1
[Fk-1]
Va. u(k - Ixx -
Here inequality (a) follows from the Cauchy-Schwarz inequality. Inequality (b) is due the fact that given Fk-1- Vo.u 2a E& la is chi-distributed with parameter [)), and then E|]] Ja-u(K-1) E Ex Pa-1]
|||
Define event
B KTan
{
Σ
k
E Braat
[11551
(o0'l(s--,-111 |F - 1100 -110")((sw-11 I((
S $4H
|
ad
k
log
4h
8'
Σ
E (obtt)
- ((0mt) -(
s 44rruux
V klog
4k:
)
8'
Wk
(11)
Lemma C.11. holds that
Pr
B KTan
> 1 - -220.
Proof. We prove the first inequality as follows.
For any k 2 1, we have that || (S S Vax and then [E [|| 11
[Fg-1]
11
(S
2H Val
Using the Azuma-Hoeffüde inequality, we have that for any fixed k > O, with probability at least 1
5'
26
4H²
4k2
E E
[10"
|F 1 - 11 ((]"(((w-))) s
$/2
2 at
k log
8'
Since k 26
I 8', by a union bound over k, we have that with probability at least 8', for any h 2 1,
E T
[11071
- [Fw-1] |10 2-2) s 122
4H²
k
4h2
ai
8
4k
S
4H
log
ax
8
The second incquality can be obtained by similar argument and the fact that 1(+=t) TT
)( < Hrmax for any t 0.
Lemma C.12. For any K 1, we have
maxxx 1 log 1+
H²
KH2
S
max
S 1)
k= i=
Proof. We have
m
m
(E--1) 5
Km
(Ee-1)
20

---

Reinforcement Learning with Segment Feedback
2Km max
H2
}
log
+ 1=1
p
maax"
(Ex-1)
h=1
H2
det dot((ad)
2Km max
log
maax
2Km]8|[A| max
H22 max
1) llog
1+
KH²
(12)
where inequality (a) is due to that for any E [0,c] with constant e 2 0, it holds that x S 2 max 1) loog(1 x)..
Proof of Theorem 3.1. Letting 8' 3+ we have Pr[E n.F KTaal S 1 - 6. Then, to prove this theorem, it suffices to prove the regret bound when event & n n
KTran holds.
Assume that event & n F F
KTram holds. Then, we have
K Σ
R(K)=
T - (T))
k
(0= TT - ( ) 18-1Fk-1 + E ( ] -
E
E
(0 -r TT ( T0 4llTmax / K log
[KK
(13)
8'
For the first term, we have
(0 -
K
E To - -00** 1
+ [(00t)
(14)
k=
In the following, we prove
[x E T -00- 1 S2V2Te- E
(10t) - -E TT ( Fi....) |Fx-1]
(15)
E ((0 - Otherwise, letting 2 == B[(Ø=T) ) T - - @.(FF
T < 0, then Eq. (15) trivially holds.
we have
(10=*) TT - E ( TT 1) 12h-1
E
(0th TT - EE ((0=*) ) Fk-1 2 2/Fx-1
Pr
A V
E
T TT 0- - ) FeelFk- --]) 1) Pr
T 2 T
) 1
( T0 - (00 TTelFF - 1) Pr ( T 2 (6 TT'FF--
I
v
E
)T= (60 T
"T Fr- 1) 2/22e
where inequality (a) uses the definition of * and inequality (b) follows from Lemma C.8. Thus, we complete the proof of Eq. (15).
21

---

Reinforcement Learning with Segment Feedback
Let E [R|S||A|| be random variable that is i.i.d. with & given Fg-1- Then, using Lemma C.9 with p' p. 3/--1 = 0
and # n², we have
E ( T -
s 2ve E
((00)) T - E ((( 1 (r
FR-1
s 2v 2Te E [|0(=*) [ + 1 [F--1]
Plugging the above inequality into Eq. (14) and using Lemma C.10 with ó5 + and Lx
H Jax
we have
E (0=))
K
2 22/ [ICOO*) TEal=<(0>"000 ) Tel Fk-1 F +B (T (00
(2<2ore+ +1) 1) B |((0r))
TEal |Pc-1] [Tel
2vre E [((00*) T |Fk-1
E (10 (00
(8) K
(AV2Te ( va-u(k-11 1)
4 log (k)) E
4v
1|00 2
1F--1
(4V2me+ Vox v(k u(k V
H
(16)
122
Vad
where inequality (a) uses Lemmas C.7 and C.10.
Here according the definition of event JB KTra and Lemma C.12, we have
K
K
K
x
E
Fx
E
Fk
-
K
4K
S
4H
log
al
8'
max H maxx
KH2
2Km|s||A|
llog
(1
(17)
al|S||AA(m
Therefore, plugging the above two equations into Eq. (13), we have
R(K) < (4v +2) Va. ((K))())
(VISIAAI + 4 (K))
K ad
4K (8')
H²
KH2
AHl
log
2Km|8|IA| max
maxd 1 log
1+
ad|Ss
aA|S||Alm
|AS|AAI
[4K'
+ 2Te + 1) H v(K))
+ +4Hrmax
Klog
X
5'
Ö expl
HTmax
(
H²
2m
) v ((K)
max
max
+
ad
where in equality (a), the last two terms are absorbed into Ō(-)
22

---

Reinforcement Learning with Segment Feedback
Optimal action: r(5 ai) Imax
Suboptimal action: (St, ((ub)) (1 max
a trassiionn to Sn+1 sub, transition to Sn+2 a1
w.p. S1
8n+1
r(n+11)) = Fmax
w.p.
r(8n42)) = 8)mx
Sn+2
w.p.
Figure 5. Instance for the lower bound under binary segment feedback and known transition.
C.2. Proof for the Regret Lower Bound with Known Transition
In the following, we prove the regret lower bound (Theorem 3.2) for RL with binary segment feedback and known transition.
Proof of Theorem 3.2. We construct random instance as follows. As shown in Figure 5, there are n bandit states $1.-..:: 8n (i.e., there is optimal action and multiple suboptimal actions), a good absorbing state 8x+1 and bad absorbing state Sn42. The agent starts from . Sn with equal probabilityy 1. For any E [n], in state 8;, action a, is uniformly chosen from A as the optimal action. In state 8;, under the optimal action a., the agent transitions to 8841 deterministically. and r(s;, a.) = Tmax: Under any suboptimal action a E A \ } the agent transitions to Sx+2 deterministically, and
r(s;, a) = (1 - e)r where ε E (0, 2) a parameter specified later. For actions a E A, r(sn+1, = -max and r(8n42: a) = 1- e)maax
In this proof, we will also use an alternative uniform instance Tunit The only difference between Tunir and I is that for any i [n]. in state 8,, under all actions A, the agent transitions to 8n+2 deterministically. and r(s;, a) (1 e)r max.
Fix an algorithm A. Let Eunir( denote the expectation with respect to Tunir. Let [.[-] denote the expectation with respect to I. For any E [n] and j e [[A[], let [-] denote the expectation with respect to the case where aj is the optimal action in state St. and Ni denote the number of episodes where algorithm A chooses aj in state 8ú, i.e., No. Σ 1 ( (s:) az}.
The KL divergence of binary observations if taking a, in s in each episode between Iunif and I is
KL. B (1
(1(11 Timxx
H
1
11
P'ax
m
(a) (1 ((1 mamx H
(Fmax
H ))
m
HL (Frux
H.
m..
(b)
nl ((1- - E) Mraux
<
jel
Hrmax
m
where inequality (a) uses the fact that (l.(B())))(gg) S decreasing when 0.
(p-9)² ql--])+ and inequality (b) is due to that n1(x:) is monotonically
In addition, the agent has probability only to arrive at (observe) state
Thus, using Lemma A.1 in (Auer et al., 2002), we have that for any E [n]] state 8;
K 1 +
p ((1 E) Hruna (s
Hrana m7a
E,y[N & Eunit [Ni
m mmmmmmmmm Eunit [e,)]
m
2
n
n
Hrmax
m
23

---

Reinforcement Learning with Segment Feedback
K
max m
He ((1 E) Hr Mrmus>
uuii
Euuit (Ni,))
1ll H Hrmax
n
Summing over j [|Al], using the inequality and the fact that Σラ Bunit [Nv.s] K. have
KHTmas maxe
|AIK μ' ((1 E) Hrmms
B. (N
SK
2
mn
11 (Nrmax
|A|K p' ((1 Cg)
$ K +
m
2
mn
11'
Hrmax
m2
where co E (0, )) is constant which satisfies Co E. We will specify how make co 2 to satisfy this condition later.
Then, we have
K pay
R(K)
Σ Bx
V'
km
Tmax HK
Σ
(1- 1)- max HK + ET ETmax
Σ j=1
Ei, [Na
[
1=1
KH maxe
K 1el ((1 cu)
Hrama
2 max
H K
A
A mm
Hriax
H
Let
A
2H max
K
1d ((1 co) Hrmaz
Then, the constant 6o should satisfy
1 2Hr maxx
Almn
11' (Hrmus))
Co-
K
/l ((1 co)
Hrmma m
Since
(exp ((1- (6) Mrmms
+ exp (-(1 6o)
Hrmaz + 2)²
m /el ((1 co)
Hrmax
cxp
exp
H Hrasx
2
m
(eep ((1 c0) Hrama
(HTmax
exp
m (11-20) 2c0
HTmax
16exp
suffices to let co satisfy
Almm
16exp (1 (1-2ch) 20g)
Hrmax
< Co:
2Hr max
K
m
24

---

Reinforcement Learning with Segment Feedback
Algorithm 3 SegBiiS-Tres
1: Input: 8, 6 X.
2: for k == ==,...., K do
3: 8x-1 t argming - k- 1 (b, log(u((0>') + (1 - v log(1 - u((0=t)) )((o) - 11110113)
4: ΣR-1 + En Eis 6²: (0r ) 1 ad
5: Draw a noise &K ~N(0, a ukk - 11)--1121111 where vlk: - 1) defined in Eq. (1)
lou( ( 6: 1 t min max
Hrmax) for any (s, a) ES
1(0.0)
7: 02 02-1+ Ex +
8: Th argmax, 11)_1) TT 86. where oτ_ is defined in Eq. (18)
Play episode & with policy n². Observe 7K and binary segment feedback {
10: end for
which is equivalent to K
mn H
exp((1 200)
Hemax m
It suffices to let
4|Amm
(Hrmax
K 2
exp
H2
m
and then cu can be any constant in (0, 2)-
Let S 3, |A| 2. co (0, ( and K
4m 1
exp( Hrmax) ). Since
m
μ² (Huma
(exp ((1 c0) Hrmux
+ exp
(-(1 cu) Hrmax) + 2)
1e ((1 co)
Hymax m
exp Himmx
+ exp
Hrmax + 2
(exp ((1 Co) Mymux m
4exp
[HTmax
m
1
(11220)) -20
Hr Hrmax
exp
4
m
we have
A mmn
HTmmx m
K
K
R(K)= 2
mmax
2HTmax
K
1 ((1 -c) Mrams 2
A
4
Hrmax
Ω
exp
(1 200)
|S|IAAmK
Hrmax
Ω
exp
co
V
C.3. Pseudo-code and Detailed Description of Algorithm SegBiTS-Tran
Algorithm illustrates the procedure of SegBiTS-Tran. In episode k, similar to SegBiTS, SegBiTS-Tran first uses MLE with past binary segment observations to obtain reward estimate 0--1. and calculates the covariance matrix of past observations Σ (Lines 3-4). After that, SegBiTS-Tran samples a Gaussian noise & using Σt-1 (Line 4).
For any & > 0 and (s,a) a) E S x A, let (a,- a) denote the empirical estimate of p( ((, a). and nu a) denote the number of times (s,a) a) was visited at the end of episode k. Then, SegBiTS- TS-Tran constructs a transition bonus 16- a), which represents the uncertainty on transition estimation. Incorporating the MLE estimate 6y-1, noise & and transition bonus 18-1(,,, (s,a). a), SegBiTS-TTre - constitutes posterior estimate of the reward parameter 0z (Line 7).
25

---

Reinforcement Learning with Segment Feedback
For any policy n, k and (s, 8 x A, define
H
(5, = Ep.
Σ
1( = s, = aH/T
(18)
L==1
which denotes the expected number of times (s, a) is visited in an episode under policy on the empirical MDP pk. In addition, let 0% = [ (s, (s.(ExXX E RIS|IAI
Then, SegBiTS-Treee Tran finds the optimal policy via argmax, ( 8% which can be efficiently solved by any MDP planning algorithm with transition Pk-1 and reward 0% (Line 8). With the computed optimal policy x², SegBiTS-Tran plays episode k, and observes trajectory and binary feedback each segment (Line 9).
C.4. Proof for the Regret Upper Bound with Unknown Transition
In the following, prove the regret upper bound (Theorem 3.3) of algorithm SegBiTS-TKe Tran for unknown transition.
Define event
log
KHIS|A 6'
Gooet =
P (x-1(-18,0)
Vhtt (Vit - p(-(s,a) (Vlssa S 22 [2Hmmax
A Hrmax
m)-1(5,a)
ESx Vk > 0 )
S.
Lemma C.13. It holds that
Pr (rtteel 2 1 25'
Proof. This lemma follows from the Hoeffding inequality and a union bound over nx-1(8, [KH] and (s, S Sxa A.
Lemma C.14 (Optimism of Thompson Sampling with Unknown Transition). Assume that event and Gooe holds. Then, for any 0, we have
Pr ( (6 T FR-1]
2V2TTe
Proof. This proof follows the analysis of Lemma in (Efroni al., 2021). Using the value difference lemma (see Lemma E.2), we have
(x-1(T²)
02
TT
H
(sp, an) - (" an) + (px-1(-1sn an) p( an)) Vites)
-Ep
H
= -Ep 1.
(sh, - + (sh, an ( (-1 an) -p-lsn, (
(
(da(sh) an) - 0² 0s an) 1p" (sh, an) 60" ani)
E
(Ba(s,, an) - -8" (sh. an))
-Epa-1.7
Σ
1=1
- (TT) T -
26

---

Reinforcement Learning with Segment Feedback
where inequality (a) uses the definition of event Hoett-
Thus, by the definition of vτ. we have
Pr Φk - (TT) 0h TT" Fa-1
Pr
Φ (x (T') 03 ( FK-1
Pr
Øk- (x²) (T²)T²² 0% (Ø )T0 0- > 01 Fk-1
Pr
Ōb- (1t (
0x -x 1 T0 0 F (T=)T0-
IV
2V2Te
where inequality (a) is due to the definition of n", and inequality (b) follows from Lemma C.8.
Define event
L m
Ak (. A
9KL
(110) S
(19)
Lemma C.15 (Concentration of Transition). It holds that
Pr[SKt] 2 8'.
Proof. This lemma can be obtained by Theorem 3 and Lemma 3 in (Ménard et al., 2021).
Recall that for any A: > 0 and (s, a)) E S x A, (s(s,, a) denotes the cumulative number times that (s. a) is visited at the end of episode k. For any l: > 0, [H] and (s, E x A. let (s,, a) denote the probability that (s, a) is visited at step h in episode k and let wry a) Σ h=1 (s,
Define event
& Σ k==1
|SIAI
H = nn(s,a) a) 2 ww - log
vk > 3..00.(s.))ESx44
(20)
Lemma C.16 (Concentration the Number of Visitations). holds that
Pr[M] 21
Proof. This lemma can be obtained from Lemma F.4 in (Dann et al., 2017) and summing over E [M].
Define event
FB
UTan
E (df
-(0tt) TTor < 4H² mmax
klog
4h
2z. Ox (T o(T [Ew--]] 1 - - - x
4k klog
Wk 0
8H
8'
Lemma C.17. It holds that
Pr [Tuna
2 -8".
27

---

Reinforcement Learning with Segment Feedback
Proof. This lemma can be obtained by a similar analysis as Lemma C.11, and the facts that 1( ) 6o-=11 S H22 rmax and 1(²=-((T*) x0"111 111 S 2H for any k 1.
Lemma C.18. Assume that event F n 9KL O H holds. Then, have
k
E
Φh (T*) - 00 [Fa-1]
S 24c22181
H V KL KL
1=1
2K SH
+ 19/ H22 log
8'
Proof. First, from Lemmas D.10 and D.11, we have
Σ Φk
(T)
((T))
K
H
Σ
wh (s)a) 811
L
+
46H²
1k (8, a)
7k- (8,a)
1=1 (s
K
H
+ e 12 S
ΣΣ
Σ
Wh (s,a)
k= hm (s
k
H
K H
w (8,a) a) (8,a)
< <
Σ
WH (3,0)
(s,a)DDe
(s,a)ED.
K
H
W (8,
| H 8'
+ 46c 12 2
L
+ | S| log
(s,
Am
h= (e.o)ED2
< 166 $ |A
KL log(((2 184e |A| 11 Log
|
+ 15 H log
2KH
< 116 AA| 1 H
KL + 10
8'
Next, we have
Σ
E
( -
0000/ [F-1
K
k
1 ( Φ
E
-0501 |F
(
11))
k=1
k=1
(2K
16e 12 (S| } |A| 3 / KL log (2H + 1926 115711) H2 2 Llog
8'
4K 8
8H +8H/
K log V
2KHSSIA
$ 12
|A| H v KL log (2HH) + (P
8'
Lemma C.19. Assume that event FB
UTran holds. Then, we have
K
4KH|S
E
(0t")
Top
pe 1 Fx-1] < 20|S||A|HH r max / K log
8'
28

---

Reinforcement Learning with Segment Feedback
Proof. It holds that
K
R
T
1
R=1
Tbpe
B ) To FR-1 (0)*) T
KHHSSIAI
K
H
log
wh (8,0)
2H
6' mk-1 (8,
A Hrmax
+ 44422 mmax
Klog
[4K
8
k=
h=
|HHS||AA
w/ (s,a)
22HTmaxx max
2HH
log
ΣΣ
Σ
8'
nk- (8,
(s.a)EDs
H
4K
HTmax
Σ
wh as,a) + 4H2 4ff Tmaxy
Klog
8r
k=1 1= (s
KH KHISIAA
K ΣΣ
wh (8, a)
2H 22TTmaas muax
log
VKH.
Σ (s.a)ED,
8'
ni n (s
|IHAIS
4K
+ +H rmx log
+ 44H2 +
K log 8
8'
KHIS|AA
< 2H 22Tmaam max
log
VKH
||A||| log (2K
8'
SIHA
4K
+ +8|S|| | max log
+ +4H2 /
K log
8'
8
4KH|S|A1
S 16 A| Tmax K Klo
8'
Proof of Theorem 3.3. Letting 8' &. we have Pr(E n FT n 9tooen O 9KL. n FF < theorem, suffices to prove the regret bound when event n FB n GHoeff n GKL H n JBll holds.
Then, to prove this
Assume that event & n JB KTran GHoei GKL n H H
H.JB Juran holds. Then, we have
K
R(K)=
Σ
)
T -60
K
R
(1) TT -
T0 + W TT0 [0 )(0)
K
E
(0 T - T 444Tmaa HHxmxx
K log
4K
(21)
8'
For the first term, we have
K
TT -00"
E
29

---

Reinforcement Learning with Segment Feedback
K
E (0=²) T 0r
( + E @ (TTh) 0% (T0))TTTFF
(22)
In the following, we prove
E [60) T - ( Fk-1
S 2v 22222e 2ne E (0)_ E
[F6-1
(23)
If IOT - - (TT) T 062 1k < 0, then Eq. (23) trivially holds.
Otherwise, letting Bl((d") ) ) - - (T²*) 02 Fk-1) we have
E
h2 (m* T E ( )
T 1) |F--1
Pr
5 (xx))(() 02 E d (1 0% FA 2 P
(o" )T 0- -0--000 - ) ) 0% Fn (A-1)) 1) Pr ( T 0% 2 (6 (T 11
IV
E
IVE
E
( TO 0r - - 0% Fk Fk-1 2VeTe
where inequality (a) uses Lemma C.14. Thus, we complete the proof of Eq. (23).
Let 5% SIIAI be an i...d random variable with given Fs-1- Then, using Lemma C.9 with p' pk-1, 2k-1
Q--1 + 1 and = = n²,, we have
E [((OT) )O' - 1 ( FE
+ - 2/ E (0u- 02 E 20 [0g]F=-1) 1)
|F
$ 2v 2TE E ( + ( T [Fk-1]
Plugging the above inequality into Eq. (22) and using Lemma C. 10 with 5z tor and Lx
Vax we have
K
22/ E (7t) Exl + (T [Fa-1
G (x+) (Ba-)) +be + =Ex) - (
+ E
K
Σ
(2/22e+ + 1) -E ( TEal
Evl [F
+ 22222e E ( Ekl [F
k=1
( (Ba-1 + +b - -
E
Σ
(AV2Te+1) va-v(k-
v(k v(k-v(k1))))))))) 1) (1)t-111((ss)) (VISTIAI + 4 10log (k)) ( (m 1|ااا Fx-1
(4V2me+1) Va- (W
S
H
+
k2
Val
30

---

Reinforcement Learning with Segment Feedback
+ I2
(
+ + -(0
(24)
We have
のx - 1 (x+)) (0a- + 12-1) (1b+) T FR-1
E
cz (Txh) (0--1-1) - 0-) [Ba-i] E (xt g 0-
E
(0-1((1 ) bbth 1
S V vlk 1)) |100 ||,2
+ Timax E 61 00011, F
Fk-1
+ E ( 1k-11
Hence, plugging the above inequality into Eq. (24), we have
(00') 0- -000-00000 -
(1V2Te+2) 2) vā-v(k- - 1) (VIS|A|++
+ 44olo (B)) RF 11 (
F
Ix-1
k=1
+ 4422e+11) 1) 1lk - 1) kz
S
+ r m E |1 - -050 F2-1]
A
+ E
(7x*) T 10hn
1 |Fk-1
Here we have
K
E
2 (
|Fa-1
-x-1
E
F 1
+
E
1 (T*))
0=* | F
K
K
1
[ - 00/1, |Fb-1]
F
1=1
k=1
(2)
K
4K
H22
K H
4H
ad
log
8'
V
2Km|8|IA|
max
max 1) log [1
E
(2-1(
- (((())/r+(1
k=1
where inequality (a) uses Eq. (17). In addition, we have
K E
(
K
[(0=*)
Topp
Fk-1
+
E
( -
|b [F
Am
km
31

---

Reinforcement Learning with Segment Feedback
K
( T To
FR-1]
+
Hr max
E
x (1 - -0-0 10111,FF-11
Therefore, plugging the above three equations into Eq. (21), we have
R(K)= - (4V2Te + 2) va ((K)
(VISIIAl + 4 loo (K))
K
4K
112 max
K 122
4H1
log
+
|Km|s||A| max
1
log
1+
ad
8
ad|S||AA|m
(4V27e++2
v(K)
(Vis||Al + Avgg((K) +2Hrmux
Σ
K
E
-0-"
1,
VA
k=1
K
E
(
T 6p 1k-11 1F +2 (4V2Te + 1) H v(K)
S||
+ +4Hr max
Klog
K log
'4K'
X
8'
k=1
(
exp
Hr'max
v(K)VISIIA
(ARmISTIA) max
H² max
1
}
H
K
m
ad
S|IA
SPIA)SHVVK)
+
V A
HTmax
where in equality (a), we use Lemmas C.18 and C.19, and the last three terms are absorbed into Ō(-)
D. Proofs for RL with Sum Segment Feedback
In this section, we provide the proofs for RL with sum segment feedback.
D.1. Proof for the Regret Upper Bound with Known Transition
We first prove the regret upper bound (Theorem 4.1) of algorithm E-LinUCB for known transition.
Define event
Kg
J
Σ
ti (ott)
Σ (T)))()T))) (TT))(G)))
4H²
2|S||AA1
4H²
2 A
Ko log
log
(25)
m
m
8'
Lemma D.1 (Concentration of Initial Sampling). It holds that
Pr [r[
Proof. Note that n² !...., E t5 (dr+) H² Then, using the matrix Bernstein inequality (Theorem 6.1.1 in (Tropp et al., 2015)), we can obtain this lemma.
... x Ko and Kg fixed before sampling, E|y,H ( = E d(T))(TT)) J] and
Lemma D.2 (E-optimal Design). Assume that event J holds. Then, we have
Ko
(6+))T
1
112
k= t=1
32

---

Reinforcement Learning with Segment Feedback
Proof. Using the guarantee of the rounding procedure ROUND (Theorem 1.1 in (Allen-Zhu et al., 2021)) and the fact that Al
Ko 2
we have
Ke
m2 (T)
Σ
E
Σ (()))(T))))) |
m
$ <(1+7)
Ko Σ w² (T) (T))
Browa
=Ell
(1 71+
Kn
Let m-in()) denote the minimum eigenvalue. Then, we have
Ko
mmin
A=1
1=1
Ko
m
Ko.
E ETaN Σ ((rc)olas
B Σ ((T.)O(T))
(
minn
Ko
Ka
Ko
2 7min
Σ E
Σ (
(
E BrooE
Σ ((T))((T))
k=1
1=
Ko
4H²
4H²
21S||A11
log
Ko
log
(26)
(1 + 2)²*
m
8'
m
8'
Let Vkg and
1
4H2
(|
4H²
f(x)
2
log
x
log
H
(1 +1+10 7)2=
m
8'
m
According to the property of quadratic functions, when
4H² m
log
4112 m
log
(251,1)
+ (1+9)0
4112
log
+ H22
8¹
m
(27)
(1+7)=²
we have f(x)= 2 0.
To make Eq. (27) hold, it suffices to set
2
(1 (1+))
4H²
(215)1A))
4H²
(2/)|_A) |AA|
2
)
Ko 2
2.
log
+ +
log
4
8'
8'
(2|S||AA)
5H2 log
(1 (1+7)²*
8'
(1 + (2)
10H72 (1 +7)=²) log (2|
m
8'
Furthermore, since || w² (I) B Eq. (26) smaller than !1, it suffices to set
Em ((T:)((TT)) []
H and then 2" > H² to make the right-hand-side in
Kg 2 26HH + (2))
log 8'
33

---

Reinforcement Learning with Segment Feedback
Therefore, combining the definition of Ko and Eq. (26), we have
Ku
Σ
p (T )(()))))))))))))))))))) 2 212
Omin
which completes the proof.
Lemma D.3. For any O,
loog /de((2s)) dec((T))
- ||1||A log (1+ X|ST|
kH²
log
1+1
Σ
(1)-
i=1
Proof. For any 0, it holds that
m
det(Ex) det
Ek-1 Σ
(
m
(lct(Ex-1)ee det
I+ Σ
(h--1)
E
t ( ((Ex)))3
m
x5 2
det(EEx-1) 1)
1
i=1
k
2
= (el
II
1 +
Σ
#=1
1=1
Taking the logarithm on both sides, we have
m
2
log (E{) = log det) +
Σ
log
+
x
==1
i=1
Then,
m
2
(de((Ex) dett(A7)
log
1
Σ
log
i=1
(r(F))) [S|A
log
A|S||AA
tr(Ex)
||||||] log
A|SS |
H²a \|S||A/| km m
|S||||| log
I|S||
kH²
S S||A|| log
1+
[|S||A|mm
where (a) uses the arithmetic mean-geometric mean inequality.
Lemma D.4 (Elliptical Potential with Optimized Initialization). Assume that event I holds. Then, for any k 2 Ko + 1,
(- 1.
34

---

Reinforcement Learning with Segment Feedback
Furthermore, for any K Ku + 1,
KH²
Σ
(Et-1)-1 S
|2Km||||||lo (1+
{|S||A|m
k= Kotl i=1
Proof. Using Lemma D.2, for any k 2 Ko + 1, we have
m
Σ
65
(i-1)
N+ Eez " ( ++ = 2i (T))
EE Rd ri )T)
H
$
m²
H
S 1.
Then, we have
K
m
Km
((a-1)
1
Kn++1
Ko+
m
Km
log 1+
(Ea-1)
k= Ko+1
K
Km- 2
log
1+
(Ea-1)-1
KH2
2K m (8||A log
1+
A|S||AAI
where (a) uses the fact that < 21og(1 + x)) for any [0, 1). and (b) follows from Lemma D.3.
Define event
K: 0
000-0 5ix
HASIAAI
kH A|S|||AIm
1
AAS|[I|, Vk 0
log
1+
+2log
+ man
(28)
8
Lemma D.5 (Concentration of 0g under Sum Feedback), holds that
Pr [C]] 2 8'.
Proof. Since the feedback each segment is # sub-Gaussian given the observation of transition and ||0*|| m Tmax S using Lemma 2 in (Abbasi- Yadkori et al., 2011), we can obtain this lemma.
Define event
F opt
Σ
(Byapk [1I0 [10"|(Ew--)-1 [Fx-2] - || ((x)))))))
Ko+1
4k klog
S 5
Vk 2 Ko + +1
(29)
8'
35

---

Reinforcement Learning with Segment Feedback
Lemma D.6 (Concentration of Visitation Indicators). holds that
J= Pr
11-8'. 8'.
opi
Proof. According to Lemma D.4, we have that for any R
Ko + 1, 11 (Sx S 1, z
and then
T [1 (() [F l (((x 2.
Using the Axuma-Hoeffding inequality. have that for any fixed h: 2 Ko 1, with probability least 1
8'
242
Σ
(Braatr |1 [10'
(1 -188 S $/2- 10:4(k - Ko 1)
4k2
8'
ko+
Since _k=Ko+1
6' 20
8', by union bound over have that with probability least 8', for any & 2 Ko
4k2
Σ
(Brnstr 1) [ 11 ((5 $
2 4(k Ko
log
8
k==K++1
4k koog
4
8'
Proof of Theorem 4.1. Let = 6
3. We have PrnJ opt. 2 1 - To prove this theorem, suffices to prove the regret
bound when event J n IC n JS holds.
Assume that event J n n FS holds. Then, we have opi
R(K)
( To (6=)))
k=1
K
IAB
(100)T ( T + 3(k 1) 1100 1
1- 2 + KoH
k= Ko++
K
(10 ) 3(k 1). 110" ((2.-)) 100 Koll
Ko+1
K
28(k - 11) 11 1(I0_1)-> Koll
K
K
(K)
Σ
Erat 1Ø= Fx- 11 + KoH
k=
(9)
E Eyant [1I0 (107|(S0-))>- [F--1] KoH
223(K)
A Ko+1
233(K)
Brwen |100 1)-1 [Fk-1] - |10
11000 11 1 +10" +100"1115, 1 ,3-1 + Kool
k=
K Σ
< 233(K)
Erany [107 1)-1 14 110 (1 1) 11 x
[E-1))-
k=
Koll,
(30)
36

---

Reinforcement Learning with Segment Feedback
Optimal action: as) = =6 + Fmax
Suboptimal action: (S,, ai Faax
aj: transition Sn+1
ai transition to Sn+2
w.p. $1
r(n+1r) = (
Sn+1
Viax
w.p. $2
S
r(n+22) = =2 Tiaxx
w.p.
Sn
Figure Instance for the lower bound under sum segment feedback and known transition.
where inequality (a) follows from Eq. (28), inequality (b) is due to the definition of x², and inequality (c) uses the Jensen inequality. Plugging Eq. (29) and Lemma D.4 into Eq. (30) and using the fact that À
max m we have
HS
KH²
1
R(K) 2
log
1
+ 2log
+ maax V A/SS|AA
X|S||A||
8
4K
K
4
K log
+
2Km|S||A||s log
1+
8
||S||Al
2|5||
S||AA|
H
max
26H (1 (2*) log
8'
72
- log ((1+
KHr max
1 + log
|S||4]]
+11|||A11)
A|
D.2. Proof for the Regret Lower Bound with Known Transition
Now we prove the regret lower bound (Theorem 4.2) for RL with sum segment feedback and known transition.
Proof of Theorem 4.2. We construct random instance I as follows. As shown in Figure 6, there are n bandit states $1,.... 8n (i.e., there is an optimal action and multiple suboptimal actions), a good absorbing state 8x41 and a bad absorbing state 5n42. The agent starts from 81, ..... Sp with equal probability J. For any E [n], state 5;, one action a, is uniformly chosen from A the optimal action. state 8;, under the optimal action a., the agent transitions to 8,41 deterministically, and r(s;, a.) = ( + s)rmax, where E (0, 1] is parameter specified later; Under any suboptimal action a E (A\sss) the agent transitions to Sn+2 deterministically, and r(s;, a) = Tmax- For all actions A, r(sn+1(1 a) (g + +)rmax and r(8n+2, 2 mmax For any (s, a) E S A, the reward distribution of (s, a) is Gaussian distribution N (r(( a),
In this proof, we will also use an alternative uniform instance Iunif. The only difference between Iunif and Z is that for any i [n]. in state s,, under all actions a E A, the agent transitions to 8,+2 deterministically. and r(s;, a) = 2 Tmax-.
Fix an algorithm Let Eqnir( [-] denote the expectation with respect to Iunit- Let [ denote the expectation with respect to For any E [n] and j E [[A[]], let [: denote the expectation with respect the case where aj is the optimal action in state
8i, and N denote the number of episodes where algorithm A. chooses aj in state 8,, i.e., Nr,- = Σk 1 ( = az}.
The divergence reward observations if taking a, in 8; (1 E [m]) between Iunif and
H H m
||
(()
H
KL
+ Pmax
mmax
m
37

---

Reinforcement Learning with Segment Feedback
Algorithm 4 LinUCB-Tran
Input: 8,8' = i. A = m
L log 3 Sloog(8((1 + KH)). For any k 1, B(k)
H|S|IAI log(1 + kSH {|s||Am + 2 2og (3) + Tmax AASA
2: for == 1,...: K do
3: Os-1 f (XI + k'
k-1
i== t5 (0tt
k-= E/= of 1e
k-1
-i=1 o+ (ot)) )
4: ΣR-1 + A
5: T" + arggaax (( 0p-1 + B(k - 1) -10 11 (82-1)-1 + Es' Bs B ma aa (s)))), where Bris's a'st (81)
is defined in Eq. (32)
6: Play episode with policy *². Ohserve x* and sum segment feedback {R 1==1
7: end for
H Tmaax))
Hr max
In addition, the agent has probability only to arrive at (observe) state Hence, using Lemma A.1 (Auer et al., 2002), we have that for any E [n]. in state si.
B.y [N,,) & Eanit [N,p] + 2 V Bunit [Nt.] Hr Hr 5?.
Summing over j E [[AA], using the Cauchy-Schwarz inequality and the fact that E}1 Exnir [ = K, we have
A
K
A
B.d [ S K
H
2
π
K
Kr
E
AHHK
K +
2
Then, we have
R(K)= =
E2 V. - p=t
k=1
LAI IE [N
1
te
FmaxHl
Tmax HinaxHI K + eTmax H
2
K
Krmaxe
HK n|Al|
maxll Hl
K
A
Recall that n = |S|- -2 Let S 2 3,
2 >
n|Al p2 maxe
17 and
E
2rann
m|Al HK
Then, we have
R(K)= = Ω (000=(((V111) (ViSILA(HK)
D.3. Pseudo-code and Detailed Description of Algorithm LinUCB-Tran
Algorithm presents the pseudo-code of LinUCB-Tran. In each episode k, similar to algorithm E-LinUCB, LinUCB-Tran first computes the least squares estimate of the reward parameter f--1 and covariance matrix Σ with past observations (Lines 3-4).
38

---

Reinforcement Learning with Segment Feedback
Then, introduce the transition estimation in LinUCB-Tran. We first define some notation which also appears in algorithm SegBiTS-Tran, For any k > 0 and (s, S A, let ( a) denote the empirical estimate of p(-|s, a), and ma(s,, a) denote the number of times (s, a) was visited up to the end of episode k. addition, for any policy я, let oz (s, a) denote the expected number of times (s, a) is visited in episode under policy л empirical MDP Ph-1 (see Eq. (18) for the formal definition).
Below we establish a bound for the deviation between òل_1 and Φ" For ease of analysis, we first connect o- with a newly-defined visitation value function C% a (s; For any transition model p', policy and (s',a') E S x A regarding hitting (s',a)) as an instantaneous reward one, then we can define a visitation value function:
Che Gaisiaa (s;p') #41 (s;p')
1 s (x) =a3 + (T)) Ght1 aa ()) Vs E, Ah {
(31)
0,
E.
Ggie'aa a' (s:p') denotes the expected cumulative number of times (s',a') was hit starting from at step h under pol- icy x on MDP p', till the end of this episode. It holds that (5'6 a') = Esg GT (81 [p)] and o8-1 = Pa [G aa (s1 1)] for any (s',a') E S x A.
With the definition of G sa' bounding the deviation between رž- and को is similar to bounding the gap between the estimated and true value functions. Then, we can build a Bernstern-type uncertainty bound between 0 and 6" using the variance of Crase For any policy n, (s', a') E S x A and k > 0, define
= min { (4)
Var Pa- (oll (9741 o (.1p 1))-
Basssa't a'sk (s) Bi
13H I. 14- (5,76
+
(e.
+ (1 + 7) PA 1 (118, m2
B a's
()), H MM)))((()))
VsES, vh E {H)
(32)
h41
Baia1 Batsa .a'k (s)
0,
V.
The construction of B a aa'ke (s) satisfies (see Lemma D.10 for more details)
10% ( - (5','a < Eorup [BT .a' (01)), (dl,))ESxA.
1 -0-1-0011 -=111 s Σ Esimp [BTTO' ( (81)
(x',a')
Incorporating this transition uncertainty Esy~p [B .a'sk (81) ) and reward uncertainty | into exploration
bonuses, LinUCB-TEE -rran computes the optimal policy *² under optimistic estimation (Line 5). After that, LinUCB-Tran
plays episode with æ², and collects trajectory - and reward observation on each segment (R. Jim1 (Line 6).
D.4. Proof for the Regret Upper Bound with Unknown Transition
In the following, we prove the regret upper bound (Theorem 4.3) of algorithm LinUCB-Tran for unknown transition. Recall the definition of events GKL and in Eqs. (19) and (20), respectively.
For any ks > 0. define the set of state-action pairs
1 Σ
|SIAIH
D2
(8, (8,0)
we (8, a) H
log
H
(33)
&
==1
D3 stands for the set of state-action pairs which have sufficient visitations in expectation. Lemma D.7. Assume that event H. holds. Then, if (s. E Dr-
k
() 2
(s, a). k
Σ
39

---

Reinforcement Learning with Segment Feedback
Proof. We have
1
|
n2- 1s
2
Wy (s, a)
log
k-1
|
Whl (8,
+
Wh (3,0) - H log
4
4
8'
k=1
1
1
|S||A|
1
wer a) (s) +
Wk (s. - -Hlog
8'
k=1l
1
1
Wk (s, a) + H wk (8,a)
2
k=1
1
Wk (8,
4
M=1
where (a) is due to the definition of D3 (Eq. (33)).
Lemma D.8. It holds that
| 8'
Σ (s
= log
Proof. If (s,a) & DR, then
1
|SAA
wk ( a) < H log
+ H.
Thus, have
H
H ΣΣΣ
EΣ Σ
(((s,)) $ D&} wan(s,,)
k= h= DD
(0.0) k= ==111
a((s,a) & D&Y (x (8,0)
|IAAI
4|ST|A|HHog log
+ +
8
s 8|S||A| log
8'
Lemma D.9. Assume that event H. holds. Then, we have
K
Wk (s.n
Th (8 < ||S||||] | log(2KH).
1=
(
Proof. It holds that
(s,)
K
wh(ss, a)
ΣΣ
()
n&k 1 a)
k= h=1 (s
k= (s
40

---

Reinforcement Learning with Segment Feedback
K
wx(s, a) (s,a)
1((s,a) D
(s,a)
K
())
1((sa) E D&)
k==1 (s,a)
k= (s.a)
K
wx(s, a)
1((s,)) D&)
k= (s,a)
[8.0]
k=
A 1og(2KH),
where (a) uses Lemma D.7, and (b) follows from the analysis Lemma 13 (Zanette & Brunskill, 2019).
Lemma D.10 (Error in Visitation Vectors). Assume that event GKL holds. Then, for any k > 0 and policy x,
I <(T))11 S
Bi ,a'th ($11)
(s1|p)] and o a') = Bss BoIno GGyis' al (s1lpx-1)) in this proof, we investigate Proof. Since (s', d') = E.I~olGTi
(Gtis'
the error in GR due to the estimation of the transition model.
In the following, we prove by induction that for any E [H] and s E S, 1G (slpk-1) Gatiiaa (s|p) S B a' (s).
Gotislaa When h Hl + 1, by definition, we have Grras GH+i (slpx-1) = H41 (slp) above statement trivially holds.
Bid
aa a for any E S, and then the
(s) H41
When 2 H, if G da' (-16x-1) - G (-p)) S Bx41 als element-wise then for any S, we have
Giii Giid' a' (slpx-1) Gh Gr (s|p)]
P (s))
h41 (-1pk-1) - n (s)) G (-1p)
Comie (-10x-1) Gaill" a' (-1p)
(1 (x()) (())s) Cassia (-Ip)
Gmiss'aa al (-Ip)) L
Pr- 1111,, (1)-(((1,TTns))) (s))
Gaaeiaa (-1mx-1)
Gailia (-1) +2
Varp(- (x)) h+1
my 1 (8, Th (s))
HL
(34)
(s,1((,((($s)
where (a) is due to Lemma E.4.
Here, we have
(Geddal (-l)) Va (3) h+1
4H2L
pa (G
aa (-lp) + (s)
S Var p (( (G4l h+l (-1r-11) + 1H (a.lssmm(680 h+l (-1pe-1) - G441 (-Ip)
(s))
ngg 1 (8, TA (+))
where (a) uses Lemma E.5 and (b) comes from Lemma E.6.

---

Reinforcement Learning with Segment Feedback
Then,
(a (+)) ( o' (-1p)) L
(35)
nk- (8, (s))
Var 1-18,,7 (+1)
Gii a' (-10x-1)) L
1 (s,
4
2HT
H Pk- (5) (1)--))))))
G. (-1pe-1) - (-1p)-
n&- 1s, (s))
nk- (8, TM (s))
(le (G (-1x-1-)))
2
nu (8, (s))
L Pk- (-1s, Th (s)) G aa (11k-11) Ght1 (+1))++
(36)
n (s, (s))
where (a) is due to the fact that rry S x +.. Hence, plugging Eq. (36) into Eq. (34) and using the fact that |G .0'' (s)l [0, HI. we have
1o 'a' (s1
G G .a' (s|p)
Var Var (+))
GF:s' (-10k-1)
13H
h+1
+
T2 (s, TT (s))
n2k 1 (3,, (s)
1
Pk (-1, (s))) H
Gaid' a' h+1 (-1pk-1) - Gotid'
h+1 (110) ^ H.
Var (ll,ma G (11R--1))
13H2L
(s, TT (s))
nu (s. (s))
pk Pk-1 (-18, B (l)
+ H
A H
B% a' (s),
which completes the induction proof.
Therefore,
(5((''aa'
Esimp GT:'saa (311(1=))) E Eginp Gaii'' (sLP))
GTT'' (silpx-1)
GT: GF:s' (si11)
< Eaiop
Summing over (s',a') E S A, we obtain this lemma.
Lemma D.11. Assume that event GKI. H holds. Then, for any K and policy m,
B a' [
Eginp
H
Va (G a' (-1p) L
46H²L
< c
12
w (s)
8/
^ H,
n4- (3,
nu. 1 (8, a)
Am
and
Σ
E Exyop
B oo a' (81)
8',0' A=1
42

---

Reinforcement Learning with Segment Feedback
< 16e 3|s| H H + 192e 2 Logg
Proof. First, we prove the first statement.
For any policy n, k > O, (8', S x A. [H] and E S, we have
Ba a' (s) (s) sV
Varp. (11o,a
(0 h+1 (1))-11) L
(Grisl al
13
ng- (8,
nk 1 (8,, (8, (s))
+ Pk- 1 (-1), B (.))(())))
2
h+1 (-IPk-1) 1)) L Varp, -1
(07+1
1
+
n 1s-1(s,th(s) (s))
n 18, n (s))
2
p(- ((-ss, BxF(((((()))
1
H
2
(0x-1 (s)) p(-1s, (s)))) T
Ba+1 ((
1
Vargi (116,
(G h+1
(Gr a (-1Dx-1)) L
1
nk- 18, (s))
1k-1 1 (8,, Thh (8))
1
2
p( (s)))
B
H
2
Varp (a.n(
BB Bittiaah (.)) L
HL
1 +
2V
H
Ti- 18-1 (b))
Tuk 1 (3, TT (s))
Var Varpe- (G741
(-186-1)) L h+1 n (s,
(Gois'
13
<4/
n 14-1((8 (s,, Thh (s))
2
p(-1s, p(-1s,(T(ss) T ()(((aa*(()
1 1+
2
H
HL
+
1 H
21 H 1-1s (T(()s))((()) (s))
Buit ())
Tk- (8, (8))
Tuk (8, Ta (s))
(b)
Va- (s)) (G a' (-1p--1)) L
22H2
n2k (T)
(s, (s))
+
1 + 8)
11 p(()),
B41 (();
()):
(37)
where (a) uses Lemma E.4, and (b) follows from the fact that Vay S x + y. In addition, we have
Var (o) a' (-1x--1) h41
@ 2Varpcla. Ga (-Ipe-1)) (s.
4
(Varp(ls.m) Griee (-p)) + (. Gagei a' (-1px-1) Gh+1 (-Ip)
a'
mx-1(s,0)
4H21.
(OTos (-p)) + 4HH(-1s, (s)) T Bit' (-pp-11 + m < <Varrccoo h+1
43

---

Reinforcement Learning with Segment Feedback
where (a) uses Lemma E.5, and (b) comes from Lemma E.6.
Then,
Varp, (1).m)))))))) (G (-1px-1))
m (8,
Var Va (+)) (hi41 (+I)))
4H2L
V H p( (s))) B (-1p-11) (s,
(5, (s)))
2HL
11k (8, ())
Varp(. (4))
GR::' (-1p) L
$ 2
h+1
pl
pl. s, (s))s) Buitl (-1p--1)
n (M,1(s, (s))
L
(38)
14 (8, Th (s))
Plugging Eq. (38) into Eq. (37) and using the clipping definition of B
(s), we have
Var (s))
G aa' (.1))
46H²L
Bi a' (s) x
h+1 (s))
8/
A H
Th (s, Th (s))
Thk
+
1 +
12 H
pl p(-18,TA(8))
Baid' (.)
h+1
Using the above inequality, taking and unfolding BT:'' aa th (s1) over h, we have
B a'' (8i) (si))
E Esiop
Varpt-laa)) (G (.p)) L
46/12
< 12 w ()) 81 h=1
h+l
nx-1(s,a) A A..
(39)
nk- 1 (3,0)
Next, we prove the second statement. It holds that
K
Σ
M
E
Esiop
B
a'a't
s',0' 1m11
K
Varp(-la,a)
(G++1 Gathsosaaa (-1p) (-pp))
46H²L
12
(k,((8,a) 88/
+ nk
7k- 1 (8,
(8
a' k= k= (s,a)ED.
H
12 H A
Σ (K,((8,a)
h= Ds
Se 12 VI.
(k. a) Var s. (G h+1 (-lp))
8'.0'
A= h= (e.0)EDs
H
(K) ThE (8,
wk.n
+ t (
46H²L
n n (8,a)
A=
(e.0)ED:
km Am (s
+ 86 1122 log
5'
44

---

Reinforcement Learning with Segment Feedback
88 &8"")S|4AIIIVK
A
+ +8 log
8'
S 16 H KL (2K 192
where (a) is due to Lemma D.8, and (b) follows from Lemmas E.3 and D.9.
Lemma D.12 (Optimism under Sum Feedback and Unknown Transition). Assume that event OKL. holds. Then, for any > O and fixed policy n,
(((1)) 0 3(k - 1) - 1 1)-2 + mmax
EES B Bris''dd
aa' (atia(a'+(ss))) (81)
Proof. It holds that
(11 d0
1 08-1 ((T) (
To ( + (x) )x-1(T) 1
s ) (1x) 0k- (1((z) ( 1101 + 3(k - 1) 11 (1) 1
(Z)) 0s-1 + 3(k - 1) (-) + Tmax
Σ
Essrp (ggis ia' (81)
s'.0'
where (a) uses Lemma D.10.
Lemma D.13. For any K 2 have
K m
2K SKS)|A
KH2
S H
log 11
(2-1)-
X
A|S||AAm
A=
Proof. We have
K
K
Km
(Eu-1)
(Ea-1)
i=
k= i=1
K
H
Km
min
[2 12
mX
H²K
K
m.
05.
min
H
(Sx
k=1
iml
2H²K K
WVV
md
1))
log
1
min
X
H2
k=1
i=1
IA@
2H K
K
log
1 Σ
( (En-1)
X
1=1
IV
2K SIA
KH²
log
1+
A
A m
where inequality (a) uses the fact that x < 2 log(1 + x) for any S x < 1, inequality (b) is due to the fact that < 422 and inequality (c) follows from Lemma D.3.
45

---

Reinforcement Learning with Segment Feedback
Define event
F reg
B
BrNat (00 - |1 1(1
-
s S4H/ k log
(4k)
4k:
8
====1
Vk > 0
(40)
Event F is similar to F ope except that here the universal upper bound of l ((E is H rather than 1.
Lemma D.14. holds that
Pr [ 8'.
Proof. For any W 2 1, we have that || (1+ S 28
H and then [B 11lo 1( 1
110-11(5
Vx
VX
Using the Azuma Hoemaddng inequality, we have that for any fixed l > O, with probability at least 1
5'
[10' [F |1 (10"(((oww.))))) $ $22
4H²
4k2
2
k log
Since Σk= 00
I 8', by a union bound over k, we have that with probability at least 8', for any k 2 1,
1=1 21
E E
[1I0 (1z
[Fw-1] 11 (1x))((
s 2.
4H²
k koo
412
4k
I 4H
log
8'
Proof of Theorem 4.3. Let 8' 1. Then, we have Pr[K n FS n 9KL nH]
6. Thus, it suffices to prove the regret
upper bound when event IC FS n 9KL n H holds.
reg
Assume that event Knn
JS n SKL n H holds. For any > 0, we have reg
V (*1)) - (*s)))-\((ss)
(4)
δ 1 B(k 1). 11100-1 1(T)))((
Tmax Σ
E Exynp
B so
a't
) 10000111-1 + B(k 1) (1 + Tmax Σ
Eeiup
B t (s1))
) - T ) + ② )
km
46

---

Reinforcement Learning with Segment Feedback
+ B(k - 1). 11 (- " )1(EE-))-- + Tmax
Σ
Baynp
Bi w aa
(f (81))
8',0'
(
BT io' La (si1))
28(k 1)
+ 2r max
k=1
e'ia'
K
K
s 28((K)
> (
)1(s) (====
+ 2r Fax
Es
Bi
(41)
where (a) uses Lemma D.12, (b) is due the definition of n*, and (c) follows from Lemma D.10 and the definition of event K.
Next, we first bound E 1+)
We have
1 1 (T )|(E)-1))-
|10
11(8 =11x~-((T*) - 0011(20-11>-
K
||o5**
((50-1) + Vi
( - 600 112
K
-1 -0 13 111)
-00111)
(Et-1) +
(42)
VT
k=1
Here we have
10 1|(5, 1)-
K
| 10 F (F (xx-1) 1)
E Brarh
(10711E2 1)-1 [Fs-1]
E FrNn' k || (10Tlleaa.)-1111
( [Fk-1 ||
(50 (ss - + ||
(155 .1-1)
(5s
K
E (10")((5a11) FF || (|
+
(E2-1)
k=1
(b)
K
4K 8'
2K 2K|SIIA1 log
KH² [+ A|S||A|I
4H
log
H
(43)
where (a) uses the Jensen inequality, and (b) comes from the definition of JS and Lemma D.13. Hence, plugging Eq. (43) into Eq. (42) and using Lemma D.10, have
K
4K
2K|S|AA log 1+
KH²
hr 1 ( (1 S 4H
log
H
K
B LogTo' ('tp'''''((s))
(51)
(44)
k=
47

---

Reinforcement Learning with Segment Feedback
On the other hand, according to Eq. (39), we have
H
Var pt (a,a) h+1 (1p)) L + 46H²L
Esi B a't (s1)
Se 12
Σ
(s, a)
81
nu 19, nH.
R4 (3, 0.
h=1 8,0
Therefore, plugging Eqs. (44) and (39) into Eq. (41), we have
V v**)
4K 8
K H
< <33(K)
4H
log
H
log 1
A
{|S||A|mm
((K)
B .a (s1)
+
VX
+
maax
Es S
s',a' km
K
4K 8'
SK|S|AA log
2
23(K)
4H
log
H
1+ X|S |||
43(K)
(166 1
S
AI H
Kolog(2K1)
1926 188) |A/ L
VA
H|S|IA log ((++ A|S||AA|
KH²
1
mmax V /11/|1/1
m
KISIIA log
(1+ A|S||AI
KH²
2 +15)
KL log(KH) +
|8 (4 2 1
H
log (og(KH))
VX
@ 0
(1 Tmax) SSAAAII log
(1+
KH (S|A [S|AA]
1)) + / log( (og( log ((1+ |
KH
11
+ + rm=x)))) LAI H22 log (og(HH)))))))) log (1+
KH
=ō =1 (m+))
A (1 Tmax) ((
where inequality (a) comes from Lemma D.11, and equality (b) uses the fact that m..
D.5. A Lower Bound for Unknown Transition and its Proof
Below we provide lower bound for RL with sum segment feedback and unknown transition with the proof. Theorem D.15. Consider the problem of RL with sum segment feedback and unknown transition. There exists a distribution of instances where the regret of any algorithm must be
Ω ( Tm H HV SVSKAAAK
Proof of Theorem 15. We construct a random instance I as follows. As shown in Figure 7, there are n bandit states s1...., (i.e., there are an optimal action and multiple suboptimal actions), a good absorbing state 8n+1 and a bad absorbing state 8n+2- The agent starts from $1,-..: Sn with equal probability 1 ". For any i E [n)], in state 8,, action a, uniformly chosen from A as the optimal action. In state s., under the optimal action a.,. the agent transitions 8.+1 and 8n+2 with probabilities 2 + e and 3 E, respectively, where & (0, }) is parameter specified later; Under any suboptimal action a E AAY }. the agent transitions to 8a+1 and 8,+2 with equal probability }
The rewards are deterministic for all aattee pairs. For any a E A, r( a) = Tmax- For any i E {1,..., n, n + 2} and A, 1(8, a) 0.
48

---

Reinforcement Learning with Segment Feedback
r(s,))
Optimal action: transition Sn+1 w.p. 1
2
1
w.p.
$1
Sn+2 w.p.
Sn+1
r(5+t1r))
-max
w.p. Sz
Sn+2
((n+2r)
w.p.
Sn
Suboptimal action: transition to Sn41 w.p.
Sn+2 W.p.
Figure 7. Instance for the lower bound under sum segment feedhack and unknown transition.
In this proof, we will also an alternative uniform instance Tumit. The only difference between Tunir and I is that for any i [n], in state under all actions a E A. the agent transitions to Sn+1 and Sn+2 with equal probability 2-
Fix an algorithm A. Let Emnit [-] denote the expectation with respect to Tunir. Let E.I-] denote the expectation with respect to I. For any E in] and j E [[.A]], let [+] denote the expectation with respect to the case where aj is the optimal action in state 5t. and N denote the number of episodes where algorithm A chooses aj in state 8ú, i.e. Nij- E 1( (s:) az}.
The KL divergence of transition distribution on (st, a.j) (i E [n)) between Tunit and I is
KL
B
B
+
=
In
2
In
2
2
2
2
2
1
In
2
-
=2
In (1 4s
2
3 4
where (a) uses the fact that - Inn(1 - x)= < 2r when a E (0, 4
In addition, the agent has probability only to arrive at (observe) state 8;.
Thus, using Lemma A.1 in (Auer et al., 2002), we have that for any E [m]] state 8;.
K 1
1
E. S Eunit [Nr
+
V
n
Eunir [Nr,]] KL
B
2
1
2
+
< Euiir Camin(NNe No.l +
Eunir NN.] 462
V
2
m
= ( + Ke
Euni [Nsg]-
Summing over j E [[AA], using the
inequality and the fact that M}41 Eunit [N. = K, we have
A
A
B [Na,s] S + KEy
K.
n
Then, have
K R(K)= = Σ
V - p
E,
km l
49

---

Reinforcement Learning with Segment Feedback
2 +
(H 1)rmax K
LAI
H 1)mmax + c(H
1)rmax
Ba,
(Nas)
A 2=1
K
2 {H m)xx
K- A
K
|Ann
Recall that n |S| 2. Let [ 2 3, |
2, 2, 1n and E =
Ann K
Then, we have
R(K) = Ω (fmax HVSIS)AA
E. Technical Tools
In this section, we introduce several technical tools.
Lemma E.1 (Self-concordancce, Lemma
(Faury et al., 2020)). For any 21, 22 R. we have
exp( 11 x2l))
exp( 01 - F2
μl (x1)
< ==0
(l((1 - 2)21 + zx2 )dz S pl (x1)
I1
x2
I2
Furthermore, we have
[" p1((1- 2) + 222)dz 2 ('(x1)
1 11 x2l
Lemma E.2 (Value Difference Lemma, Lemma E.15 in (Dann et al., 2017)). For any MDPs M' and M with rewards r' and rd and transition distributions p' and p", we have that for any h E [H] and s E S,
Σ (s), at) (p' (1) (.(sss,,, V |s+ = :==
Lemma E.3 (Law of Total Variance, Lemma 15 in (Zanette & Brunskill, 2019)). For an MDP p and a fixed policy n, we have
H
Erip
Σ
rsnn (s)) (())))((((s)) (7((s)
s2 = Ex.
Var Var (V (S441()))1)) 81
The idea of Lemma E.3 was also used in earlier works, e.g., (Munos & Moore, 1999; Lattimore & Hutter, 2012; Ghesh- laghi Azar et al., 2013).
Lemma E.4 (Lemma 10 in (Ménard et al., 2021)). For distributions p,q As and function f f [0, KL s a then
- f(11 f(O) (2Var,(faa+
ba.
Lemma E.5 (Lemma 11 in (Ménard et al., 2021)). For distributions p,q As and function f: - [0, if KL 9) S then
Var,(f) S (f) 4b2a.
Lemma E.6 (Lemma 12 in (Ménard et al., ().1)). For distribution E Ax and functions f.g S - |0, b), we have
VJr < (Vr 2bp(-) Ti(() - g(:)--
50


Reviews:
[{"review_id": "FSstmiHwkr", "reviewer": "Reviewer_JY4c", "summary": "This paper introduces Reinforcement Learning with Segment Feedback, a framework where episodic MDPs are divided into \n$m$ segments, and feedback is provided at the end of each segment. The authors study binary feedback (stochastic binary outcomes) and sum feedback (cumulative rewards with noise), analyzing how the number of segments $m$ impacts learning efficiency.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our paper! We will certainly incorporate your suggestions in our revision.\n\n**1. More Experiments**\n\nThis is an excellent suggestion. However, it is difficult to perform experiments on the Atari environments before the rebuttal deadline since it would take some time to adapt our discrete state-space setting to Atari's continuous state space setting of images. However, following the reviewer's suggestion, we ran preliminary experiments on a more complex Grid World environment called Cliff Walking, which is used in the popular RL textbook [Sutton \\& Barto, 2018].\n\n\n| (0) | (0) | (0) | (0) | (0) | (0) |\n| -------- | -------- | -------- | -------- | -------- | -------- |\n|   $\\rightarrow$ (r_max)     |  $\\rightarrow$ (r_max)    |  $\\rightarrow$ (r_max)     |  $\\rightarrow$ (r_max)     |  $\\rightarrow$ (r_max)     |  $\\downarrow$  (r_max)     |\n| $\\uparrow$ start (0)     | $\\otimes$ (-r_max)    |  $\\otimes$ (-r_max)     |  $\\otimes$ (-r_max)     |  $\\otimes$ (-r_max)     |  end (r_max)     |\n\n\nThe above table depicts the Cliff Walking environment considered in our experiments. Each table cell denotes a state. An agent starts from the left bottom state (marked as \"start\") and aims to arrive at the right bottom state (marked as \"end\"). The reward of each state is marked in the bracket $(\\cdot)$ in the state. The states with $\\otimes$ denote a cliff and generate negative rewards $-r_{\\max}$. The optimal path is the path close to the cliff, and the path close to the upper wall is suboptimal.\nIn our experiments, $|\\mathcal{S}|=18$, $|\\mathcal{A}|=4$, $H=8$, $m\\in\\\\{1,4,8\\\\}$, $K=50000$, $r_{\\max}=2$ and $\\delta=0.005$. We performed our algorithm SegBiTS for $3$ independent runs under binary segment feedback, and reported the average regret with standard deviation to see how the number of segments $m$ impacts learning performance.\n\n\n| Setting | Regret of SegBiTS (Std.) |\n| -------- | -------- |\n| $H=8$, $m=1$     |  $1.114 \\times 10^6$ ($1.112 \\times 10^3$)   |\n| $H=8$, $m=4$     |  $6.365  \\times 10^5$ ($1.167 \\times 10^3$)   |\n| $H=8$, $m=8$    |  $4.544 \\times 10^5$ ($1.186 \\times 10^2$)   |\n\nAs shown in the  table, under binary feedback, as the number of segments $m$ increases, the regret significantly decreases, which matches our theoretical finding.\n\nDue to time limit, here we only present the results for this instance and binary segment feedback. We will include more experimental results on larger instances in our revision.\n\n---\n\nReference:\n\nRichard S. Sutton and Andrew G. Barto. Reinforcement learning: An introduction. 2018.\n\n**2. Non-tabular Settings**\n\nYes, we expect that similar results will hold in non-tabular settings, e.g., linear function approximation.\nIn the linear function approximation setting, it is assumed that each state-action pair is associated with a feature vector $\\phi(s,a) \\in \\mathbb{R}^d$, there exists a global reward parameter $\\theta^* \\in \\mathbb{R}^d$, and segment reward feedback is generated according to $(\\sum_{h \\in \\mathcal{H}} \\phi(s_h,a_h))^\\top \\theta^*$, where $\\mathcal{H}$ denotes the set of step indices in a segment. Since our analytical procedure is mainly based on visitation indicators $\\phi(s,a)$ and the fact that segment reward feedback is generated linearly with respect to $\\phi(s,a)$, we believe that generalizing $\\phi(s,a)$ from a visitation indicator in the tabular setting to a feature vector in the linear function approximation setting should be possible.\nWe will further investigate non-tabular settings in our future work.", "claims_and_evidence": "**Binary Feedback: Exponential Regret Reduction with More Segments**\n\nTheoretical Bounds: Theorems 4.1 and 4.3 establish regret upper bounds scaling as $\\tilde{O}(\\exp(H/m)/\\sqrt{K})$, while Theorem 4.2 provides a matching lower bound. The exponential dependency arises from the sigmoid function’s sensitivity: smaller segments reduce the effective reward scale, improving distinguishability of actions.\n\nFigure 2a shows regret decreases rapidly as $m$ increases. \n\n**Sum Feedback: Regret Insensitive**\nTheorems 5.1 and 5.3 show regret $\\tilde{O}(\\sqrt{HK})$ independent of $m$, with a matching lower bound (Theorem 5.2). The intuition is that segment-level noise and covariance matrix shrinkage counteract the benefit of more observations.\n\nFigure 2b shows  minimal regret variation across $m$ validating the theory.", "methods_and_evaluation_criteria": "**SegBiTS** (binary feedback): Uses Thompson sampling with Gaussian perturbations and MLE for reward inference. \n\n**E-LinUCB** (sum feedback): Incorporates E-optimal design to refine the covariance matrix, improves Efroni et al. (2021) by a $\\sqrt{H}$ factor. \n\nIn the experiments, the authors plot the cumulative regret to verify the theory.", "theoretical_claims": "This is a theory paper. See **Claims And Evidence**.", "experimental_designs_or_analyses": "The authors use a very simple experiment to show verify the theory results. See **Claims And Evidence**. \n\nI understand that this is mainly a theory paper, but is it possible to experiment on more complex environments than what you have used, such as Atari.", "relation_to_broader_scientific_literature": "**Bridging Classic RL and Trajectory Feedback**: The paper introduces a new RL model with segment feedback that acts as a middle ground between per-state-action feedback in classic RL (Sutton & Barto, 2018) and trajectory feedback (Efroni et al., 2021; Chatterji et al., 2021)​. This novel paradigm allows feedback at the segment level, which is more practical in real-world scenarios like autonomous driving and robotics. The authors highlight that previous works on trajectory feedback rely on the martingale property of entire trajectories (Efroni et al., 2021), which does not hold for segment feedback due to the dependency among segments within a trajectory.", "essential_references_not_discussed": "This paper properly discusses the references I know.", "other_strengths_and_weaknesses": "Please see previous reviews.", "other_comments_or_suggestions": "Please see previous reviews.", "questions_for_authors": "I think this paper deals with tabular RL. Do you expect similar results will happen in non-tabular settings?", "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": "", "extra_scores": {}}, {"review_id": "KwYTVcTtTb", "reviewer": "Reviewer_spk8", "summary": "This paper studies the problem of RL with segment feedback, which offers a general paradigm filling the gap between per-state-action feedback and trajectory feedback. The authors study two settings with binary and sum feedback, developing computationally efficient algorithms achieving nearly optimal regret upper bounds. They show that the number of segment m significantly matters in the binary feedback setting, while not that important in the sum feedback setting. They also provide regret lower bounds and experimental results to validate their claims.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our paper! We will certainly incorporate your comments in our revision.\n\n**1. Comparison with [Chatterji et al., 2021] in Formulation**\n\nThe objectives in [Chatterji et al., 2021] and our paper are different. In [Chatterji et al., 2021], the goal is to choose a policy which maximizes the probability of a trajectory getting a rating of $1$, i.e., getting positive feedback. Whereas, in our model, our goal is to maximize the expected sum of rewards over trajectories. In our opinion, both models have value and are applicable in different contexts. In particular, our model is better suited to situations where we want to solve an MDP but only get binary segment feedback.\n\n---\n\nReference:\n\nChatterji et al. On the theory of reinforcement learning with once-per-episode feedback. NeurIPS, 2021.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "There have been several works that consider RL with trajectory feedback (Efronietal.,2021; Chatterjietal.,2021).  And a recent work, Tang et al.(2024), studies the segment feedback, yet only from the empirical aspect. This is the first work to theoretically study RL with segment feedback.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n\n1. This is the first work to theoretically study the important RL with segment feedback setting. It is well motivated.\n2. The paper is well-written and easy-to-follow.\n3. The authors conduct a complete study in this topic, providing algorithms with nearly optimal regret upper bounds, and proving novel lower bounds. They also provide experimental results to support the theoretical findings.\n\nWeaknesses:\n\nThe authors consider a different setting for the binary feedback from the previous work (Chatterji et al.,2021). It would be better to explain why the setting the authors considered is better.", "other_comments_or_suggestions": "None.", "questions_for_authors": "Could you please explain more about why the setting for the binary feedback considered in this work is better than that of (Chatterji et al.,2021)?", "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": "", "extra_scores": {"ethical_review_flag": "Flag this paper for an ethics review."}}, {"review_id": "npCmo9IS1z", "reviewer": "Reviewer_FY6P", "summary": "This paper studies RL with segment feedback, where each episode in an MDP is divided into $m$ equal-length segments, and the agent receives reward feedback only at the end of each segment instead of every state-action pair. The authors investigate two feedback settings: binary feedback, where the agent receives a binary outcome per segment, and sum feedback, where the agent observes the cumulative reward within a segment. They design TS-style algorithms for binary feedback and UCB-style algorithms for sum feedback, establishing regret upper and lower bounds for both known and unknown transitions. Their theoretical and empirical results show that increasing $m$ exponentially decreases regret under binary feedback, but has little effect under sum feedback.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time in reviewing our paper! We will revise our paper according to your comments.\n\n**1. Determine the Feedback Type**\n\nWe assume an MDP setting, so the sum of step-level rewards being the trajectory reward is natural. Given this model, we can ask a human to give a score to a trajectory, which is an approximation to the sum feedback and has been considered in prior works cited in our paper. Or we can ask for thumbs up/down feedback which is the binary feedback model. So we believe that in our context, it is reasonable to assume that the type of feedback is known ahead of time since the type of feedback is designed by us. \n\n**2. Assumption on Equal-Length Segments**\n\nWe agree with the reviewer that in practice, the segment length may be unequal. However, studying segments of equal length is an important starting point which has uncovered non-trivial challenges, and we reveal a new and surprising result: segments help under binary feedback, but do not help much under sum feedback.\n\nWe believe that our algorithms and analysis can be extended to segments of variable length. For example, a natural extension is to consider that the arrival of reward feedback follows a point process. In this case, the variable segment length will affect the noise variance of reward feedback, and the sum analysis of segment visitation indicators. One idea to handle this case is to obtain high probability bounds of the segment length and the number of segments within a trajectory, and use these bounds in our analysis.\n\n**3. Experimental Comparison**\n\nWe ran preliminary experiments to compare our algorithms with the adaptations of trajectory feedback algorithms [1, 2] (reviewer's reference numbers) to the segment setting.\n\nIn our experiments, we set $|\\mathcal{A}|=5$, $r_{\\max}=0.5$, $\\delta=0.005$ and $m=2$. In the binary feedback setting, we set $|\\mathcal{S}|=5$, $H=6$ and $K=1000$. In the sum feedback setting, we set $|\\mathcal{S}|=3$, $H=10$ and $K=5000$. For each algorithm, we performed $15$ independent runs and presented the average regret with standard deviation, and average running time across runs.\n\n\n| Binary Feedback |  Regret (Std.)    |  Running Time (s)    |\n| -------- | -------- | -------- |\n| SegBiTS    | 234.26 (35.12)    | 36.98     |\n| Adaptation of \"UCBVI with trajectory labels\" [1]     | 199.94 (29.54)    | 7796.90     |\n\n| Sum Feedback |  Regret (Std.)    |  Running Time (s)    |\n| -------- | -------- | -------- |\n| E-LinUCB | 3954.66 (7.68)    | 940.15     |\n| Adaptation of OFUL [2]  | 4180.95 (12.74)    | 925.60     |\n\n\nAs shown in the tables, under binary feedback, while our algorithm SegBiTS has a slightly higher regret than the adaptation of \"UCBVI with trajectory labels\" [1], SegBiTS achieves a significantly faster running time, since SegBiTS is computationally efficient while \"UCBVI with trajectory labels\" is not. Under sum feedback, our algorithm E-LinUCB attains a lower regret than the adaptation of OFUL [2], since E-LinUCB employs the experimental design technique to sharpen the regret. \n\nThe experimental results for $m\\in\\\\{1,H\\\\}$ are similar. Here we only present the results for $m=2$ due to space limit. We will include more experiments in our revision.\n\n**4. Reviewer's Reference [2] (\"Harnessing ...\")**\n\nThe problem and focus in [2] are very different from ours. [2] considers RL with bagged decision times, where the state transitions are non-Markovian within a bag, and a reward is observed at the end of the bag. This problem can be regarded as a periodic MDP with non-stationary state transitions and reward functions in a period, and [2] adapts an RL algorithm for standard stationary MDPs to this periodic MDP to solve this problem. The focus of [2] is to handle the non-Markovian state transitions within a bag using a causal directed acyclic graph, instead of investigating bagged rewards. [2] does not consider how to infer the reward function of state-action pairs from bagged rewards, or study how the frequency of reward feedback impacts learning performance like us.\n\nWe will cite [2] and include this discussion in our revision.\n\n**5. Structural Assumptions**\n\nWe assume an MDP model, which is widely used in reinforcement learning. In the MDP model, the reward of any segment of any trajectory is the sum of the rewards of each individual step in the segment. So the type of reward aggregation is fixed by our MDP model. And for binary feedback, we assume that it is generated according to a sigmoid function, which is also widely accepted and used. Beyond these two assumptions, we didn't make any other structural assumptions. To the best of our knowledge, the fact that one gets extremely coarse information about the sum reward in the binary feedback case makes it impossible to have a common analytical technique for both feedback models.", "claims_and_evidence": "The paper's claims are generally well-supported by theoretical analysis and empirical results. However, two strong assumptions should be further discussed: \n1. The paper assumes that the type of segment feedback (sum or binary) is known in advance. Since the conclusions differ significantly depending on the feedback type, understanding the feedback structure seems crucial before applying these methods. However, in real-world scenarios, it is often difficult to determine how segment feedback is derived from step-level rewards.\n2. The assumption that each episode is divided into $m$ equal-length segments is somewhat strong and may not always hold in real-world scenarios where feedback aggregation is irregular. A discussion on the potential impact of non-uniform segment lengths on the proposed methods, along with possible extensions to handle variable-length segments, would improve the robustness of the claims.", "methods_and_evaluation_criteria": "The authors design TS-style algorithms for binary feedback and UCB-style algorithms for sum feedback, which are appropriate choices given the problem structure.", "theoretical_claims": "The theoretical claims and proofs, particularly those on regret bounds, appear correct and well-structured, with no major issues observed.", "experimental_designs_or_analyses": "Since trajectory feedback algorithms can be naturally extended to the segment feedback setting, it is important to clarify the advantages of the proposed approach over these existing methods. An experimental comparison with trajectory feedback algorithms (e.g., [1, 2]) should also be included.\n\n[1] On the Theory of Reinforcement Learning with Once-per-Episode Feedback.  \n[2] Reinforcement Learning with Trajectory Feedback.", "relation_to_broader_scientific_literature": "This paper discusses segment feedback, a topic previously studied from different perspectives in [1,2]. Building on [3], the authors design TS-style algorithms for binary feedback, and based on [4], they develop UCB-style algorithms for sum feedback.\n\n[1] Reinforcement Learning from Bagged Reward.  \n[2] Harnessing Causality in Reinforcement Learning with Bagged Decision Times.  \n[3] On the Theory of Reinforcement Learning with Once-per-Episode Feedback.  \n[4] Reinforcement Learning with Trajectory Feedback.", "essential_references_not_discussed": "The paper does not discuss \"Harnessing Causality in Reinforcement Learning with Bagged Decision Times\" (AISTATS 2025), which presents a similar problem setting.", "other_strengths_and_weaknesses": "**Strengths**\n\n1. The paper is well written, and the theoretical results appear correct, with detailed analysis and proofs supporting the claims.\n2. The counterintuitive finding that increasing $m$ does not significantly reduce regret under sum feedback is well-supported by both theoretical analysis and experimental results.\n\n**Weaknesses**\n\nSee comments.", "other_comments_or_suggestions": "1. (Claims And Evidence) Discuss potential extensions to non-uniform segment lengths to enhance practical applicability.\n2. (Claims And Evidence) In practical applications, how do we determine whether segment feedback follows the sum or binary structure, or if it follows a different aggregation rule altogether? Since the proposed methods rely on knowing the feedback type, addressing this question would improve their real-world usability.\n3. Can the proposed methods be understood as making structural assumptions about the reward aggregation process? If so, does this imply that any form of segment feedback (inclued binary segment feedback) could, in principle, be analyzed based on sum segment feedback as a general case?\n4. (Experimental Designs or Analyses) The paper does not include a comparison with trajectory feedback methods. Since trajectory feedback algorithms can be extended to the segment feedback setting, an experimental comparison would strengthen the empirical evaluation and clarify the advantages of the proposed approach.\n\nI will look forward to your response.", "questions_for_authors": "See comments.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper provides a theoretical analysis of Reinforcement Learning with segment feedback. They study two settings with binary and sum feedback, developing computationally efficient algorithms achieving nearly optimal regret bounds for each one of these. During the discussion phase with reviewers, it was agreed this work provides a meaningful contribution to the study or RL with novel forms of feedback. That is why I am recommending acceptance.
Decision: Accept (poster)