Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
Authors: Zihan Zhang
Yuxin Chen
Jason D. Lee
Simon Shaolei Du
Ruosong Wang
Venue: ICML 2025 poster (2025)
Keywords: reinforcement learning
online learning
trajectory feedback
Primary area: theory->reinforcement_learning_and_planning
TL;DR: We prove a near-optimal regret bound of $\tilde{O}(\sqrt{SAH^3K})$ for finite-horizon MDP with trajectory feedback.

Abstract: In this work, we study reinforcement learning (RL) with trajectory feedback. 
Compared to the standard RL setting, in RL with trajectory feedback, the agent only observes the accumulative reward along the trajectory, and therefore, this model is particularly suitable for scenarios where querying the reward in each single step incurs prohibitive cost. 
For a finite-horizon Markov Decision Process (MDP) with $S$ states, $A$ actions and a horizon length of $H$, we develop an algorithm that enjoys an asymptotically nearly optimal regret of $\tilde{O}\left(\sqrt{SAH^3K}\right)$ in $K$ episodes.
To achieve this result, our new technical ingredients include
(i) constructing a tighter confidence region for the reward function by incorporating the RL with trajectory feedback setting with techniques in linear bandits and 
 (ii) constructing a reference transition model to better guide the exploration process.

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
Zihan Zhang'
Yuxin Chen 2
Jason D. Leed Simon S. Du
Ruosong Wang*
Abstract
each step, the doctor decides action (e.g., taking certain medicines) and observes the new state (e.g., information like body temperature or blood pressure). On the other hand, the state-action dependent reward signal could be costly to observe, since the extent to which the disease has been cured might be expensive to measure it requires comprehensive medical tests. In this case, in order apply the RL framework, it is more reasonable to assume that the agent observes only the current state in each step, and the cumulative reward value is revealed only after a whole trajectory is finished.
In this work, we study reinforcement learning (RL) with trajectory feedback. Compared to the standard RL setting, in RL with trajectory feed- back, the agent only observes the accumulative reward along the trajectory, and therefore, this model is particularly suitable for scenarios where querying the reward in each single step incurs pro- hibitive cost. For a finite-horizon Markov Deci- sion Process (MDP) with S states, actions and a horizon length of H. we develop an algorithm that enjoys an asymptotically nearly optimal regret of ò (VSAHHK) in K episodes. To achieve this result, our new technical ingredients include (i) constructing a tighter confidence region for the reward function by incorporating the RL with tra- jectory feedback setting with techniques in linear bandits and (ii) constructing reference transition model to better guide the exploration process.
As another example (which was also discussed in prior work on RL with trajectory feedback (Efroni et al., 2021)). in autonomous car driving, defining state-action dependent reward function could be challenging task, as it requires associating all possible state-action pairs with a real number. A possible workaround is to have human experts involved to produce the reward signals. However, defining reward signals could be a highly subjective matter, and waiting for reward values from human experts could take unacceptable amount of time for RL algorithms.
To circumvent issues mentioned above, practitioners often rely on heuristics (e.g., reward shaping (Ng et al., 1999)). RL with trajectory feedback has been recently proposed by Efroni et al. (2021) as a more principled framework. In this framework, the agent no longer has access to a per state- action reward function. Instead, it receives the cumulative reward on the trajectory as well all the visited state-action pairs. Clearly, this new feedback model is harder than the standard RL setting and could be more applicable for real- life scenarios like healthcare or autonomous driving as men- tioned in previous paragraphs. In the work by Efroni et al. (2021), algorithms based on the principle of optimism and Thompson sampling were proposed for RL with trajectory feedback. Although the algorithms in (Efroni et al., 2021) achieve VK-type regret bounds, the dependence on the number of states is far from being asymptotically optimal, and obtaining asymptotically nearly optimal regret bounds
1. Introduction
In the standard reinforcement learning (RL) framework, it is assumed that the agent acts in an unknown environment, and in each step, the agent receives feedback in the form of a state-action dependent reward signal, and then transits to the next state. Although such an interaction model might be reasonable when a simulator is available, for real-life applications, such feedback model could be hard to realize. For practical scenarios, querying the reward function could be costly, or even impossible in certain circumstances.
As motivating example, in healthcare, a doctor repeatedly interacts with a patient for the purpose of treatment. In
'aaul G. Allen School of CSE, University of Washington ?Wharton Statistics and Data Science, University of Pennsylvania DDepartment of ECE, Princeton University *CFCS and School of Computer Science, Peking University. Correspondence to: Ru- osong Wang <ruosongwang @ pku.edu.cn>.
'In this paper, by asymptotically nearly optimal, we mean that the regret bound is optimal up to logarithm factors when the number episodes K approaches infinity, which is standard in the RL theory literature (cf. (Azar et al., 2017; Agarwal et al., 2020)).
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
in this setting is the main focus of the present paper.
ically nearly optimal regret bounds, show that such an algorithm does not exist.
Our contribution. In this paper, we prove the first asymp- totically nearly optimal regret for RL with trajectory feed- back. Our main result is summarized as follows.
2. Related Work
RL with limited feedback. As mentioned in the intro- duction, RL with trajectory feedback was first introduced by Efroni al. (2021). Compared to the results in Efroni et al. (2021), our regret bound is asymptotically nearly op- timal, while the results in Efroni et al. (2021) are not. In Section 4, detailed comparison with the results in Efroni et al. (2021) from a technical perspective will be provided.
Theorem 1.1 (Informal version of Theorem 5.6). Fix 8 > O. There exists algorithm (Algorithm 1) such that for any episodic MDP with trajectory feedback, with probabil- ity 1 - 8, the regret in K episodes is upper bounded by Ô (VSAH&K)) 2 for sufficiently large K.² Here S is the number of states, A is the number of actions, H is the hori- zon length, and K is the total number of episodes.
Cohen et al. (2021) designed an algorithm with v VK-typo regret bound that works for RI. with trajectory feedback even when the noise is adversarially chosen. However, the regret bound by Cohen et al. (2021) is not asymptotically nearly optimal. Chatterji et al. (2021) considered a more general setting, where the reward revealed to the learner is no longer the cumulative reward on the sampled trajectory, but instead drawn from a logistic model. It is an interesting future direction to generalize our techniques to their setting and obtain asymptotically nearly optimal regret bounds.
It is known that for episodic MDPs, even if the agent has access to the per state-action reward function, the regret bound of any RL algorithm is lower bounded by (((SAH*3) (Jin et al., 2018; Domingues et al., 2021). Thus, the regret bound in Theorem 1.1 has nearly optimal dependence on S, A and H as K approaches infinity, and therefore, our regret bound is asymptotically nearly optimal.
Conceptually, Theorem 1.1 shows that RL with trajectory feedback, seemingly harder setting, has the same asymp- totically optimal regret bound as the standard RL setting. Therefore, at least statistically, RL with trajectory feedback no harder than the standard setting.
Very recently, Cassel al. (2024) considered RL with tra- jectory feedback in linear MDPs (Yang & Wang, 2019; Jin et al., 2020) and achieved a regret bound of d Translating their regret bound to the tabular setting con- sidered in the present paper, the regret bound would be Ö(V ( ()) which is far from being asymptotically optimal. It would be interesting to generalize our techniques to RL with trajectory feedback when function approxima- tion schemes are used and obtain improved regret bounds.
Why trajectory- feedback is no harder. is well-known that in tabular MDPs, learning the transition kernel is harder than learning the reward, and RL algorithms usually pay more for learning the transition kernel. As result, if the price of learning the rewards in RL with trajectory feedhack is upper bounded by that of learning the transition kernel, RL with trajectory feedback would have the same asymp- totically optimal regret bound as the standard RL setting. As will be shown later in Section 4, the regret incurred by learning the reward is indeed upper bounded by that of learn- ing the transition kemel, and therefore, RL with trajectory feedback is no harder than the standard setting statistically.
Preference-basee RL (PbRL) (Wirth et al., 2017) is another RL paradigm to deal with the lack of reward signals. In PbRL, the agent receives feedback in terms of preferences over a trajectory pair instead of numerical rewards values. Compared to RL with trajectory feedback, PbRL is concep- tually harder due to the lack of numerical feedback, and indeed, existing regret bounds for PbRL in the tabular set- ting (Novoseller et al., 2020; Xu et al., 2020b; Saha et al., 2023) is much worse than the nearly optimal regret bound obtained in this paper. PbRL was also studied in function approximation settings (Chen et al., 2022; Wu & Sun, 2023; Wang et al., 2023) and the bandit setting (Yue al., 2012: Falahatgar et al., 2017; Bengs al., 2021; Xu et al., 2020a).
Computational efficiency. Despite achieving an asymp- totically nearly optimal regret bound, the algorithm for achieving Theorem 1.1 is not computationally efficient as it requires maintaining a set of deterministic policies whose cardinality could be exponential in S and H, and an in- triguing open problem is to design computationally-efici algorithms for RL with trajectory feedback with asymptot-
Linear bandits. Linear bandit is a classical setting for modeling sequential decision- problems, and various sample complexity bounds and regret bounds have been obtained in this setting and its generalizations (Dani et al., 2008; Abbasi- Yadkori et al., 2011; Li et al., 2019; Filippi Abbasi-Yadkori et al., 2010; Li et al., 2019). We refer readers to Lattimore & Szepesvári (2020) for a comprehensive survey on this
Throughout, we use Ö(:) to suppress logarithmic factors. "A our main focus is obtain asymptotically nearly optimal regret bounds, here we consider the case that K approaches infinity while S. A and H are all fixed.
"In fact, the regret lower bound proved by Jin et al. (2018) is ((SSAH2T) with T = KH, which would be translated to R(VSAH** using our notations.
2

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
topic. As observed in Efroni al. (2021), there is a deep connection between RL with trajectory feedback and linear bandits. More specifically, RL with trajectory feedback can be understood as an instance of linear bandits over a convex set. Such a connection is also exploited in the present paper which will be discussed in more details in Section 4.
In each episode, the agent decides policy and observes the induced trajectory ($1, 01; 82, a2;-...; 8H; "M,;a At the end of each episode, the agent also receives a trajectory reward feedback Y = Σh= The where each 1% is independently drawn from RA an). We use T denote the set of all possible trajectories. Note that [7] = (SA)".
For a policy n, the Q-function and V-function are given by
Regret bounds in the standard RL setting. There is a long line of work studying regret minimization in RL (Kakade, 2003; Jaksch et al., 2010; Azar et al., 2017; Jin
(T, a) = ExT
Σ
Th (sw aN) (sh. = (s.
et al., 2018; Zanette& & Brunskill, 2019; Zhang & Ji, 2019; Zhang et al., 2020; Li et al., 2021; Zhang et al., 2022b: 2024). In particular, an asymptotically nearly optimal regret upper bound of Ô (VSAH*K) has been known in the lit- erature (Azar et al., 2017), and more recent work typically focuses on the lower order terms. i.e., by considering the case where the total number of episodes K is not that large compared to the number of states S, the number of actions A and the horizon length H. In particular, the most recent work by Zhang et al. (2024) shows that an upper bound of δ [VSAHKK+ + KH) can be achieved for any K 2 1.
H
(+) = Fx
Σ
The (swr, (nxssca)))) =
Li/=h
The optimal Q-function and V-function are given by
(7(
sup as)
FEllaa
(i) = max VA (s) (T)
= max (s,a).
rEllaa
We use 'T" denote an optimal deterministic policy such that (s, a) = 0% (s, a) for all (s, a, h). Moreover, for given transition kernel p and reward distribution r, define
In this paper, to learn the transition kernel, we use pol- icy elimination framework similar to that in Zhang et al. (2022b). Compared to our algorithm, the algorithm in Zhang et al. (2022b) is designed for the standard RL setting and does not require the tighter confidence region construction for rewards. Such confidence region construction is the main technical contribution of the present paper.
Σ rn (sn, an) Lh=1
W"(r,)) Ex.
W (r,pp)) max rellact
WF (r.
Let x* be the policy executed by the agent in the k-th episode, the regret is defined by
K
3. Preliminaries
Regret(K) = Σ (R, (R, (R,
(R,
Throughout this paper, for an integer N 2 use [N] to denote the set NN.
Other Notations. Given a policy π and transition kernel p. we use Ex,pl (Prr,>l-)) to denote the expectation (proba- bility) under the policy and transition kernel p. In particu- lar, for a trajectory r = {(*h, ) 1== Pr [T] is the prob- ability of observing under т and We also define the oc- cupancy function (s a, h) = Er,r [[((), a,)) = (s. a)]] We use d= to denote the -AHH-dimensional vector {dz (s, a, ha)sss..))ESxxx
Episodic RL with trajectory feedback. An MDP is defined as M = A, P.P p), where S is the state space, A is the action space, R = (R, ().()))x)) is the unknown reward distribu- is the unknown transi- tion kernel and y is the initial distribution. For state-action pair as, S x A, a level h E [H] and state s' E S, Pe,a.h.'' is the probability of transiting from s to s' at level h after taking action a. We assume that the reward distribu- tion (s, a) is supported on [0, 1] with mean (s, a).
tion, P (a.a)
We may also regard R as a AHH--dmmnssion vector (Ra,s, (e.,,, (x...)))SxxxxH]] Given trajectory
{(sh, an) ) we let o, E SAR to be the vector such that (sh, a.)]. We use I to denote the SAH -imeennsia identity matrix. We use E to denote the complement of the set E.
[((s'aa')
A (deterministic) policy и can be viewed as collection of mappings ( where each Fa S - A is a mapping from the state space the action space. We use Naat to denote the set of all deterministic policies. We also consider mixtures of deterministic policies which can be seen as a distributions over N A policy ा induced a random trajectory ($1, a1, $2, SH. az), where $1 ~ 14, an- = Th (8%. and 8141 ~ P an h for all h E [A].
4. Technical Overview
In this section, we give an overview of the technical chal- lenges for obtaining the asymptotically nearly optimal regret
$It well known that optimal Q-function and V-function be achived by a deterministic policy.
3

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
bound for RL with trajectory feedback, together with our approaches to tackle these challenges. To explain the high- level ideas, we first consider the simpler setting that the transition kernel P is known, and then switch to the general setting in which case the transition kernel is unknown.
trajectory feedback, each arm in the linear bandits instance corresponds deterministic policy in the original MDP.
Our construction of the tighter confidence region is based on the following two observations:
Although the total number of deterministic policies could be as large A the number of trajectories is [T] = (SA)# which is much smaller than the number of deterministic policies;
Connection with linear bandits. As observed in prior work (Efroni et al., 2021), when the transition kernel P is known, RL with trajectory feedback can be seen as an in- stance of linear bandits. More specifically, in each episode, suppose the trajectory observed by the agent is т, the ex- pected trajectory reward feedback would be o. R. i.e., linear function with respect to o,. Based on this observa- tion, Efroni et al. (2021) showed how to build appropri- ate confidence regions for RL with trajectory feedback by adapting analysis for linear bandits algorithm and obtained a regret bound of Ô (VS2AAHAA)
For any deterministic policy x. dz = =E PTa.PIT) or which is a convex combination of {Ø+ IEET-
Based on these observations, instead of building confidence region for [(d))" T (R R) for each deterministic policy and applying a union bound over all policies which result in suboptimal regret bounds, we consider the following event
Although it is plau-
sible to improve their regret bound to Ô (VS*AI*K)
&
VT E T, 07
(0. ( - R))
by more refined analysis, it is unclear how to improve the dependence on S in their regret bound. Indeed, in the work by Efroni et al. (2021), RL with trajectory feedback is naively treated as an instance of linear bandits with feature dimension = SAH, and the best known regret bound for any linear bandits algorithm is O(d/T) (Dani et al., 2008), or ((VdT log K) for linear bandits with K arms (Bubeck al., 2012). Since there are ASH policies for an MDP, and each of them can be seen as arm in the linear bandits problem instance, improving the order of S in the regret bound of prior work requires fundamentally new ideas.
[T 1- log ( H ()= (2)
(77)
Sc min
where is an absolute constant and 0² < H is constant such that {r - - RT is a group of independent zero- mean o² -uuuuaauuni random variables. By standard con- centration arguments, E holds with probability at least 1 - 8. We assume & holds in the remaining part of the diseussion.
Note that second observation mentioned above implies that for any policy n,
Tighter confidence region based on trajectories. In or- der to achieve a minimax optimal regret bound, our first new idea is to build a tighter confidence region by exploiting structures of the linear bandits instance associated with RL with trajectory feedback. Before getting into more details, we first review least squares regression (LSR), an estimator commonly used in linear bandits algorithms (also in prior work on RL with trajectory feedback (Efroni et al., 2021)).
(d)) (R R)
Σ
07 (R RR) p|
FE
Pr Pra,p(7) min { (ooT/V-T-----0oo H (lg((1 m})
0
Σ TET
Given a set of data points f Y' where for each 1 S 1 < T, nh is the policy executed in the 1-th episode, r' is the trajectory sampled by executing &' and the Yt is the trajectory reward feedback. Clearly, E[y"] = o_. R, which motivates the design of the LSR estimator
< H
Pr min (07 A A-l1011 13
(3)
TET
where the last step holds by Mouchy-Schwarz incquality, the fact that |T| (SA)", and suppressing log(SA) factors into the Ō(.) notation.
T
T
i = arg min Σ (Y' - oT.r)²² A|rr|3- A > o Y
Exploration by optimal design. During the execution of the algorithm, we maintain a set of deterministic policies II that have not been eliminated. According to (3), in order to prove a uniform upper bound for (dr)) ((p.))((a - - for all deterministic policies x E II, it suffices to bound
1=1
(1)
where A = = O. is the information matrix. Optimism- Optse linear bandits algorithms typically main- tain a set of arms, and eliminate arms outside the confidence region during the execution of the algorithm. For RI. with
max TELl
Σ TET
Pr Pr,,p[T] min (Ø_ A- 6r, 1}.
(4)

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
For this purpose, we need to carefully choose a of poli- cies |== so that the quantity in (4) is upper bounded. As another new technical ingredient, we show how to Theorem (see Lemma B.1) to our setting. In particular, in Lemma B.2 in the supplementary material, we show that there exists π which is a mixture of deterministic policies, such that
where eg = =Ō =::0VVAAATA (VSAH>/K)) it holds that क" E lI++1
and
generalize the classical Shefer-Wolfowiee
P) (R. (V
for any т E 44+1 Therefore, the regret in the (e + 1)-th batch is bounded by
max mEll
Pr PIToo A or = SAH,
(5)
Ö(VSAH3K),
TET
which means that the total regret is most Ö(VSAH*K)
where Ag == EET pr Therefore, by running π for T steps, we could collect an information matrix > cT As with high probability for some absolute constant e e>> 0. Combining (3) and (5), we obtain that
Dealing with unknown transition kernels. In the discus- sion above, we assume that the transition kernel P is known. Now we discuss how to remove such an assumption by learning the transition kernel in an online fashion. In order to implement the elimination- based online batch learning process mentioned above, we only need the transition kernel (i) to design the exploration policy so that (5) is ensured and (ii) to ensure the policy elimination step in (8) can be accurately implemented.
max RE
(dpp) T - R2) s LH(N
(6)
In summary, with the arguments above, for any policy set II, we are able to collect dataset {T', ,", y' in T episodes obtain R. such that
To achieve (i) and (ii), we first obtain a reference transition kernel P. which serves as an efficient tool to help design the exploration policy. Following the regret analysis for online batch learning in (Zhang et al., 2022b), the regret stemming from learning P can be bounded by Ó(V SAH*K) (with lower order terms ignored). Moreover, for (i), an exact solution for (5) is not necessary. Instead, an approximate solution with a constant competitive ratio is sufficient to guide the exploration process, which could be found with the assistance of a reference model. For (ii). by using samples obtained by executing the exploration policy found in (i), could build an empirical transition kernel which would be sufficient for implementing the policy elimination step in (8).
max well
W -
#ell max (dp) TR R)
s o (VSAH3/T)
Online batch learning by policy elimination. Finally, we show how to combine the two technical ingredients mentioned above into the framework of online policy elimi- nation. In this framework, the learning process is divided into consecutive batches. The algorithm maintains policy set during its execution. Suppose the policy set maintained is II, at the beginning of the Ł-th batch. The algorithm will eliminate a subset of policies from II, to form II++1 in the f-th batch. Initially, we set IT, to be the set of all determin- istic policies. Moreover, there are (log log K) batches for the whole algorithm, and there are K₃ 2k- & episodes in the b-th batch.
Computational efficiency. Given an approximate transi- tion kernel, the algorithm by Zhang et al. (2022b) achieves computationally efficient batch learning in the standard RL setting. In contrast, in the RL with trajectory feedback set- ting studied in this work, even with full knowledge of the transition kernel, we suffer from computational inefficiency due to the lack of reward information. In our algorithm, we maintain a subset of deterministic policies and solve opti- mization problems over the remaining policies (cf. Line 4 in Algorithm 3). Recall that initially we include all deter- ministic policies, and therefore the number of remaining policies could be exponential in S and H during the execu- tion of the algorithm. To our best of knowledge, no existing algorithm could solve such optimization problem efficiently even if the transition kernel is known and approximation is allowed, and therefore, our algorithm is also not com- putationally efficient. We leave obtaining computationally efficient algorithm as an interesting future direction.
As an invariant, during the execution of the algorithm, we always have that the optimal policy x= E II, for all f. By (7), for each L, we obtain a set of estimated reward values fe such that
<0 (VVSHHI)))))
max (R.)) so xell.
By setting
lle+1
{ r E 11:: max WR ((, (R Se
E'lll
(8)
5

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
5. Algorithm
Raw exploration. In Algorithm 2, we invoke Raw-Exploratiion (see Algorithm 6 in Appendix C) to learn a proper reference model. This algorithm is based on Algorithm 2 (Zhang et al., 2022b), with slight modification so that it could be applied to general policy set IT.
In this section, we present our algorithm. The specific choice of the parameters could be found in Appendix A. The main algorithm (Algorithm 1) has two stages.
The first stage (Line 3 in Algorithm 1) serves to acquire coarse approximation p of the transition kernel P, guiding the design of exploration policy. Instead of approximating P to the L1 norm,, it is required the trajectory distribution under P could be covered by that under p up to a constant
Algorithm 2 MModel (Ko, K)
1: Input: length Kg, total length K;
2: Ki 10000 K₂ Ko 3Ki
3: P1 f Rww.Exploration////
K1);
ratio. Formally, we have the definition below to measure the similarity between
4: R < Reward-RRgressionn?? Ha R));
transition kernels.
5: II + -Plan(R, P1. K1, Hee c0);
Definition 5.1. For two transition kernels p and p', we say p is an (m, .:) aapproximation of p' with respect to a set of policies II iff S x A x S x [H] could be divided into two sets IC and KC such that
P₂ +- Bon-Exploran (nT,, K2);
return: {P2, }
Properties of the learned model are summarized as below.
lop(m) 1 Pa S Ps Se 1ng(m) Peannss (ss,,,,,s')E E
Lemma 5.2. By running Mef-Mode2(Kin K), with prob- ability 1 5, it holds that
(9)
P VT E Elatti
(10)
Po is (3, -aproxiappooiniaai of P w.E.t I[,;
max Pra [K S x. nEll
(11)
x² El;
where prx is the probability of visiting K.C under policy and transition kernel q.
WW P) 2 W*( (R. - for any π E lI1
The second stage consists of several consecutive batches. In each batch of the second stage (Line 5 in Algorithm I), we search for an exploration policy स by using the coarse model p obtained during the first stage. Subsequently, we execute मे to collect the trajectory feedback, and construct reward confidence region R with least squares regression to conduct policy elimination.
The proof of Lemma 5.2 is postponed to Appendix D.1
5.2. Policy Elimination with Reward Regression (the Second Stage)
Algorithm Traj -Larnning(p, R, II)
I: Input: reference model p, length K, policy set II;
Å <- Reward- in K, IT);
Algorithm
Inext + Plan p, K, k1;;;
1: Input: total number of episodes K.
4: return: I
2: Initialization: Set Kp. L, (Kehgegus co. oo, k ac-
cording to Appendix A;
3: (P,Il} t- f ReodM (Ko, K):
We present the algorithm for reward regression and policy elimination in Algorithm 3, which has two parts. In the first part, the goal is to learn the reward by least squares regression, while the goal of the second part is to eliminate policies in II based on the reward learned in the first part.
4: for f = 1,2, T. do
5: 11 - Learning(P, Ke, 1e);;
6: end for
Throughout Algorithm 3, the agent only executes policies within II, and therefore, the regret incurred by running Al- gorithm 3 is upper bounded by K maxxen (W" (W"(R, P) W P)) where K is the total number of episodes.
5.1. Learning the Reference Model (the First Stage)
We present the algorithm for learning the reference model in Algorithm 2. The algorithm consists of four stages. Initially, the goal is to acquire a coarse reference model. In the sub- sequent stage, the focus shifts to learning coarse reward estimator. The third stage involves gathering samples to execute policy climination, ensuring that the remaining poli- cies are approximately O(c)) opttmall. In the final stage, we invoke Exx-Exploxzz ion with a larger length to obtain a more refined reference model.
Reward regression. We compute the optimal design pol- icy according to the reference model p. and then collect trajectory feedback to learn the reward function. It is worth noting that the least squares regression estimator R (see Line 12 in Algorithm 4) might escape [0, 1] and thus we construct reward confidence region R (see Line 13
6

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
Algorithm 4 Reward Reward-Regreseee Regression(p,k K I1)
(u. P) yffor any II; W P) W
1: Input: reference model length K, policy set II;
max+ell [ (u, P) WT P)
2: À -
1 SAHAK A AI, K1 + ) )
K
c < 2(b + 2). where
3: for 1, ...,, K1 do
4: n² < arg max Σ Pr. p min A 1 or 11;
b 30 SAH2 + Sy) log (SSAH
Tell FET
5: A + A+ ETe Pr [T m 10..1
K
6: end for
360.5 AH3 log 8
(8SAH
+ 4SA112
7: á be the mixed policy which plays x² with probability
K
1/K, , for each 1 <. t S K1;
8: for = 1, .., do
Let 1lnxxt = Plan(u, P, K, el, With probability 1 1 8, it holds that:
9: Run क to get trajectory 7' and trajectory reward feed- back yt:
end for
the optimal policy 't" E eTexxti'
11: Å (2dlo(2d/6)1++ Σ 0.:0..;
12: R + -- === O'
WR P) 2 W (R, P) 2e for any π E nnextt-
R {R [0, 1|SHH
10 (R- R)]
Lemma 5.4 states that, given some proper reference tran- sition kernel and policy set II such that x¹ E II, AI- gorithm 5 could return a policy set with better confidence bounds by policy elimination.
3 / 112 log" ASAH 10 1 VT E T};
14: if R # then
15: Choose R E R;
16: else
17:
0:
Algorithm 5 Pl (lan c),
18: end if
I: Input: reward function u, reference model p, episode
return: R
length K, policy set II, threshold
2: न x- -Design([T, p);
3: Execute म in the next K episodes, and collect samples
in Algorithm 4) instead. For Algorithm 4, we have the following lemma to bound the error of reward regression.
as D;
Na, a) < the count of (s, a, in D; for (s, a, h) E S A x [H] do
Lemma 5.3. p is a (3, approxxmaaaiio of P with respect to II for some x 2 0, with probability 5, it holds that
Pa.ah the empirical transition probability of the samples of (s, h) in D;
max TEll
W (R, 1 (R,
7: end for
8: 1lnext + - I1: (T 2 max W WT (u, =c]
(SAHH)
SAH log" ( 2SAHK
return: N
log?
x + 325
K
'10: Function: Design(II,p) p);
11: Let = (Mabren E A be the distribution
where R = Reward-Regrrescoon...f K.II.
Σ as,
A + argminy-
max y (X)).nnEA"
"'EIl 3,4, Σ, (s,
Policy elimination. With the reward estimator Å, we pro- ceed to construct the confidence region to facilitate policy climination. As described in Algorithm 5, for every batch, the reference model p and policy design to find exploration policy 7 with nearly optimal coverage. By ex- ecuting म, we obtain an empirical transition model which is then used to eliminate policies. Formally, we have the uniform convergence guarantee for Algorithm 5.
12: return: स be the mixed policy which plays Il with probability A
Based Lemma 5.3 and Lemma 5.4, summarize the guarantees of Algorithm 3 as below.
Lemma 5.5. Let = log² 16SAHK Let 1lnext
Lemma 5.4. Fix F, y, 2, 2 0. Assume that
Traj-Learning(p III.). Fix F M
0. Assume that
IT; p is a (3, .1) apprrxxiiaii of w.E.L. II;
x²* E II:
is (3, (.8.))aappxximmatoon of P. with respect to II;
7

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
W"(R, W (R, (R,
ÿ for any II;
R 2 2 SAH* + 6V AH S).
1005 A
iss T) appproxmmaaiii of P with respect to II;
+
K
K
WF(R, W (R.
for any E Ig
With probability 1 8, holds that x² E II and
2 20( SAHHI.).
SAH
+ 6V R
SPAH
100 AH
+
Kr
Kr
W
2x
for any E nnext.
Using Lemma 5.5, with probability 1- 8, it holds that (1) x² E 114+1; (2) (T P) 2 (R, P) 22g for any π Π1+11 By induction on & = 1.2..... L, with probability [L-1) it holds that
The full proofs of Lemma 5.3, Lemma 5.4 and Lemma 5.5 are presented in Appendix D.
1.6
5.3. The Final Regret Bound
W (RR, P) W
(R, (R, 22c.
Theorem 5.6. Fix 5 > O. For any episodic MDP with trajectory feedback, with probability 1 - 8, the regret in K episodes of Algorithm is upper bounded by
Recall that K2 2K- for 1 S e < L - and Kg S 2k #t_ The regret in the (E + 1)-th batch is bounded by
Regret (areet(())))))))) S Ö(VSAH>K + +
O(Ke116)) = OOVSÓHOSSSSSSSA +
ASH A5T
+
5 S
(13)
Below sketch the proof of Theorem 5.6.
for 1 S 1-1, Moreover, the regret incurred in the first batch is bounded by O(K O((K()))
Regret in the first stage. Recall the definition of II, in Line 3 Algorithm 1. By Lemma 5.2 and the fact that x² E Hett with probability 1 8, we have that
Putting all together. By (12) and (13), obtain that the total regret is bounded by
n" El1;
Regret K) 0 [Ko00+ K, + Σ
K KKH
P is a (3, oo)) -approximmaioon of P with respect to Th, hence it is also (3, appppoxximtaoonn of P with re- spect to II. for any 8 2 1;
t=2 =((SAHHK + VS
S Kt
S 13
WT (R,R P) 2 W W*(R, P) - 2eg for π E II
By the third property, the regret in the first stage is at most
The proof is finished by replacing 5 with 165 A6S+AB(L+1))
(K250 + H1)
6. Conclusion
= [VSAHHK + S AAH A K. SHAAH
In this work, we design an algorithm achieve asymptot- ically nearly optimal regret bound of (OOOSAASA K) for RL with trajectory feedback. However, the proposed algorithm is based on elimination, resulting in exponential running time. An intriguing future direction to investigate whether the optimal regret bound is achievable using a computation- ally efficient algorithm. Additionally, another interesting future direction involves minimizing the lower-order terms in the regret bound.
(12)
where K, 1000/ SAHK and K₂ Ko 3K1 are defined in Algorithm 2 and Appendix A.
Regret in the second stage. Recall that the second stage comprises consecutive batches. We bound the regret in each batch separately.
Fix S L < L (log log (K)) and assume T² E IIg. Re- [68AAK] Set J = do. 1 = 26,, and 6
call that /. log²
Acknowledgments
20 72, SAHS, +9, AH AHH +SAAl20o!)) K,
K.
K2
Y. Chen is supported in part by the Sloan Research Fel- lowship, the Google Research Scholar Award, the AFOSR
We can then verify the conditions Lemma 5.5:
8

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
grant FA9550-22-1-0198, the ONR grant N00014-22-1- 2354, and the NSF grants CCF-2221009 and CCF-1907661. JDL acknowledges support of Open Philanthropy, NSF IIS- 2107304, NSF CCF-2212262, ONR Young Investigator Award, NSF CAREER Award 21 2144994, and NSF CCF- 2019844. SSD acknowledges the support of NSF IIS- 2010770, NSF DMS-2134106, NSF CCF-2212261, NSF IIS-214393,, NSF CCF-2019844, NSF IIS IIS-222988I, and the Sloan Research Fellowship.
reinforcement learning with general function approxima- tion. In International Conference on Machine Learning, pp. 3773-3793, PMLR, 2022.
Cohen, A., Kaplan, H., Koren, T., and Mansour, Y. Online markov decision processes with aggregate bandit feed- back. In Conference on Learning Theory, pp. 1301-1329. PMLR, 2021.
Dani, V., Hayes, T. P., and Kakade, S. M. Stochastic linear optimization under bandit feedback. In COLT, volume 2, pp. 3. 2008
Impact Statement
This paper discusses research aimed at advancing the field of theoretical reinforcement learning. While our work may have various potential societal impacts, we believe none of them require specific emphasis in this context.
Domingues, O. D., Ménard, P., Kaufmann, E., and Valko, M. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pp. 578-598, 2021.
References
Efroni, Y., Merlis, N., and Mannor, S. Reinforcement learn- ing with trajectory feedback. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 7288- 7295, 2021.
Abbasi-Yadkorii Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Falahatgar, M., Hao, Y., Orlitsky, A., Pichapati, V., and Ravindrakumar, V. Maxing and ranking with few as- sumptions. Advances in Neural Information Processing Systems, 30, 2017.
Agarwal, A., Kakade, S., and Yang, L. F. Model-based rein- forcement learning with generative model minimax optimal. In Conference Learning Theory, pp. 67-83, 2020.
Filippi, S., Cappe. O., Garivier, A., and Szepesvári, C. Para- metrie bandits: The generalized linear case. In Advances in Neural Information Processing Systems, pp. 586-594, 2010.
Azar, M. G., Osband, I., and Munos, R. Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, pp- 263 272, 2017.
Jaksch, T., Ortner, R., and Auer, P. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 1(AAp)) 2010.
Bengs, V., Busa-Fekete R., El Mesaoudi-Paul A., and Hüllermeier, E. Preference- online learning with dueling bandits: A survey. Journal of Machine Learning Research, 1207):1-10,, 2021.
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. Is
Q-learning provably efficient? In Advances in Neural Information Processing Systems, pp. 4863 4873, 2018.
Bubeck, S., Cesa- Bianch,,, N., and Kakade, S. M. Towards minimax policies for online linear optimization with ban- dit feedback. In Conference Learning Theory, pp. 41- 1. JMLR Workshop and Conference Proceedings, 2012.
Jin, C., Yang. Z., Wang, Z., and Jordan, M. I. Provably efficient reinforcement learning with linear function ap- proximation. In Conference on Learning Theory, pp. 2137-2143, 2020.
Cassel, A., Luo, H., Rosenberg, A., and Sotnikov, D. Near- optimal regret in linear mdps with aggregate bandit feed- back. In Proceedings of the 41st International Conference on Machine Learning, pp. 5757-5791, 2024.
Kakade, S. M. On the sample complexity of reinforcement learning. PhD thesis, University of London London, England, 2003.
Chatterji, N., Pacchiano, A., Bartlett, P., and Jordan, M. On the theory of reinforcement learning with once-per- episode feedback. Advances in Neural Information Pro- cessing Systems, 34:3401-3411 2021.
Kiefer, J. and Wolfowitz, J. The equivalence of two ex- tremum problems. Canadian Journal of Mathematics, 12: 363-366, 1960.
Chen, X., Zhong, H., Yang, Z., Wang, Z., and Wang, L. Human-in-thee in-the-loop: Provably efficient preference-basee
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
Li, G., Shi, L.., Chen, Y., Gu, Y., and Chi, Y. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34:17762-1777 17776, 2021.
Zanette, A. and Brunskill, E. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312 2019.
Li, Y., Wang, Y., and Zhou, Y. Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory, pp. 2173-2174. PMLR, 2019.
Zhang, Z. and Ji, X. Regret minimization for reinforce- ment learning by evaluating the optimal bias function. In Advances in Neural Information Processing Systems, pp. 2923-2832, 2019.
Maurer, A. and Pontil, M. Empirical Bemsttein bounds and sample variance penalization. In Conference on Learning Theory, 2009.
Zhang, Z., Zhou, Y., and Ji, X. Almost optimal model-free reinforcement learning via position. In Advances in Neural Information Processing Systems, 2020.
decom-
Ng. A. Y., Harada, D., and Russell, S. Policy invariance under reward transformations: Theory and application to reward shaping. In ICML,, volume 99, pp. 278-287, 1999.
Zhang, Z., Ji, X., and Zhou, Y. Almost optimal batch-regret tradeoff for batch linear contextual bandits. arXiv preprint 100.0007 2021.
Novoseller, E., Wei, Y., Sui, Y., Yue, Y. and Burdick, Dueling posterior sampling for preference-basee rein- forcement learning. In Conference on Uncertainty in Artificial Intelligence, pp. 1029-1038. PMLR, 2020.
Zhang. Z., Ji, X., and Du S. Horizon-free reinforcement learning in polynomial time: the power of stationary policies. In Conference on Learning Theory, pp. 3858- 3904, 2022a.
Saha, A., Pacchiano, A., and Lee, J. Ducling rl: Reinforce- ment learning with trajectory preferences. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 6263-6268 PMLR, 2023.
Zhang, Z., Jiang, Y., Zhou, Y., and Ji, X. Near-optimal regret bounds for multi- reinforcement learning. Advances in Neural Information Processing Systems, 35:24586- 24596, 2022b.
Wang, Y., Liu, Q., and Jin, C. rihf more difficult than standard rI? a theoretical perspective. Advances Neural Information Processing Systems, 36, 2023.
Zhang. Z., Chen, Y., Lee. J. D., and Du S. S. Settling the sample complexity of online reinforcement learning. In The Thirty Seventh Annual Conference on Learning Theory, pp. 5213-5219. PMLR, 2024.
Wirth, C., Akrour, R., Neumann, G., and Fürnkranz, J. A survey of preference-basee reinforcement learning meth- ods. Journal of Machine Learning Research, 18(136); 1-46, 2017.
Wu, R. and Sun, W. Making rl with preference- feed- back efficient via randomization. In The Twelfth Interna- tional Conference on Learning Representations, 2023.
Xu, Y., Joshi, A., Singh, A., and Dubrawski, A. Zeroth order non-convex optimization with dueling-choice bandits. In Conference on Uncertainty in Artificial Intelligence, pp. 899-908. PMLR, 2020a.
Xu, Y. Wang, R., Yang, L., Singh, A., and Dubrawski, A. Preference- based reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:18784-18894 2020b.
Yang, L. and Wang, M. Sample-optimal parametric Q- learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004, 2019.
Yue, Y., Broder, J., Kleinberg, R., and Joachims, T. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 15385)133881111 2012.
10

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
A. Parameter Settings
Set
Ko 100000S A K log
(SAHK)
and K
2k'
# for l Let == ming (Ko E Ke) z
K. Set co
90000 log 3( (AAK))
SAH
+
S
SAA
d0 SăAŽHáK log 2 (1 and A
K
K
20
72
SAH 9
EHt T
10052AH?
SAH
T
By this definition, we have L S 2 logg log(K). With slightly abuse of notation, we re-define Kr K - -(Ko -imi Le).
then holds that Ko + Et=1 K; K.
B. Technical Lemmas
Lemma B.1 (General Equivalence Theorem in (Kiefer & Wolfowitz, 1960)), For any bounded subset X C Rd, there exists distribution XXX) supported on X, such for any > O, it holds that
max
(el Eooxx 1) x x
(14)
xE
Furthermore, there exists mapping x², which maps a context X a distribution over such that
max
T (eI + By (i--))-10 ---------- S 2d.
(15)
2EX
In particular, when supp(X) has finite size, n (X) could be implemented within poly(Isupp(X)) time.
Lemma B.2 (Generalized KW Theorem). For any policy set 11 C. IIldet.
min max Σ (A))) SSHH, TET
(16)
where A(x): := Eter Pr,, PT
Proof of Lemma B.2. Let F(T) == log(det(A(T))) for ग E Al Because All is closed set and F(T) S d lllg(d) for any π E A with d = SAH, there exists some ग such that ग = arg max F(T). We assume that (AF))) * 0. Otherwise de)( is always O, which implies there is redundant dimension.
Because could be viewed as distribution over we use X(#, .) to denote the probability that distributes on . for II. It then holds that Eren A(7,T) T) and
A ( Σ ((TT))A(T). Nell
As a result, F(#) could be viewed as multi-variable function with respect to distribution {A(#, m)) For two different Ti, u2 E such that A(#, uι) > 0, A,, n2)) > 0, by the condition that arg max F(T).. have that
@F(a) OF(R)
(17)
0A( T)) OA(F,T2) T2)
which means that
Σ Pr.. P ( -b,
E Pr (A(T(((())) -t
For mi 22 such that A(T, mi) > 0 and \(T, x2) we have that
aF(=)
OF(
0A( (T T
a\(

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
which implies
Σ TET
Pra ' 2 Σ Pr Pr (A(T)) '
TET
Therefore, max+ell ΣTET Prz (A()) " is reached by any such that A(T, 1T) 0. Assume this value is That is,
m( Σ
TET
for all π E II. Taking sum over E II, we have that
I = Trace (race(((](M(m)) =d== SAH.
(18)
The proof is completed.
Lemma B.3 (Lemma in (Zhang et al., 2022b)), Lel d > 0 be an integer. Let X C (A4)m. Then there exists a distribution
D over X, such that
max z= (x: 1m
md,
EX
y1
dm where y = {m RynD [xr].
Lemma B.4 (Bennet's inequality). Let Z, Ziy..., Zn be i.idd random variables with values in [0, 1] and let 0. Define
V (Z E Then we have
12
24 (2(28)
In(2/0) T6
2
22
S 8.
71
Lemma B.5 (Theorem in (Maurer & Pontil, 2009) Let 7, 71. Zn (n 2 2) be i.d. random variables with values in
00, and let 8 > 0. Define Z Eiz Zi and Vn
Σm (Z, 2)2. Then have
2V, In(2/0)
7ln(2/0) 3(n 1)
TP
E. [
7
56.
n
Lemma B.6 (Lemma 10 in (Zhang et al., 2022a)), Let X1, X2... be a sequence of random variables taking value in [0, T]. For any k 2 1, let Fy be the a-algebra generated by (X1, Xz,..., Xx), and define Yv = E[[x, | Fx-1). Then for any > 0, we have
1 $
P
3
X
Yv llog
5
k=1
k=1
P
3n.
Yv
X loo
5..
8
k=1
Lemma B.7. Fix d > 0. Let A daxd be PSD matrix and x E RRd be a vector such that T A-1 l I
Then we have that
log(det(A T) log(det(A)) 2x AA-
Proof. Direct computation gives that
1
log(dct(A + xx T!> - log(dct(A)) log(dct(( + -TA-I = log(1 + +
2 x -
2
12

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
Lemma B.8 (Proposition I in (Zhang et al., 2021)). Consider a sequence of independent PSD (positive semi-defnite)
matrices X1, X2....; Xn Raxd such that X2 W for fixed PSD matrix W and all 1 S k S For every ô > 0 and E (0, 1), it holds that
Pr
X
Σ
[[Xa] + +
21-6;
(19)
k=1
n
Pr
Xx
E[XM] 3log(//0)
(20)
Lemma B.9, Assume p is an (n, papproxiipoiiiiioonnnn of with respec to IL. It then holds that
Ex Ex (shh an) = (s. & E, [[[(s), and = (s, a)]l s nE (lEnp/[[((s, an) = (8, a). +
(21)
n
for any E II and (s, a,
Proof. By (9) and (10), for any trajectory т, we have that PrylT & Pry [r']. It then holds that
1
E. n an) a)]l Er [[[(,,, an) = (s, a.]]
n
On the other hand,
B (T an) = (s, a)]]
< En y' [[)
ax) an) (s, a)] n [[w av, (h K1 A s A]]
max PIx [CC)
wellda
S n R [[(k, an) (s, a)] + x.
(22)
Lemma B.10. Assume p is an (n, aapprrxiiiinni of p/. It then holds that
max =ellaa
Pro.p/ [Tbac] $ x,
where Toad {T: Prpple [r] 2 nPrp[T]}.
Proof. Let = {sh, H hmmm | be an element in Toad By definition, there exists h such that (sh, an, h, sh+1) E K.C Asa result, maxxell.... Pra,y/ [Tha]] S max p' [X S x.
C. The Raw-Exploration Algorithm and Analysis
Lemma C.1. By running Raw-Exploration ion with input (II, K,,,KO 8), with probability 1 8, the output p is an (3, 110005 AH (SHH58H/ approximation of with respect to
K
Proof. Let A be the value 'D after the h-th iteration. Let ph Confideece-Roiionn"" and P. be the final value P. Let N (8, a, s') be the count of (s, a, M,,')) 8.) in Dr, and (s, == min E. N (s, 8'), 1}. Let p NA (s,ass) be the empirical transition probability computed by D,. (s,a)
By Lemma B.4, with probability 1 1 66/2.
(N a's')e + (s,
W - Parahor 5
(23)
NN (s,
13

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
Algorithm 6 Raw naw-Explorating ion K)
1: Input: policy set 11, length K
2: Initialize: K1 -- SAH + log 25/
D
3: for h 1,,.... H do
4: P
5: for (s, E x A do
6: {Taan .pm pp.a.h] t arg ma Ex. [1( an) = (s, a)];;
7: end for
8: for (s, h) ESX Ax do
9: Execute ghahh for K₁ episodes, and collect the samples as D ki
10: end for
11: D (Us,a, D.,,h))
12: end for
13: P + Conffiiieenn --Cofiidence-Reioolll
14: < arbitrary element P
15: return: pi
16: Function: Confidence-Region
17: Na(s, a, 8') &- count of (8, a, h 8') in D, for all (s)
18:
a, s'), Pa,ahh, t Na(a.e.a h(s,,,
a) t max (E, a,,
for all (s,a);
Mu(s.a)
20: W+ + (s,,,,,,8)) Na(s,u,8') 2 2):
21: Peaah + p A p Psahhol S [N..s. 5t
Nateoj .s ESJ. s(h,
(f
Peoch {clip(p, W): : p P s. ((s,ahh); Return: Ss.a,PPs,..ttt
23:
Function: clip(p, W)
25:
P Prand t Ps.ahh.s' s,a,s, W: 26: Peahs t 0, a,
W:
27: Vaa,h, + Eoslaahhss' Psahh 8(h, [M] x A:
28:
Pla,h t 1,, a(h,a) [H] x A:
29:
Return: p.
holds for all (8, a, (8, a, s') in Da.s.a and N, a) max E., Nu(s, a, s'), 13. Define
h², s') and E [H] We proceeds the analysis conditioned on (23). Let Na a, s') denote the count of
K, = [1, (s),,,s)) Nu(o,a, 200//21)
where log AH²
By (23), for any (s, 8') E Kr, and any h/ h, we have that
(V WOOFEe + 40/f2
ph - Paaaio S Diianhos
which implies that
pl Pa..
.H P....h.s
(24)
Moreover, by definition of ph, using similar arguments, we have
1 3H
|ps,, Paathil
P b.
(25)
14

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
for any a,, 8') Kr and p ph
We set K UnKr and verify the three conditions in Definition 5.1. The first condition (9) holds by (25), and the second condition (10) holds because Ps,,,,.s' 0 for any E P and (s, (s,, E Kg. As for the third condition (11), we analyze as below.
Fix [M]. By (24) and definition of {x (x , p%...h1), we have that
p. 1,P [[((s++1,ah+)) = [s,
H
IV
[[((8)1, = (8, a)]l
3H
IV
E 2... parddi [[(s+11, ax+1) (s, a)]l
IV 59 3
max E ap [1(())1) = (s, as,a
well
max E,, [Tss (w,, Kh, v1 S h' s h] I[(sh+1, 0441) (s,a)]].
(26)
9 wEll
Here (26) holds because for any trajectory == (sw, ak 1i== such that (sw, ans, 8u441) KN, Pr Pr Prx, for any Ph and any E II. Consequently,
11 [[[(s++1, ah+1, Sh42) (s, a, s'Ill
max E., [I[((s, SW+1) E Kn, v1 < h' S h] ([(5++1,4441,00 = (s, a, s')l' sell
(27)
On the other side, by Lemma B.6, with probability
AH it holds that
Nn+1(s,a,)
1 Kg KyEnsentt [1[( an-1, 1n-1, = (8, a,a.ss) s']ll log
2.2 AH²
3
5
1
A
AH2
K1 max E.,P [[(s,, aw, sw41) Kh. V1 < h < h]
[[88411,444)) = (8, -log
27
xell
8
which implies that
2427
max E. [[ss,, aN, Sw42)) Kn. v1 S h < h] (((hh+1,4442) (s)a 5
(28)
K
for (8, a, 8') E KC h+1
Taking sum over all (s,a,5) E h+1- we learn that
54275 AH?,
max
E, [[[(s, a, s') e Ko Iss,, aw, SM+1) E Kh, V1 s h < h]] <
(29)
fell
K
Taking sum over [H], we learn that
max Pr (
max E, (lsss,,ss)) Konl I[s, sw41) Kn, V1 s h' <h]]
1=1
54
K1
Therefore (11) holds with
5427 AH3 Ki
The proof is completed by noting Ki
K
SAH
15

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
D. Missing Algorithms and Proofs
D.I. Proof Lemma 5.2
Proof. By Lemma C.I, with probability 1 3(1+1)' Po is an (3, 11000s AH 1og(1SA -approximation of P with respect to II By noting that
K2
SAHK
K2 960005 A H K log
and
110005 AH log (L
du
K₂
we conclude that P2 an (3, (3,o0)aaaproximmaiin of P with respect to 11, and thus is an (3, approxxaoooiiiiooonn of P with respect 11g for any L 1.
Let bj == 110005 A log( 4
By Lemma C.I. with probability - P1 an (3,b)) aaproxiappoiinnai P with respect
K1
to det- By Lemma 5.3, with probability 1 - 4. we learn that
W (R, P) WT (R,
max *Ellass
SAH log K) log
H (ogSSH)o0
bi + +25
K,
< 1000
(~8
[SAIK)
SAHH
+ 44AAH%..
(30)
8
K
By Lemma 5.4 with parameters as:
II Iett
110005 AH* log
4SAH
b1
K1
H;
SAHK
SAH2 K!
S"AH6
= 1000 log?
+
8
K
28a AH² log
328AH
360S AH log
(329AH
44000S AH4 log
3282A112
301
Ki
K1
Ki
SAHK
SAH2
S$
SHAHo
e = 6
90000 log
8
Kt
Kt
2(b++2)
(31)
we have that: with probability The proof is finished.
4. it holds that (1) x² E (2) Wd (R, P) 2 W*(R, P) 2c for any x E TT.
D.2. Proof of Lemma 5.3
Proof. Let d SAH. Fix II. By definition, we have that
P <
Σ
Pr.. Pl..p1].10000 10T
R)).
TET
16

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
By Lemma D.2, with probability - 18//2, it holds that R E R, which implies that
P) W
10, (R R) Σ Pr
p(T] Prx,p[T]
TET
x Σ PIx, -ains/))mmi88
min(8y H² log(4/8) --1 H}
TET
$ H (og(AAA))ooo/////
Σ
pr min { 88 N-A-11TT
(32)
TET
By Lemma D.3, with probability 1 6/22, > 3.. Consequently, have that
Pr p(T) min { 5y of ύ- 1
WT, W (R. P)
& H (ogg(SS))))og(////)
Σ
FET
< (og(SSH))ogg4//))
x +
Pr [r] min /VO7T A 0,77-10T11
(33)
TET
H (og))))
+ 15
Pr. Pro /rimm/nnm
min { {
(34)
TET
SAH log K) log((d/)))) (2d/6)
S H VlVloo( log4/)) x + 325
(35)
K
Here (33) holds by Lemma 1. (34) is by Cauchy's inequality, and (35) is by Lemma D.1.
The proof is finished.
Lemma D.1. Let Å be the final value of A in Algorithm then holds that
Pr Pr (iipl1) "0,A-1,,,11 1,,135 432SAH log( K)) log(2d/0)
max REN
(36)
K
TET
Proof. Let K1
&
Let A be the value of A before the t-th iteration. For any policy π E II, we have that
R
Σ pr min( - 6r, 1 TET
min (At)-11 2rr 1}
K1
t=l
TET
R
p minn 10, 1}
K
1m
TET
1
(et((A
4 llg
(37)
K
ASAH
4325 AH log K) log(2d/8)
K
Here (37) derived as following. Let 2t,5 or
Then we have that A++1 A +
V /max( (o) (A1)-16, 1.
ErEr Pr Prrt,priee 2T Because 21, TT A', it holds that Σ1ET Pr & A. Let x be order
all possible trajectories and A(T) = A Erier Pr ( (1))) x 21º
17

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
As result, have that
del(A
log
det(A*)
(log(det(A(T) + P +1 - log(dot(A(()))) (A()))
TET
Pr a > (A(T),(((TT) 21,5
(38)
TET
2
1
Σ TET
Pr .p (A)) 2,,7
(39)
Here (38) is by Lemma B.7.
Lemma D.2. With probability 6/2, R E R.
Proof. Let X' = 18)log())))) It easy R E [0, 1JSH.. It suffices verify that
R o. R S 8/ 112 log( (og////00
VT.
Let = ((5h oi) Let == Σm= (s af.). Noting that y -E T' (sh, af)) where each (s af)) are
drawn according to (s d) independently, we have that Elexp(2(*)] & exp(H2? /22 for any 2 O. For fixed т, we note that
00 R o R.
STA-1
Σ
N
<
Φ A
+ -'H
A
+ H NONAAA1
(40)
K
2 0 A
(41)
Here (40) holds by the fact that A XI PSD and (41) is by the fact that 18A (o)lo(2d/6))F S Note that {( does not change the distribution of (Φr, YT= Therefore, it holds that
K
22
Pr
Σ
S
2 x V OT -
S 2eep
(42)
2H
With union bound of all possible choices of 7, we learn that, with probability 1 1-6,
6, for any it holds that
l - o_ R < 8y H1 (S log(/))) 1
The proof is completed.
Lemma D.3. With probability - 8/2, holds that
À >> 3Ā.
18

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
Proof. Let A o A be the value of A before the t-th round in line 4, Let 2 0r max
It is then easy to
verify that A t zezg By Lemma B.10, we have Prp[T] S 3Pry [r] for any т. By noting that
R1
A
Ext
Σ
Prat p0.07
max (0= (A9) 11
LTET
Ex y
Σ
Prat Prat,pore p0r0,
1 max faxx(07 10 A 11-11rr 11
1=1
LEe
K Br
Σ Pr
max o A -1 -l
TET
we have
K 18 log((2//)) + EnTt,P
k
1 max max -o0,, 13
* 18log(2d/5)AI + BF.
> (allog(d//)A.)
(43)
By Lemma B.8, with probability 1- -8/2.
k
24
7
E
Σ
212
3log(2d/5){ > 3log(2d/6)) 18Alog(2d/8)1
which means that
À x 18d1og(2d/0) + Σ 26 & 34.
The proof is completed.
D.3. Proof of Lemma 5.5
Let R. be the reward function in line Algorithm 3. By Lemma 5.3, with probability 1-8/% 88/2,
SAH log (K
log( 48AH
WT WT ( <b, == H (oH) + 325
max
HEll
K
As result, for any II,
- (R PR)))
max well
(R P) -DT(R, 2 25+22 261.
(44)
SAHR2HH+Sy) log( 188A8
3605 A/ log 193AH
Let IT, 2b, = by Let 30/
4SAH
By Lemma 5.4 and the assumption that > 2(b + =) = =2(b b1), it then holds that n3 E IInxxt and
W WR,RR P) WR,RFF P) 2k
for any π E Tnxxt
19

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
D.4. Proof of Lemma 5.4
Additional notations. We use (s)) (s))) to denote the (optimal) value function under the policy и, transition P and reward With slight abuse of notation, define (s, a. h) = E [I((sh an) (s, a)]] For two vector 2, y with the same dimension, write the inner product x y zy for simplicity, Let A be probability distribution over [S] and v R we define the variance function as (p,, v) pm² (po)². Define c(s, h)) E [T[(s,, os) = (s, a)] for all (8, a, h).
Because p is an (3, approximation of with respect to 11, by Lemma B.9 we have that
a(s a, h) S dp(ss,, h) s 3c(s, h) xx.
(45)
Let L == ((s, als,a,h) h): c(s, a, h) 2 max(x; (o By (45), ds a, h) I 4x for (s, (s,a,h) h) $ L. By noting that
Pen.an.h is independent of +1 using Bernstein' 's inequality, with probability 1 1-88 6/8,
V(Ps, 2/41) (HHSAA))
H Hlgg(8SAh/0)
(Ds,a.h Paaah)utt1 $2
2
V(s,ah));
(46)
(s(s,a)
Nn(s,))
Paans log(8SAH/0)
H log(8AA1/0)
Da.a Paannol $ 2
V(s,a,h,s').
(47)
(s(5,a)
(s,
We continue the analysis conditioned on (46) and (47). Fix E II. Using policy difference lemma, and noting that ap(s,a, < 4x for (8, a.ahh) & L, we have that
WRR, WT W" (R. W (R, (R.
Ex.P
Σ (Pen.anhh P heh
36 log
logg1888.. (8S (8SAH/8)
Σ (x.,
drpls, a ()
4SAH²
x
(48)
T
Let F 4SAH2 (a+
36 (8g
By definition of &,, further have that,
K
- -
(49)
Σ
dp(s, a, (D PaauDatt +
Σ (s.R,A)EC
dz(ss a, a),oaa Paan)(th+ oh+1) +
(s.a,)EE
V(Ps.n, 2 log (n(3,a)
SSAH
H Hlog 88AH ) (x(
Σ
ap(s,a,h)
21
(saah)ec
SV 1h+1 - "/41) log
8SAH
SH log (SSAH Na(s,a)
Σ
ap(s,a,h)
2/
+ F
Nn(s,a)
8SAH
dp(s,a,h) Nn(s,a)
< 2 log
Σ
Σ
on u. vit + SV(P sh 1/+11 2y -
(LO,))EL
(8AH
dp(s,a,hi)
+ 2SH log
Σ
+F. (50)
8
N1(s,
(s.R,AjEc
We then bound the terms (50) separately.
20

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
The doubling count term.
By definition of L, have that
dp(s,a,h) an(s,a)
a, N1(5,a)
Σ
$4 E
(51)
(s,a,))EE
s,a.h
By Lemma B.6, we further have that, with probability 1 holds that
(n) 2 Re(s,a, h) 188(88AH/0).
(52)
any (s, a, h). Conditioned on this event, we have that
dp(s,a,h)
108
Σ
(5,0,,
5
1085 AH
(53)
(x(
K
as
K
saa
In the last inequality, we use the fact that
max Σ (s,
SAH.
(54)
ETT 8,4.h
a(s,a,h)
which is direct result following Lemma B.3.
The variance terms.
Direct computation gives that
ET,P
E
V(P sn th,
= Er.p
(1144186441)) (P (n
A=1
< Bz,p
((n) to
H
< 22HE..
(v)(s)) Pan.an.nuhhi)
Hf (U)(5)) v(+z((841))
2HHB,,
1=1
< 2/12
(55)
21

---

Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback
and
H
E
V(Panaan hn vh+1) + (V
hs 1/41
vitz))
E
((07+1(8h42) - 1/+2 (P (Ponoon.h(hhtt o8(+)))8)
< F.
Σ
((o8((s)) - (xx)))) (P v
< НH
(s)) hor - (1)) an 22t
(vN(6a) Panannhhhhh Ru (8n,
-2HE,,r P
H
22H
Σ (v%) - un(s Pontann
(56)
2H (u, P) -
< 2Hy.
(57)
Here (56) holds by the fact that (5%) 2 un (sh, an) + P
Putting together.
By (50), (53) (55) and (57), we have that
SH + Sy) log (8SAH)
360Sa AH3 log (8SAH)
[W* (u, P)1 S 3
+ 4SAH² x =b.
(58)
K
K
Now we verify that x² 1lextt It suffices to show that
W (u,
max W (u,
(59)
x' x'Ell
By the assumptions and (58), we have that
TT (u, 2 WT P) - 62 T (R, -
V (v, (w, P) +b WT (R, P) + +bb W (R, () +b
Noting that 2 2(b 2), we conclude that nt E Inxtt- On the other hand, for any π E II we have that
WT P) 2 (w, (b 2) W= (u.i) 2(b 2) W (R, P) 3(b 2) W (R, P) 2c.
The proof is finished.
22


Reviews:
[{"review_id": "b2JpQoO9Yp", "reviewer": "Reviewer_egr3", "summary": "This work studies Reinforcement Learning with only Trajectory Feedback, where the agent does not observe the reward for each individual step separately. Under this setting, the author proposes a novel algorithm based on the arm-elimination method over all possible deterministic policies and achieves a near-optimal regret bound, which matches the lower bound for the setting with single-step rewards up to logarithmic factors.", "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": "We are grateful for the reviewer's detailed assessment and helpful suggestions. Below we present our response.\n\n **Regarding your concerns about correctness:**\n1. In the first $K_0=O(\\sqrt{K})$ episodes (other factors ignored), the main target is to identify the infrequent state-action-state triples with probability $O(\\sigma_0)=O(K^{-1/2})$. For the left triples, we want to  compute an  $(3,\\sigma_0)$-approximate estimation for the transition probability $P_{s,a,h}$. Note that this approximate transition matrix is only for designing the exploration policy, not for computing the near-optimal policy. Hence, computing such an approximate transition matrix requires only $O(\\sqrt{K})$ episodes.\n\n2. We set $\\epsilon_0 = O(K^{-1/4})$ ignoring other factors (please refer to Appendix.A). You are correct that it requires $1/\\epsilon_0^2$ episodes to learn an $\\epsilon$-optimal policy.    \nIndeed, we compute this $\\epsilon_0$ optimal policy to improve the efficiency of exploration in the following episodes.\nIn the main algorithm, we use $K_0=O(\\sqrt{K})$ episodes to identify the triples with probability $O(K^{-1/2})$. If we apply direct exploration, the regret in this stage might be $K_0H$, which violates the minimax bound $O(\\sqrt{SAH^3K})$ due to the dependencies on $S,A$ and $H$. Instead, we first compute the set of $\\epsilon_0$ optimal policies, and then conduct exploration within this policy set. In this way, the regret due to exploration is bounded by $O(K_1 H + K_0 \\epsilon) = O(\\sqrt{SAH^3K})$.\n\n**Regarding the computational inefficiency:** \n\nWe admit that the current algorithm is computationally inefficient, and indeed, devising algorithm with minimax optimal regret bound and polynomial running time for RL with trajectory feedback is an  intriguing open problem. However, we notice that obtaining statistically (nearly) optimal algorithms is usually the first step for completely settling problems in machine learning theory, and we believe our techniques would be useful for later developments in the theory of RL with trajectory feedback. \n\n**Regarding  the large dependency on $S,A,H$:**\n\nIndeed our current regret bound has large burn-in terms, and we would leave improving those terms as a future direction. On the other hand, we would like stress that even for RL in the standard setting, minimax optimal regret bounds have not been obtained until recent few years, and the burn-in terms were not fully optimized until very recently. Therefore, as the first work that achieves minimax optimal regret bound for RL with trajectory, we believe it is reasonable to have large burn-in terms in our bound. Moreover, we believe our new techniques are crucial for fully understanding the regret bound of RL with trajectory feedback. \n\n**Regarding other comments or suggestions:**\n\nWe are sorry for the typos. The $T$ notation in Section 5 denotes number of episodes, not number of steps. We will use $\\check{K}$ to replace $T$ throughout Section 5 and the corresponding analysis in the next revision. We will also separate $K$ from other factors. The final regret bound would be $\\tilde{O}(\\sqrt{SAH^3K}+S^{24}A^4 H^{32})$.", "claims_and_evidence": "The author provides a clear claim of the result in the theorems and includes a proof sketch to outline the key steps of the theoretical analysis.", "methods_and_evaluation_criteria": "The main contribution of this work focuses on the theoretical analysis of regret and does not have experiment.", "theoretical_claims": "The author provides a clear proof sketch for the case where the transition probability is already known. In this setting, the author utilizes the observation that the number of trajectories is significantly smaller than the number of deterministic policies and represents the reward of each policy as a linear combination of the rewards for each trajectory. By leveraging this method, the author reduces the problem to a linear bandit problem, achieving better performance with a lower-dimensional representation.\n\nHowever, the correctness of the analysis when the transition probability is unknown is not entirely clear, and I have several concerns:\n\n1. As the author mentions in the regret guarantee, the upper bound matches the lower bound for a more powerful learner with single-step rewards, suggesting that the main challenge in learning an MDP comes from estimating the transition dynamics. Given this, it seems unreasonable that the algorithm in Ref-Model only dedicates a small fraction of rounds to estimating the transition matrix and then primarily focuses on reward estimation using the estimated transition model for the majority of rounds. More explanation is needed to justify why the key challenge can be effectively addressed in the first $\\sqrt{K}$ rounds.\n\n2. In Lemma 5.2, the Ref-Model is claimed to achieve an approximate transition probability function with a small error $\\epsilon_0$. According to the regret analysis in this first stage, $\\epsilon_0$ is approximately $1/\\sqrt{K}$. However, in general cases, it typically requires $O(1/\\epsilon^2)$ rounds to obtain an $\\epsilon$-optimal estimator. Thus, it seems unreasonable that the algorithm can achieve a $1/\\sqrt{K}$-optimal approximation with only $\\sqrt{K}$ rounds. Further clarification is needed on how this estimation is justified.", "experimental_designs_or_analyses": "The main contribution of this work focuses on the theoretical analysis of regret and does not have experiment.", "relation_to_broader_scientific_literature": "This work mainly focuses on reinforcement learning with trajectory feedback; however, the proposed algorithm is highly computationally inefficient, making it primarily relevant for the theoretical analysis of reinforcement learning rather than practical applications.", "essential_references_not_discussed": "This paper provides a comprehensive discussion of related work in linear bandit and trajectory-based reinforcement learning method.", "other_strengths_and_weaknesses": "1. The proposed algorithm is highly computationally inefficient, making it primarily relevant for the theoretical analysis of reinforcement learning rather than practical applications.\n\n2. For the non-dominant term, the dependency on $S, A, H$ is extremely large, making the regret guarantee non-trivial and only meaningful for an excessively large number of rounds $K$.", "other_comments_or_suggestions": "1. The notation of $K$ and $T$ is consing. As the author mention in the introduction, there may exists a gap of the episode length $H$ between the number of episode and tnumber of stage $H$. However, the author use the both notation in algorithm, e.g., Algorithm 1 take a oracle to  Traj-Learning with parameter $K$ and when introduce the  Traj-Learning algoritmh, with a notation of $T$. better to union.\n\n2. For the non-dominant term in Theorem 5, there is still a dependency on the number of $K$. It would be better to explicitly separate the effect of $K$ in the non-dominant term to provide a clearer understanding of its impact on the regret bound.", "questions_for_authors": "1. As the author mentions in the regret guarantee, the upper bound matches the lower bound for a more powerful learner with single-step rewards, suggesting that the main challenge in learning an MDP comes from estimating the transition dynamics. Given this, it seems unreasonable that the algorithm in Ref-Model only dedicates a small fraction of rounds to estimating the transition matrix and then primarily focuses on reward estimation using the estimated transition model for the majority of rounds. More explanation is needed to justify why the key challenge can be effectively addressed in the first $\\sqrt{K}$ rounds.\n\n2. In Lemma 5.2, the Ref-Model is claimed to achieve an approximate transition probability function with a small error $\\epsilon_0$. According to the regret analysis in this first stage, $\\epsilon_0$ is approximately $1/\\sqrt{K}$. However, in general cases, it typically requires $O(1/\\epsilon^2)$ rounds to obtain an $\\epsilon$-optimal estimator. Thus, it seems unreasonable that the algorithm can achieve a $1/\\sqrt{K}$-optimal approximation with only $\\sqrt{K}$ rounds. Further clarification is needed on how this estimation is justified.", "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": "JIaSrSID8Y", "reviewer": "Reviewer_gvw8", "summary": "This work considers the problem of online learning in a tabular finite horizon MDP with stochastic rewards and aggregate bandit feedback, where agent observes only the sum of rewards she collected after each episode.\n\nAn algorithm based on policy elimination is proposed, which builds on the linear bandits perspective to the problem. This approach, while not computationally efficient, achieves nearly minimax optimal regret in all problem parameters (assuming the number of episodes $K$ is sufficiently large).\n\nOne of the main observations used to design the algorithm, is that the number of possible trajectories in the MDP ($(SA)^H$) is much smaller than the number of \"arms\", i.e., deterministic policies ($A^{SH}$). Thus, building on confidence regions based on trajectories rather than policies, leads to dependence on $\\sqrt S$ rather than $S$ that would be the result of a vanilla linear bandits algorithm, even in the known dynamics case.\n\n## update after rebuttal\nI chose to increase my rating to accept. After further consideration, and taking into account that none of my concerns were major, I think there is more than enough in this work to merit acceptance.", "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": "We sincerely appreciate the reviewer's thorough evaluation and constructive feedback. Below we present our response.\n\n**Regarding the computational issue:**\n\nWe admit that the current algorithm is computationally inefficient, and indeed, devising algorithm with minimax optimal regret bound and polynomial running time for RL with trajectory feedback is an intriguing open problem. However, we notice that obtaining statistically (nearly) optimal algorithms is usually the first step for completely settling problems in machine learning theory, and we believe our techniques would be useful for later developments in the theory of RL with trajectory feedback. \n\n**Regarding the burn-in terms:**\n\nIndeed our current regret bound has large burn-in terms, and we would leave improving those terms as a future direction. On the other hand, we would like stress that even for RL in the standard setting, minimax optimal regret bounds have not been obtained until recent few years, and the burn-in terms were not fully optimized until very recently. Therefore, as the first work that achieves minimax optimal regret bound for RL with trajectory, we believe it is reasonable to have large burn-in terms in our bound. Moreover, we believe our new techniques are crucial for fully understanding the regret bound of RL with trajectory feedback. \n\n**Regarding other comments and suggestions:**\n\n**About $c(s,a,h)$:** We are sorry for this mistake. $c(s,a,h)$ is only used  in the analysis for Algorithm 5. We will move the definition of $c(s,a,h)$ to Appendix D.4 in the next revision.\n\n**About $\\delta$ in Algorithm 2:** We will use $\\delta$ as a common parameter across all algorithms and delete $\\delta$ from the input of Algorithm 6. \n\n**About parameters in Appendix.A:** Thanks for the suggestion. We will refine the lemma statements to improve clarity.\n\n**About the proof overview of Theorem 5.6:**  Thank you for pointing out the typo. It should be $\\tilde{y}=2\\epsilon_{\\ell}$.\n\n**About $\\tilde{P}$ in Lemma 5.2:** Thank you for pointing out the typo. We will replace $\\tilde{P}\\to \\hat{P}_2$ accordingly.\n\n**About Eq.(28):** Here we use the fact that $\\log(A)\\log(B)=O(\\log^2(AB))$ for $A,B\\geq 1$.  We have revised the inequality and reset the value of $\\epsilon_0$ as $\\epsilon_0=90000\\log^3(\\frac{SAHK}{\\delta})\\left( \\frac{SAH^2}{K^{\\frac{1}{4}}}+\\frac{S^4AH^6}{K^{\\frac{1}{2}}} \\right)$. There should be an extra $H$ factor in the right-hand side of Eq.(28) to make the inequality holds. The revised version of Eq.28 is as follows.\n$$\\max_{\\pi\\in \\Pi_{\\mathrm{det}}}| W^{\\pi}(\\hat{R},P) - W^{\\pi}(R,P)|\\leq H\\sqrt{\\log(SAH)\\log(16/\\delta)}\\left(b_1+ 325\\sqrt{\\frac{SAH\\log(K)\\log(8SAH/\\delta)}{\\bar{K}_1}} \\right)\\leq  1000\\log^2\\left(\\frac{SAHK}{\\delta}\\right)\\cdot \\left(\\frac{SAH^2}{K^{\\frac{1}{4}}} + 4SAH^2b_1 \\right).$$\n We remark that this $H$ factor is in the second order term so the final regret bound is still asymptotically optimal.\n\n**About $\\mathcal{R}$:** We are sorry for the abuse of notations. You are correct that $\\mathcal{R}$ is the confidence region defined in line 13 of Algorithm 4. The proof of Lemma D.2 is under the proof of Lemma 5.2, which studies the properties of Algorithm 4. We will make this clear in the next revision.We will also replace $\\mathcal{R}$ with $\\mathsf{R}$ when introducing the reward distribution. \n\n**About Eq.(30), Eq.(31) and Eq.(32):** Thanks for pointing out the typos. We will fix accordingly.\n\n**About the term \"reward hacking\":** We will remove the term \"reward hacking\" from this paragraph.\n\n**About $\\sup$:** We will replace $\\sup$ with $\\max$.\n\n**About $xy$ and $x^{\\top}y$:** We will fix the notation about $\\sup$ and $x^{\\top}y$. We only use $xy$ as a shorthand of $x^{\\top}y$ in Appendix D.4 to reduce the complexity of the notations.\n\n**About \"the regret stemming from learning $\\tilde{P}$ can be bounded by ...\":** We will mention  that *\"$\\tilde{P}$ serves as an efficient tool to help design the exploration policy\"* before this sentence.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I went over proofs of Lemmas 5.2 and 5.3, and the proof overview of Theorem 5.6. I didn't find any significant issues.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The problem we initially proposed by Efroni et al. (2021). Later, Cohen et al. (2021) study the adversarial setting, and Cassel et al. (2024) study the stochastic Linear MDP setting.\n\nAll the previous approaches provide $\\widetilde O(\\sqrt K)$ regret in the the tabular stochastic setting, but with suboptimal dependence on the rest of the problem parameters $S,A, H$. However, they are computationally efficient.\n\nThe approach proposed in this work gives optimal dependence on all parameters (assuming $K$ large enough), but is not computationally efficient.", "essential_references_not_discussed": "None that I know of.", "other_strengths_and_weaknesses": "**Strengths**\n\n* The approach yields a (near) minimax optimal regret bound for the problem.\n* The technical overview and presentation of the algorithm are well written and relatively clear.\n\n**Weaknesses**\n\n* The algorithm is not computationally efficient, and the burn-in period (requirement on $K$ for minimax optimality) is quite demanding.\n\nUltimately, establishing the optimal dependence on problem parameters is secondary in importance, even more so for a non-computationally efficient approach. Further, this is essentially the first paper that proposes a non-computationally efficient approach to the problem. That said, it is clear the problem is far from trivial and it seems this work offers some valuable insights. The algorithmic approach is pretty elegant and intuitive, at least at a high level.", "other_comments_or_suggestions": "Algorithms\n* Algorithm 5 line 3 computes $c(s,a,h)$ (the occupancy of $\\bar\\pi$ wrt $p$?) but it does not seem to be used anywhere.\n* Algorithm 2 does not pass a $\\delta$ (lines 3,6) to Raw-Exploration (algorithm 6)\n* I suggest you add a \"Conditioned on parameter settings in Section A,...\" to the relevant Lemma statements.\n- In the proof overview of Theorem 5.6, should $\\tilde y=2\\epsilon_0$ be $\\tilde y=2\\epsilon_\\ell$?\n    \nLemma 5.2\n- In the proof, $\\tilde P \\to \\hat P_2$ (or change the Lemma statement to be about $\\tilde P$)\n- Eq. 28 is not synced with Lemma 5.3 (e.g., $log^2(T/\\delta) \\nleq \\log (T) \\log(1/\\delta)$)\n- Also in Eq. 28, the last inequality seems to follow from a condition on $K$ that is not mentioned in the statement of the Lemma.\n\nLemma 5.3\n- “By Lemma D.2 … it holds that $R \\in \\mathcal R$” is this the $\\mathcal R$ defined in line 13 of Algorithm 4, when invoked with $(p, T, \\Pi)$ of the current Lemma? Better to be explicit about this to help the reader. Also, $\\mathcal R$ denotes your reward distribution, which is unrelated.\n- In Eq. 30, same comment as for Lemma 5.2, $\\log^2(Z/\\delta) \\nleq \\log (Z) \\log(1/\\delta)$ for general $Z$. \n- There seems to be a sum over $\\tau$ missing in Eqs. 31 and 32\n\nMisc\n* \"To circumvent issues mentioned above, practitioners often rely on heuristics (e.g., reward shaping (Ng et al., 1999) or reward hacking (Amodei et al., 2016)).\" - Amodei et al. propose methods to **avoid** reward hacking. Reward hacking refers to the scenario where the agent exploits an inaccurate reward signal.\n* \"The optimal Q-function and V-function are given by ...\" Why use $\\sup$ and not $\\max$ for $Q^*$?\n* \"we write the inner product $x^\\top y$ as $xy$ for simplicity\" - I would suggest to revise this decision, it generates place for confusion with scalar multiplication.\n* \"the regret stemming from learning $\\tilde P$ can be bounded by...\" It this point it is not clear what is the reference transition kernel so the sentence does not convey much information.", "questions_for_authors": "I don't have any important questions.", "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": "bK0t24IoJF", "reviewer": "Reviewer_J7DL", "summary": "This paper investigates reinforcement learning with trajectory feedback, where the agent receives only the cumulative reward for an entire trajectory rather than individual state-action rewards, while still observing all visited state-action pairs. The authors establish the first asymptotically nearly optimal regret bound of $O(\\sqrt{S A H^3 K}) $ for this setting, matching the asymptotically optimal regret bound in standard RL. To achieve this, they construct a tighter confidence region for rewards by leveraging the structure of the linear bandit instance associated with RL with trajectory 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": "We are grateful for the reviewer's detailed reviews and valuable suggestions. Below we present our response.\n\n**Regarding Lemma B.1:** In Lemma B.1,  $\\bar{\\pi}$ represents a mixed policy. That is, by following $\\bar{\\pi}$, the learner takes each deterministic policy $\\pi\\in \\Pi$ with a certain probability as $\\lambda(\\bar{\\pi},\\pi)$. As a result, $F(\\bar{\\pi})$ could be regarded as a multi-variable function with respect to the probability vector $[\\lambda(\\bar{\\pi},\\pi)]_{\\pi\\in \\Pi}$.  We will revise the proof accordingly in the next version. \n\n**Regarding clarification of KW theorem:** In the proof, we do not directly use KW theorem. Instead, we generalize the KW theorem to a distributed version in Lemma B.1. In the next revision, we are planning to present the original version of the KW theorem together with our generalized version to make the difference clear.\n\n**Regarding computational inefficiency:** We admit that the current algorithm is computationally inefficient, and indeed, devising algorithm with minimax optimal regret bound and polynomial running time for RL with trajectory feedback is an intriguing open problem. However, we notice that obtaining statistically (nearly) optimal algorithms is usually the first step for completely settling problems in machine learning theory, and we believe our techniques would be useful for later developments in the theory of RL with trajectory feedback. \n\n**Regarding large burn-in terms:** Indeed our current regret bound has large burn-in terms, and we would leave improving those terms as a future direction. On the other hand, we would like stress that even for RL in the standard setting, minimax optimal regret bounds have not been obtained until recent few years, and the burn-in terms were not fully optimized until very recently. Therefore, as the first work that achieves minimax optimal regret bound for RL with trajectory, we believe it is reasonable to have large burn-in terms in our bound. Moreover, we believe our new techniques are crucial for fully understanding the regret bound of RL with trajectory feedback. \n\n**Regarding other comments and suggestions:**\n\n**About lines 282-284:** We will rewrite this sentence as *\"Instead of approximating $P$ by $p$ under the $L_1$-norm, it is required the trajectory distribution under $P$  could be covered by that under $p$, up to a constant ratio.\"*\n\n**About line 208:** Thanks for pointing out the typo. We will fix accordingly.\n\n**Regarding the  elimination-based online batch learning:** In this work, the fundamental problem is still reinforcement learning. More precisely, even if assuming that the reward is known, we are required to learn the transition kernel. This step cannot be trivially implemented using a linear bandit algorithm. As a result, we choose to use a linear bandit algorithm to learn the reward function and  an RL algorithm to learn the transition kernel.  Another two reasons to apply the eliminated-based batch learning are that: (1) Designing an algorithm that can simultaneously learn both the reward function and transition kernel presents significant challenges. As a result, we have to learn the reward and transition kernel separately; (2) By batch learning, we can efficiently reduce the statistical dependencies between different batches, which makes the analysis less complicated.", "claims_and_evidence": "All theoretical claims are followed by proofs in the appendix or the main paper.", "methods_and_evaluation_criteria": "As a theoretical paper, the proposed algorithm seems well suited for the problem.", "theoretical_claims": "I've reviewed some of the proofs, and while most appear correct, I would appreciate further clarification on the proof of Lemma B.1. This lemma seems to play a key role in improving the dependence of the regret bound on $S $. However, the definition of $ \\lambda(\\bar{\\pi}, \\pi) $ is unclear. How do the authors define the probability that $ \\bar{\\pi} $ \"distributes\" over $ \\pi $? Additionally, the interpretation of the partial derivative of $ F $ with respect to this quantity is not well explained. These concepts may be standard in this type of analysis, but it would be helpful to reintroduce them rigorously, especially for readers in RL who may not be familiar this.", "experimental_designs_or_analyses": "not applicable.", "relation_to_broader_scientific_literature": "Efroni et al. (2021) established a regret bound of $ \\tilde{O}(\\sqrt{S^2 A^2 H^4 K}) $ for RL with trajectory feedback, which holds for all $ K > 0 $, not just asymptotically. The authors suggest that refining the analysis could improve this bound to $ \\tilde{O}(\\sqrt{S^2 A H^3 K}) $, but reducing the dependence on the number of states requires a fundamentally new approach. This paper presents the first algorithm that asymptotically achieves the lower bound of $\\tilde{O}(\\sqrt{S A H^3 K}) $ for RL with trajectory feedback, matching the optimal rate in standard RL, though the bound holds only in the asymptotic regime (for large $ K $, not all $ K > 0 $). Like Efroni et al. (2021), the algorithm leverages the connection between RL with trajectory feedback and linear bandits but introduces a novel confidence region around rewards. Additionally, it employs a policy elimination method to learn the transition kernel, similar to the approach of Zhang et al. (2022b).", "essential_references_not_discussed": "To the best of my knowledge, the related work is clearly presented.", "other_strengths_and_weaknesses": "**Strenghts**: \n- The paper is generally well-written. \n\n- The technique of building the confidence region around the reward estimation by considering trajectories, rather than defining it for each deterministic policy and applying a union bound, enables an improved dependence on the number of states in the regret bound and appears to be a novel approach. \n\n- This work is the first to achieve an asymptotically near-optimal regret bound for this problem.\n\n**Weaknesses**: \n\n- Some parts of the paper require further clarification, such as the proof of Lemma B.1 and the precise application of the classical Kiefer-Wolfowitz theorem in this setting (as claimed on page 5, line 224). \n\n- The proposed algorithm is not computationally efficient, whereas some existing approaches, such as UCBVI-TS from Efroni et al. (2021), are computationally efficient but yield worse regret bounds ($ O(H^7 S^4 A^3 K) $).\n\n- The regret bound established in this work holds asymptotically in $ K $ and does not apply for all $ K > 0 $, unlike the bound in Efroni et al. (2021).", "other_comments_or_suggestions": "- The phrase on page 6, lines 282-284, may be lacking some connectors, which makes the formulation unclear: ex.: \"to the L1 norm\"\n\n- Page 4 line 208: $Y_t$ should be $Y^t$?", "questions_for_authors": "Why the authors choose to use an elimination-based online batch learning process rather than using the new confidence region directly with a linear bandit algorithm? I may be overlooking a key step and would appreciate further clarification.", "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": "tl0IA04hV8", "reviewer": "Reviewer_zDaM", "summary": "This paper studies the setting of tabular MDP, with trajectory feedback, i.e., every round after executing a policy the learner obtains the entire trajectory with the total reward along the trajectory. The per-step reward is not given to the learner. This paper provided an algorithm for this setting and also proved that the algorithm achieves $\\tilde{O}(\\sqrt{SAH^3K})$ regret upper bound, which also matches the lower bound, asymptotically.", "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": "We are grateful for the reviewer's detailed comments and constructive suggestions. Below we present our response.\n\n**Regarding significance:**  We would like  to stress that even for RL in the standard setting, minimax optimal regret bounds have not been obtained until recent few years, and the burn-in terms were not fully optimized until very recently. Therefore, as the first work that achieves minimax optimal regret bound for RL with trajectory, we believe our work is non-trivial in terms of technique.\n\n**Regarding technical novelty:** While the algorithmic framework depends on previous work, the key technical observation is that the number of possible trajectories $O( (SA^H)$ is smaller to that of possible policies $O( A^{SH})$. This is why we can remove the extra $\\sqrt{S}$ factor compared to previous work Efroni et al., 21.\n\n**Regarding the large burn-in terms:**  Indeed our current regret bound has large burn-in terms, and we would leave improving those terms as a future direction.  The current term is $S^{24}A^4H^{32}$. The main reason of such a large burn-in term is due to learning the reference model. This term can be significantly reduced under the assumption of an effective reference model.\n\n**Regarding other comments:**\n\n**About the typos:**\nThanks for pointing out the typos. We will fix the typos accordingly in the next revision. In the second typo, we use $d_{P}^{\\pi}$ to denote the feature vector with respect to $\\pi$, which does not depend on the trajectory $\\tau$.\n\n**About the preference-based learning:** Preference-based RL (PbRL) is another RL paradigm to deal with the lack of reward signals. We will discuss the similarities and differences between the two settings in the next revision.\n\n**Regarding the questions:**\n\n**Abut the exact burn-in term:** Following the current analysis, the final regret bound is $\\tilde{O}(\\sqrt{SAH^3K}+S^{24}A^4H^{32})$.\n\n**About the extensions to other settings, e.g., linear MDP and MDP with function approximation:** At the moment, we are not aware of any possible extensions to linear MDP or MDP with function approximation. We believe these problem settings should enjoy some advantages of low-rank structure so that we can construct a feature space with lower dimensions. \nFor example, in linear MDP, we can take $ (\\phi_{s_1,a_1}, \\phi_{s_2,a_2},..., \\phi_{s_H,a_H})$  as a $dH$-dimensional unified feature to learn the reward kernel $ (\\theta_{1}, \\theta_2,..., \\theta_H)$. However, the exploration and policy design over this feature space is more complicated compared to the counterparts in the tabular case. It requires more efforts to solve the experimental design problem over these complicated structures.\n\n**About learning the reward and transition kernel simultaneously:**  Thanks for the interesting question. Although we cannot establish this definitively, we conjecture the answer is negative in the worst case. The problem could be reformulated as finding a mixed policy $\\bar{\\pi}$ to meet two following conditions simultaneously (we set $\\phi(\\tau)$ to be $\\phi_{\\tau}$ for display):\n\n$$\\min_{\\bar{\\pi}\\in \\Delta^{\\Pi}}\\max_{\\pi\\in \\Pi}\\sum_{\\tau}Pr_{\\pi,P}[\\tau]\\phi^{\\top}(\\tau)\\Lambda(\\bar{\\pi})^{-1}\\phi(\\tau)=O(SAH)$$\n\n$$\\min_{\\bar{\\pi}\\in \\Delta^{\\Pi}}\\max_{\\pi\\in \\Pi}\\sum_{s,a,h} \\frac{d_{P}^{\\pi}(s,a,h)}{d_{P}^{\\bar{\\pi}}(s,a,h)}=O(SAH).$$\n\nFor the first problem, the target is to maximize $\\log(\\det(\\Lambda(\\bar{\\pi})))$ \nwhere we recall that $\\Lambda(\\bar{\\pi}) = \\sum_{\\tau}Pr_{\\pi,P}[\\tau]\\phi(\\tau)\\phi^{\\top}(\\tau)$.\n For the second problem, the target is to maximize $\\log(\\Pi_{s,a,h}d_{P}^{\\bar{\\pi}}(s,a,h))=\\log(\\det(diag(\\Lambda(\\bar{\\pi})))$, where $diag(\\Lambda)$ denotes the matrix by setting all non-diagonal elements of $\\Lambda$ to 0. As a result, the two optimization problem are substantially different when $h\\geq 2$. So we conjecture that the answer to your question is probably negative in the worst case.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, I checked all proofs. They all look correct to me.", "experimental_designs_or_analyses": "No experiment is provided in this paper.", "relation_to_broader_scientific_literature": "The closest literature to this paper is (Efroni et al., 2021), which proposes the setting of learning MDP with trajectory rewards. In the previous paper, they show the regret upper bounded by $O(\\sqrt{S^2A^2H^4K})$, which is suboptimal. This paper improve this rate to $O(\\sqrt{SAH^3K})$.", "essential_references_not_discussed": "No. As far as I know, this paper includes sall related references.", "other_strengths_and_weaknesses": "Strength: \n1. This paper is well-written, except few typos I pointed out below.\n2. The paper provides a tight characterization to the regret.\n\nWeakness:\n1. This paper studied the setting of tabular MDP, which is quite restrictive. Additionally, this paper merely tightens the bounds provided in Efroni et al. 21, which is incremental.\n2. I concern about the novelty of this paper. The results are good results, and they match the lower bound, which is also good, but by looking at the proving techniques, it feels that everything is well developed in previous literature and nothing feels special to me.\n3. The upper bound of the algorithm requires a large \"burning in\" phase, which I believe, still having improvement space.", "other_comments_or_suggestions": "Typos: \n(1) in Eq. (1), (Y^t - \\phi_{\\tau^t}^T r) to (Y^t - \\phi_{\\tau^t}^T r)^2\n(2) On the right side of Line 175, d^\\pi_P to d^\\pi_P(\\tau)\n(3) In Line 722 (Line 6 of Algorithm Raw-Exploration), missing symbol \"\\leftarrow\"\n\nSuggestions:\n1. The author mentioned that the preference-based learning can be a possible application to the RL with trajectory feedback. It would be better write down explicitly how does results in this paper implies about preference-based learning.\n2.", "questions_for_authors": "I have the following questions:\n1. Regarding the \"burning in\" term in the regret, e.g. the term that does not scale with K, what is the best you can obtain?\n2. Is it possible to generalize the results into linear MDP, or MDP with function approximation, since the tabular MDP is most restrictive?\n3. The algorithm designed in this paper first learns the transition model $P$, then learn the reward model $r$. Is it possible to learn these two simultaneously?", "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: We thank the authors for their submission.
All in all, the contributions were clear, the paper is well-written and the proofs appear to be sound.
The reviews were reserved about the algorithm not being computationally efficient, and excessively large regret incurred during the burn-in period. Perhaps these can be studied in future work.
Decision: Accept (poster)