On the Theory of Reinforcement Learning with Once-per-Episode Feedback
Authors: Niladri Shekhar Chatterji
Aldo Pacchiano
Peter Bartlett
Michael Jordan
Venue: NeurIPS 2021 Poster (2021)
Keywords: theoretical reinforcement learning
regret analysis
statistical learning theory
non-Markovian rewards
optimistic algorithms

Abstract: We study a theory of reinforcement learning (RL) in which the learner receives binary feedback only once at the end of an episode. While this is an extreme test case for theory, it is also arguably more representative of real-world applications than the traditional requirement in RL practice that the learner receive feedback at every time step. Indeed, in many real-world applications of reinforcement learning, such as self-driving cars and robotics, it is easier to evaluate whether a learner's complete trajectory was either ``good'' or ``bad,'' but harder to provide a reward signal at each step. To show that learning is possible in this more challenging setting, we study the case where trajectory labels are generated by an unknown parametric model, and provide a statistically and computationally efficient algorithm that achieves sublinear regret.

On the Theory of Reinforcement Learning with Once-per-Episode Feedback
Niladri S. Chatterji'
Aldo Pacchiano"
Peter L. Bartlett
Stanford University
Microsoft Research
UC Berkeley
ni diladri@ces stanford edu
apacchiano@microseo....
peterOberkeley. edu edu
Michael I. Jordan UC Berkeley
j jordan@es.
ber.eley.ede..... borda@@cs.berkeeeyyycoom
Abstract
We study a theory of reinforcement learning (RL) in which the learner receives binary feedback only once the end of an episode. While this is an extreme test case for theory, it is also arguably more representative of real-world applications than the traditional requirement RL practice that the learner receive feedback at every time step. Indeed, in many real-world applications reinforcement learning, such as self-driving cars and robotics, it is easier to evaluate whether a learner's s complete trajectory was either "good" or "bad," but harder to provide a reward signal each step. To show that learning possible this more challenging setting, study the where trajectory labels are generated by unknown parametric model, and provide a statistically and computationally efficient algorithm that achieves sublinear regret.
Introduction
The Reinforcement Learning (RL) paradigm involves a learning agent interacting with an unknown dynamical environment over multiple time steps. The learner receives a reward signal after each step which it uses improve its performance empirical success in the recent past [24, 23, 33,
time. This formulation of RL has had significant
While this empirical success is encouraging, as RL starts to tackle more wide- wide-ranging class of consequential real-world problems, such as self-driving cars, supply chains, and medical care, new set of challenges arise. Foremost among them the lack a well-specified reward signal associated with every state-action pair in many real-world settings. For example, consider robot manipulation task where the robot must fold pile of clothes. It is not clear how design useful reward signal that aids the robot to learn to complete this task. However, it is fairly easy to check whether the task was successfully completed (that is, whether the clothes were properly folded) and provide feedback at the end of the episode.
This classical challenge but it is one that often neglected in theoretical treatments of RI.. To address this challenge introduce framework for RL that eschews the need for Markovian reward signal at every step and provides the learner only with binary feedback based on its complete trajectory in an episode. In our framework, the learner interacts with the environment for fixed number of time steps (H) in each episode to produce trajectory (r) which is the collection of all
35th Conference Neural Information Processing Systems (NeurIPS 2021).
"Equal contribution.

---

states visited and actions taken in these rounds. At the end of the episode a binary reward yr E {0, 1] is drawn from an unknown distribution ((|[T) and handed to the learner. This protocol continues for N episodes and the learner's goal is to maximize the number of expected binary "successes."
One approach to deal with the lack of reward function in the literature is Inverse Reinforcement Learning [25], which uses demonstrations of good trajectories to learn a reward function. However, this approach is difficult to use when good demonstrations are either prohibitively expensive or difficult to obtain. Another closely related line of work studies reinforcement learning with preference feedback [2, 15, 3, 5, 37, 26, 38]. Our framework provides the learner with an even weaker form of feedback than that studied in this line of work. Instead of providing preferences between trajectories, we only inform the learner whether the task was completed successfully or not at the end.
To study whether it is possible to learn under such drastically limited feedback study the case where the conditional rewards (y>) are drawn from an unknown logistic model (see Assumption 1). Under this assumption we show that learning is possible-we -e provide an optimism basee algorithm that achieves sublinear regret (see Theorem 3.2). Technically our theory leverages recent results of Russac et al. [31] for the online estimation of the parameters of the underlying logistic model, and combining them with the UCBVI algorithm
[4] to obtain regret bounds. Under an explorability assumption we also show that our algorithm is computationally efficient and we provide dynamic programming algorithm to solve for the optimistic policy at every episode.
We note that Efroni et al. [11] study similar problem to ours, such that reward is revealed only at the end of the episode, but they assume that there exists an underlying linear model that determines the reward associated with each state-action pair, and reward revealed the learner the sum of rewards over the state-action pairs with added stochastic noise. This assumption ensures that the reward function is Markovian, and allows them to use an online linear bandit algorithm [1] to directly estimate the underlying reward function. This not possible in our setting since we do not assume the existence of underlying Markovian reward function. Cohen et al. [6] provided an algorithm that learns in this setting even when the noise is adversarially chosen. An open problem posed by Efroni et al. [11] was to find an algorithm that learns in this setting of reinforcement learning, with once per episode feedback, when the rewards drawn from unknown generalized linear model (GLM). In this paper we consider a specific GLM-the logistic model.
The remainder of the paper organized as follows. In Section 2 we introduce notation and describe our setting. In Section 3 we present our algorithm and main results. Under an explorability assumption we prove that our algorithm is computationally efficient (in Appendix E). Section 4 points to other related work and we conclude with a discussion in Section Other technical details, proofs and experiments are deferred to the appendix.
Preliminaries
This section presents notational conventions and a description of the setting.
2.1 Notation
For any le E N we denote the set (1....,k] }} by [k]. Given any set T, let Ay denote the simplex over this set. Given a vector v, for any p E N, let [[v|pp denote the lp norm of the vector. Given vector and positive semi-definie matrix M. define ||v := Vv Mv. Given matrix M let || denote its operator norm. For any positive semi-definite matrix M we use Amax (M) and Amin (M) to denote its maximum and minimum eigenvalues respectively. We will use C1, C2,... to denote absolute constants whose values are fixed throughout the paper, and c, c' to denote "local" constants, which may take different values in different contexts. We use the standard "big Oh notation" [see, e.g.. 7].
2.2 The Setting
We study Markov decision process (MDP) M = (8, (S,A,P, H). where S the set of states, is the set of actions, ((-1s, a) is the law that governs the transition dynamics given state and action pair

---

(s, a). and H E N is the length of an episode. Both the state space S and action space A are finite in our paper. The learner's 's trajectory T is the concatenation of all states and actions visited during an episode; that is, 7 (81, 01, ,H 0 ). Given any h E [H] and trajectory т, sub-trajectory Th := ($1, di,...... .......,.... 8h, .4) is all the states and actions taken up to step h. Also set To = 9. Let Th: := (5h, .h..... SH, aH) denote the states and action from step h until the end of the episode. Let I be the set of all possible trajectories т. Analogously, for any h E [M] let T' be the set of all sub-trajectories up to step h. At the start of each episode the initial state is drawn from fixed distribution p that is known to the learner.
At the end of episode the trajectory gets mapped to feature map ((T) E R. We also assume that the learner has access to this feature map ø. Here are two examples of feature maps:
1. Direct parametrization: Without loss of generality assume that S fI,..., [S]} and
A = {I..... [A]}. The feature map é(T) = Σ (n(sn.an) where the per-step maps 6 (ss,, a) E RIS||A|H are defined as follows:
(1,,8,))) = {1 j = (h 1ach-1110 1)|S|AA| + 1) +a
to otherwise.
The complete feature map (TT) E IR S||A| is therefore an encoding of the trajectory т.
2. Reduced parametrization: Any trajectory T associated with a feature ((T) E IRd, where d < |H.
After the completion of an episode the learner is given a random binary reward yr E {0, 1j. Let W, E Rd be a vector that unknown to the learner. We study the case where the rewards are drawn from binary logistic model as described below.
Assumption 2.1 (Logistic model), Given any trajectory + E T, the rewards are said to be drawn from a logistic model if the law of yr [ is
1e (( (())) 1 1- 1 (w. ((T)),
wap.
0
w.p.
where for any = E R. p(z) [+exp(-s] is the logistic function. We shall refer to w. as the "reward parameters." "
We make the following boundedness assumptions on the features and reward parameters. Assumption 2.2 (Bounded features and parameters). We assume that
|w.112 < B for some known value B > 0 and
for all T I. [[o(T]]l2 S 1.
We note that such boundedness assumptions are standard in the logistics bandits literature [13, 31, 14].
A policy v a collection of per-step policies (mi, (.I,...,, TH) such that
Th T S A
If the agent is using the policy x then at round h of the episode the learner plays according to the policy Th. We let II, denote the set of all valid policies at step and let IT denote the set of valid policies over the trajectory. Let 1P (-|s;) denote the joint probability distribution over the learner's s trajectory т and the reward y, when the learner plays according to the policy and the initial state is si Often when the initial state clear from the context we will refer to Pd (-Ist) by simply writing par Also with some abuse of notation will sometimes let F denote the distribution of the trajectory and the reward where the initial state is drawn from the distribution p.
Given initial state S the value function corresponding to a policy क is
v (s) = Ey [V+
81 = s) = Erare IM (TT) |s = s]
3

---

where the second equality follows as the mean of yr conditioned on T is p W Φ(T)). With some abuse of notation we denote the average value function as V := Ee [s](s))
E arg m V It is worth noting that in our setting the optimal policy may be non-Markovian. The learner plays for a total N episodes. The policy played in episode & [N] is (()) and its value function is V(O = ya Also define the value function for the optimal policy to be V, = V Our goal shall be to control the regret of the learner, which is defined as
Define the optimal policy
R(N)
Σ V. V(4
The trajectories in these N episodes are denoted by {7(0) [y')]
Jt=1 and rewards received are denoted by
3 Optimistic Algorithms that Use Trajectory Labels
We now present an algorithm learn from labeled trajectories. Throughout this section we assume that both Assumptions 2.1 and 2.2 are in force.
The derivative of the logistic function is /²(2) (1+exp(-2))
exp(-=) and therefore, yr is 1/4-Lipschitz.
The following quantity will play an important role in our bounds
max sup rel willw]lsB p'(w ((())))
A consequence of Assumption 2.2 is that S eBp( We briefly note that is measure of curvature of the logistic model. It also plays an important role in the analysis of logistic bandit algorithms [13, 31].
Since the true reward parameter w, is unknown will estimate it using samples. At any episode I E [M], a natural way of computing an estimator of w., given past trajectories {7(9) } and
labels { Ige[e-1], is by minimizing the lz-regularized cross-entropy loss:
(.(w) := - Σ y/s) log (N (wTT((()))) (1 - (s) log (1 (1- (w (T(o((()))) + |w13
t-1
2
This function strictly convex and its minimizer defined to be
== arg min Ce (ww). wERd
(3)
Define design matrix every episode
Σ = sl, and
E, = xI + Σ
Φlr ( )6( for all t 2 1.
q=1
Further, define the confidence radius (5) as follows
(x( (1 + B + pr())
(V1+
B + +
3/2
(4)
41
1
where, (5) == d log 4
+ 2og
2
We adapt result due Russac et al. [31, Proposition 7] who studied the online logistic bandits
problem to establish that at every episode and every trajectory the difference between u(w. Φ(T)) and p( W ((T)) is small.
Lemma 3.1. For any 8 (0,1). 1). define the event
Es = for all E [N], E P [p(w] ((T)) - ((TTT(()))) ((T)) & (=8(()))((()), 1 (5)
Then PPEs) 2 8.

---

We provide a proof in Appendix B.2. The proof follows by simply translating [31, Proposition 7] into our setting. We note that we specifically adapt these recent results by Russac et al. [31] since they directly apply Wr, the minimizer of the fz-regularized cross-entropy loss. In contrast, previous work on the logistic bandits problem [see, e.g., 14, 13] established confidence sets for an estimator that was obtained by performing non-convex (and potentially computationally intractable) projection of W, onto the ball of Euclidean radius B.
Our algorithm shall construct an estimate the transition dynamics P,, Let (2 a) be the number of times that the state-action pair (s, a) is encountered before the start of episode t, and let (s'; s, a) be the number of times the learner encountered the state s' after taking action state before the start of episode t. Define the estimator of the transition dynamics as follows:
(a(s'a,,s) = Ne(s';s,a)
(6)
Ne(s,a)
Also define the state-action bonus at episode t
(SNN log(A)(s.a))
2 min 2, 2,41 log
(s,
In this definition whenever Ne(s, a) = O. that is, when state-action pair hasn't been visited yet, we define cli to be equal to 2. Finally, define the optimistic reward functions
(w, r) == min (w T ((T)) + Vib((0)1o(())le
and
(8a)
(w. : (.(w, Σ
(())
(8b)
S55.0m
The first reward functiin Pr is defined as above to account for the uncertainty in the predicted value of w, in light of Lemma 3, and the second reward function jú, is designed to account for the error in the estimation of the transition dynamics P. With these additional definitions in place we are ready to present our algorithms and main results.
3.1 UCBVI with Trajectory Labels
Our first algorithm is an adaptation of the UCBVI algorithm [4] to our setting with labeled trajectories.
Algorithm 1: UCBVI with trajectory labels.
Input: State and action spaces S,A.
2 Initialize P, = O, visitation set K
for t == 1,... do
1. Calculate the w, by solving equation (3).
2. If > 1, compute (()
(1) E arg max E,, simpp, PP(p)) (W,, T) TEll
(9)
Else for all h, 7h-1 [H] x S x T set The (1) over the action set. Observe the trajectory (1) p= and update the design matrix
(+|s, Th 7h-1) 1) to be the uniform distribution
Σ KI +
o ((7(0)((77))
(10)
-=1
4. Update the visitation set KC ((5, S A: N1(s, a) 0).
5. For all (s, a) E K, update P142 a) according to equation (6).
For all (s,a) a) & K. set P+41 a) be the uniform distribution over states.
5

---

Theorem 3.2. For any E (0, 11, set d = (6N) then under Assumptions 2.7 and 2.2 the regret of Algorithm 1 is upper bounded as follows:
R(N) S (
H² Vnd(d + B3/3]] VN + (H (S)AAI
with probability al least - 8.
The regret of our algorithm scales with VN and polynomially with the horizon, number of states, number of actions, K, dimension of the feature maps and length of the reward parameters (B). The minimax regret in the standard episodic reinforcement learning is O( D(V S)|A|[N) [27, 4]. Here we pay for additional factors in H, [S] and & since our rewards are non-Markovian and are revealed to the learner only the end of the episode. We provide proof of this theorem in Appendix B. For more detailed bound on the regret with the logarithmic factors and constants specified we point the interested reader to incquality (41) in the appendix.
Proof sketch. First we show that with high probability each episode the value function of the optimal policy V, upper bounded by V() ;= IE
s1mp, r~ [ite (e,.)] r)] (the value function of the policy x(1) when the rewards are dictated by jr and the transition dynamies given by P.). Then we provide a high probability bound on the difference between the optimistic value function (t) and the true value function (*)) to obtain our upper bound on the regret. In both of these steps we need to relate expectations with respect to the true transition dynamics IP to expectations with respect to the empirical estimate of the transition dynamics Pt. We do this by using our concentration results: Lemmas
and B.2 proved the appendix. While analogs of these concentration lemmas do exist in previous theoretical studies of episodic reinforcement learning, here had to prove these lemmas in our setting with non-Markovian vajectory-level feedback (which explains why we pay extra factors H and (S).
3.2 UCBVI with Added Exploration
Although the regret of Algorithm is sublinear it guaranteed to be computationally efficient since finding the optimistic policy x(1) (in equation (9)) at every episode might prove to be difficult. In this section, we will show that when the features are sum-decomposable and the MDP satisfies an explorability assumption then it will be possible find a computationally efficient algorithm with sublinear regret (albeit with slightly worse scaling with the number of episodes N).
Assumption 3.3 (Sum demopoccopooaalle features). We assume that the feature maps & Rd are sum-deccoposable over the different steps of the trajectory, that is, ((T) = - @n(sh an).
Under this assumption, given any w Rd and any trajectory 7 E r, w (()) E w T Φn (sh, ax). We stress that even under this sum-decomposablity assumption, the opti- mal policy potentially Mon-Markovian due to the presence of the logistic map that governs the reward.
We also make the following explorability assumption.
Assumption 3.4 (Explorability). For any s, E S. a, E A. and h # h' E [H], suppose that
a)) ow (s'd'')) =0)
Further assume that there exists (0, 1) such that for any unit vector Rd we have that
sup E, P Tlll
Σ HEIH
T (h and
2 w.
In setting with Markovian rewards similar assumption has been made previously by Zanette et al. [40]. This assumption allows us to efficiently "explore" the feature space, and con- struct a sum-decomposabbl bonus (5) EH | (8h, ax)ll x-- that we will use instead of

---

(=3)(0)(0(T))) in the definition of fh (see equation (8a)). Define the reward functions
pta (w, min p (w ((T)) (R)
> on (sh, 01)llx7",11 1
and
(1la)
H-1
(e = p (w, T)
Σ
(11b)
h=1
To prove regret bound for an algorithm that uses these rewards our first step shall be to prove that the uun-decomposable bonus also leads to an optimistic reward function (that is, the value function defined by these rewards sufficiently over-estimates the true value function). To this end, will first use Algorithm 2 to find an exploration mixture policy U and play according to it at episode / with probability 1/11/3, This policy U will such that the minimum eigenvalue of
E sy r~P" (-Jax) [o(T))(T)]]
(12)
lower bounded by function of d, w and N (see Lemma 3.5). This property shall allow us to upper bound the condition number of the design matrix E, and subsequently ensure that the rewards fit and fi are optimistic. Given unit vector v define a reward function at step as follows:
(s, == v on(ssa))
(13)
Let rV (rY... ........ h be reward function over the entire episode. a subroutine Algorithm uses the EULER algorithm [39]. (We briefly note that other reinforcement learning algorithms with PAC or regret guarantees [e.g.. 4, 19] could also be used here in place of EULER.)
Algorithm 2: Find exploration mixture.
Input: Initial unit vector v,, Exploration lower bound w, number of EULER episodes NEUL. number of evaluation episodes NEVAL-
2 Initialize: Ao 16
2²
and Amin inf zead T Agz.
while Amin < 2² do
8
Update the counter t n 1. Un - (ULER(((")) NEUL) // //run EULER for NEUL episodes.
for f=/,- .NEAAL episodes do
L Sample trajectory Tn ~ ppx x pl...
Calculate the average feature ān Eiet (b(((1) (1)) //EEALL
Nev
Update the matrix A, An-1 + a Update the minimum eigenvalue: Amin +- inf z AnZ.
10
Set Vn to be the minimum eigenvector of A,,
Set Yoloop
Return: (i) Unif(U .Una //the uniform mixture the policies;
(ii) Nexp TNloop x (NEUL NEVAL) //total number of episodes.
Lemma 3.5. There exist positive absolute constants C₁ and C2 such that, under Assumptions 2.2, 3.3
and 3.4, if Algoritth 2 is run with NEUL CilsPlA H² log [
and NEVAL Cyd log" Na²
and N > d'oog( 1 18N
log(3/2) (NEuL + NEVAL) =: Nexp then, with probability at least 28, we have
Nexp I Neep and furthermore:
W log(3/2) B Bsia, T- ((o) [ 32dlog (d (1 + d
I.
This lemma proved in Appendix With this lemma in place now present our modified algorithm under the explorability assumption. In the first few episodes this algorithm finds the exploration mixture policy (+) which maximizes the value function associated with the rewards pod (We, 7) with probability 27 Otherwise it uses the exploration mixture policy U.
a subsequent episode this algorithm acts according to the policy

---

Algorithm 3: UCBVI with trajectory labels and added exploration.
Input:
State and action spaces S, A, Initial unit vector V1, Exploration lower bound w, number of EULER episodes NEUL: number of evaluation episodes NEVAL-
Initialize P1
visitation set K 9.
Find exploration mixture policy U in Noxp episodes by running Algorithm for t Nexp 1.... ,N do
1. Calculate W, by solving equation (3).
2. lft Nexp + L, compute (())
19
E arg max E simp, P- (-181) [ (wr,))]
(14)
Else for all h, Th-1 [H] x S x - set 1 (1) over the action set.
(-18, 7h to be the uniform distribution
Sample b.
w.p. 1
3173,
I.
1 w.p. 2133
4. If = 1 then set x! t U.
Observe the trajectory 7(1) ~ pa and update the design matrix
E.11 RI
(6(
(15)
N=
10
6. Update the visitation set K {(s,(( E A: (s, a) 0}.
11
For all (s, a) E K, update (- a) according to equation (6).
8. For all (s,a) a) & K. set P-41(-1s, a) to be the uniform distribution over states.
The following is our regret bound for Algorithm
Theorem 3.6. For any 8 (0, 1], set 8/(12N). Under Assumptions 2.1, 2.2, 3.3 and 3.4, and for all N > Neep (see its definition in Lemma 3.5) if Algorithm 3 is run with the parameters NEUL and NEVAL set as specified in Lemma 3.5 then its regret upper bounded as follows:
R(N) 2 ( (VRHd (d3 B3/2) + H (H + SIISII H2 VN
& d2 we (1
+(H + (H++
with probability at least
The proof of Theorem 3.6 is in Appendix D. For more detailed bound the regret with the logarithmic factors and constants specified we point the interested reader to inequality (58) in the appendix. The bound on the regret this algorithm scales with N2/3 up to poly-logarithmic factors. This is larger than the / N regret bound (again up to noly-logarithmic factors) that we proved above for Algorithm since here the learner plays according to the exploration policy U with probability 1/12/3 throughout the run of the algorithm. However, the next proposition shows that by using the sum-decomposable reward function fod the policy (1) defined in equation (14) can be efficiently approximated.
Proposition 3.7. For any t [N] define Vir(()) == E., (+1a)) (Tr (we, +)]. Given any under Assumptions 2.2, 3.3 and 3.4 it possible to find policy #()) that satisfies
Vis (+(()(()) Se,
using most poly (IS), H, d, 12, 1 log ) time and memory.
We describe the approximate dynamic programming algorithm that can be used find this policy (0)) and present proof of this proposition in Appendix E. We also note that if we use

---

e-approximate policy +(*) instead of x0)) in Algorithm 3 then its regret increases by an additive factor of at most eN. (It is possible to casily check this by inspecting the proof Theorem 3.6.) Thus, for example choice of 1 1/N1/3 ensures that the regret of Algorithm 3 is bounded by ((N2/3) with high probability if the approximate policy (()) (which can be found efficiently) is used instead.
4 Additional Related Work
There have been many theoretical results that analyze regret minimization in standard episodic reinforcement [18, 29, 16, 28, 4, 19, 8, 39, 34, 10, 30]. Recently Efroni et al. [12] introduced a framework of "sequential budgeted learning" which includes as a special case the setting of episodic reinforcement learning with the constraint that the learner is allowed to query the reward function only a limited number of times per episode. They show learning is possible this setting by using a modified UCBVI algorithm.
As stated above to estimate the reward parameter we rely on the recent results by Russac et al. [31] who in term built on earlier work [13, 14] that analyzed the GLM-UCB algorithm. Dong al. [9] provided and analyzed a Thompson sampling approach for the logistic bandits problem.
Discussion
We have shown that efficient learning is possible when the rewards are non-Markovian and delivered to the learner only once per episode. It would be interesting to see if one can establish guarantees under more general reward models than the logistic model that we study here. Another interesting question is if faster rates of learning are possible when the learner obtains ranked trajectories (that is, moving beyond binary labels).
Acknowledgments
The authors would like to thank Louis Faury, Tor Lattimore, Yoan Russac and Csaba Szepesvári for helpful conversations regarding the literature logistic bandits. We thank Yonathan Efroni, Nadav Merlis and Shie Mannor for pointing us to prior related work.
Funding
We gratefully acknowledge the support of the NSF through the grant DMS-2023505 in support of the FODSI Institute.
References
[1] Y. Abbasi-Yadkori, D. Pál, and Szepesvári. Improved algorithms for linear stochastic bandits.
In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
[2] R. Akrour, M. Schoenauer, and M. Sebag. Preference-based policy learning. In Join! European Conference on Machine Learning and Knowledge Discovery in Databases, pages 12-27, 2011.
[3] R. Akrour, M. Schoenauer, M. Sebag, and J.-C. Souplet. Programming by feedback. In International Conference on Machine Learning, pages 1503-1511, 2014.
[4] M. G. Azar, Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272, 2017.
[5] Christiano, Leike, B. Brown, M. Martic, Legg, and D. Amodei. Deep reinforcement
learning from human preferences. In Advances in Neural Information Processing Systems, page 4299 4307, 2017.
[6] A. Cohen, H. Kaplan, T. Koren, and Y. Mansour, Online Markov decision processes with aggregate bandit feedback. arXiv preprint 202.v:200..00490, 2021.
[7] Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to algorithms. MIT Press, 2009,

---

[8] C. Dann, T. Lattimore, and E. Brunskill. Unifying PAC and regret: uniform PAC bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, pages 5717-5727, 2017.
[9] S. Dong, T. Ma, and B. Van Roy. On the performance of Thompson sampling on logistic bandits. In Conference on Learning Theory, pages 1158-1160, 2019.
[10] Y. Efroni, N. Merlis, M. Ghavamzadch, and Mannor. Tight regret bounds for model-based reinforcement learning with greedy policies. In Advances in Neural Information Processing Systems, pages 1 12224-12234, 2019.
[1]] Y. Efroni, N. Merlis, and S. Mannor. Reinforcement learning with trajectory feedback. In AAAI
Conference on Artificial Intelligence, pages 7288-7295, 2021.
[12] Y. Efroni, N. Merlis, A. Saha, and S. Mannor. confidence-budger matching for sequential budgeted learning. arXiv preprini arXiv:2102.03400, 2021.
[13] L. Faury, M. Abeille, C. Calauzènes, and O. Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning pages 3052-3060, 2020.
[14] S. Filippi, O. Cappe, A. Garivier, and C. Szepesvári. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems, pages 586-594, 2010.
[15] J. Fürnkranz, E. Hüllermeier, W. Cheng, and S.-H. Park. Preference-based reinforcement learning: a formal framework and a policy iteration algorithm. Machine learning, (9(1-))
123-156, 2012.
[16] A. Gopalan and S. Mannor. Thompson sampling for learning parameterized Markov decision processes, In Conference on Learning Theory, pages 861-898, 2015.
[17] S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055-108) 2021.
[18] T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning.
Journal of Machine Learning Research, 11(4), 2010.
[19] C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4868-4878, 2018.
[20] C. Jin, A. Krishnamurthy, M. Simchowitz, and T. Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4879, 2020.
[21] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
[22] Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[23] S. Levine, C. Finn, T. Darrell, and P. Abbeel. End-to-end training of deep visuomotor policies. Journal of Machine Learning Research, 17(1)1334-13775 2016
[24] V. Mnih, K. Kavukcuoglu, D. Silver, A. Rusu, J. Veness, M. Bellemare, A. Graves. M. Riedmiller,
A. Fidjeland, G. Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540))522 533, 2015.
[25] A. Ng and S. Russell. Algorithms for inverse reinforcement learning. In International Confer- ence on Machine Learning. pages 663-670, 2000.
[26] E. Novoseller, Y. Wei, Y. Sui, Y. Yue, and J. Burdick. Dueling posterior sampling for preference- based reinforcement learning. In Conference on Uncertainty in Artificial Intelligence, pages 1029-1038, 2020.
[27] I. Osband and B. Van Roy. On lower bounds for regret in reinforcement learning. arXiv preprint 160iv:1608.0 02732, 2016.
[28] I. Osband and B. Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International Conference on Machine Learning, pages 2701-2710, 2017.
[29] I. Osband, D. Russo, and B. Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, pages 3003-3011, 2013.
[30] A. Pacchiano, P. Ball, Parker-Holle Holder, K. Choromanski, and S. Roberts. On optimism in model-based reinforcement learning. arXiv preprint arXiv:2006. 1911, 2020.
10

---

[31] Y. Russac, L. Faury, O. Cappé, and A. Garivier. Self-concordant analysis of generalized linear bandits with forgetting. In International Conference on Artificial Intelligence and Statistics, pages
2021.
[32] A. Senior, R. Evans, J. Jumper, Kirkpatrick, L. Sifre, T. Green, C. Qin, A. Zidek, A. W. Nelson, A. Bridgland, et al. Improved protein structure prediction using potentials from deep learning. Nature, 577(7792):06-7710 2020.
[33] D. Silver, J. Schrittwieser, Simonyan, I. Antonoglou, Huang. A. Guez, T. Hubert, Baker, M. Lai, A. Bolton, et al. Mastering the game of Go without human knowledge. Nature, 550
(7676):354-35, 2017.
[34] M. Simchowitz and K. G. Jamieson. Non-asymptotic gap-dependent regret bounds for tabular MDPs. In Advances Neural Information Processing Systems, pages 1153-1162, 2019.
[35] Tropp. Freedman's 's inequality for matrix martingales. Electronic Communications in Proba- bility, 16:262-2700 2011.
[36] R. J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcmeettt learning. Machine learning, 8(3-4):229-25 256, 1992.
[37] C. Wirth, R. Akrour, G. Neumann, and J. Fürnkranz. survey preference-based reinforcement learning methods. Journal of Machine Learning Research, 18(136):1-46 2017.
[38] Y. Xu, R. Wang, L. Yang. A. Singh, and A. Dubrawski. Preference-baie reinforcement learning with finite-time guarantees. In Advances in Neural Information Processing Systems, pages
18784-18794, 2020.
[39] A. Zanette and E. Brunskill. Tighter problem-dependent regret bounds reinforcement learning without domain knowledge using value function bounds. In International Conference Machine Learning, pages 7304-7312, 2019.
[40] A. 7anette, A. Lazaric, M. J. Kochenderfer, and E. Brunskill. Provably efficient reward-agnostic navigation with linear value iteration. arXiv preprint urXiv:2008.07737, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All assumptions are stated clearly with the accompanying thcoretical results.
(b) Did you include complete proofs of all theoretical results? [Yes] The complete proofs of all theoretical results are carefully proved in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See Section F.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section F.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] See Figure 1.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (c.g., code, data, models) or curating/releasing assets...

---

(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "vSMtOUBGL2Q", "reviewer": "Reviewer_RHC6", "summary": "The authors discuss an RL setting where the reward is given trajectory-wise instead of a per state-action reward. In this settings, they assume the reward is given by a GLM over a feature space representing the trajectories. First, the consider this general case, and prove a $O(\\sqrt{T})$ regret bound for a computationally inefficient algorithm. To address this problem, the add assumption regarding the feature space, and devise a computationally efficient algorithm which achieves $T^{2/3}$ regret.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Quality and Clarity\nThe once-per-episode reward feedback setting is a very important extension to the usual RL model. The motivation given by the authors is very clear: Indeed, one of the shortcomings of RL is the need for a properly specified reward function, an assumption which is often far from reality.  The paper is very clearly written and easy to follow.\n\n## Originality and Significance\n\n1. This work extends the work of Efroni et al. [1] to the more general setting of GLM. Specifically, [1] consider a once-per-episode reward which is an additive sum of the rewards in state-action pairs observed in this episode. Instead, this work deals with rewards defined over the whole trajectories (by GLM over the trajectory rewards features). For this scenario, the authors achieve a $O(\\sqrt{T})$ regret. However, this extension to the GLM setting seems a bit incremental, as it just an adaptation of known results on the online logistic bandits together with UCBVI. Moreover, the proposed algorithm is computationally infeasible algorithm, as opposed to the prior work in [1].  \n\n2. To improve this result computationally-wise, the authors make two assumptions: 1) sum-decomposability of the features: this assumption basically constraint back the rewards to being \"markovian\" (i.e. being state-action dependent). 2) \"Explorability\" - to my understanding, this mostly demands the feature space to be of size $d\\geq HSA$, colliding with the usual tabular rewards assumption. Therefore, it is not clear, why this case is more general than the one considered in [1]. For this case, the authors provide a $T^{2/3}$ rate, which is not optimal, and is strictly worse than the rate derived in [1]. Thus, I would appreciate if the authors will give some information or motivation to when these assumptions are valid, besides the regular tabular case, to understand whether this algorithm truly improves prior works in terms of generality.\n\n\n## Comments and Questions:\n\n* Why is the pure exploration phases of algorithm 3 mandatory?  Furthermore, do you need to know $\\omega$ in order to find $\\bar U$. If so, is there any explanation for how to estimate this parameter?\n\n* Why does the optimization problem in eq. 3 use L2 regularization and not shannon-entropy? It seems more natural with the cross-entropy loss.\n\n* In a way, this work deals with the representation of the unobserved rewards. As one only sees once-per-episode reward, the \"true\" reward signal does not matter (or does not exist), and is more of an artifact of the chosen representation. Do you agree with this claim? If so, it might be valuable to discuss this view in the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "t10LVh_idaD", "reviewer": "Reviewer_NUdX", "summary": "This paper studies the RL problem where the learner only receives feedback once at the episode endpoints. The case where trajectory labels are generated by an unknown parametric model is investigated. An algorithm is proposed for achieving sublinear regret. \n", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- The related work section can be strengthened. The difference and novelty of the results should be better highlighted. \n- The presentation of the paper needs improvement. For instance, the formulation is presented without much justification. The assumptions are also stated without explanation. The significance and motivation of the problem are both not clear. \n- It would be helpful if the authors could highlight the technical novelty of the results. Right now the algorithms appear intuitive. Also, it appears hard to directly see the advantage of the algorithms. For instance, the additional factor H in Theorem 3.2 seems quite natural. The reviewer wonders whether such a bound can also be obtained by adapting an existing algorithm and treat each episode as a timestep. Intuitively, this might only enlarge the bound by a similar factor? Please elaborate. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper needs improvement in motivation, related work, and also the presentation of the technical contents. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "hg7HJwDenF8", "reviewer": "Reviewer_NR8J", "summary": "This paper considers a special RL problem where the learner receives a binary reward only once at the end of an episode. The paper argues that this special RL problem is more representative of real-world applications than the traditional requirement in RL (reward per step). For this problem, the paper considers a setting that seems to be slightly general than the tabular one and provides a provably efficient algorithm that achieves sub-linear regret.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The Once-per-Episode binary reward problem considered in the paper is interesting, novel, and is clearly presented. The paper provides a solution to the problem and shows some theoretical analyses for the proposed solution. Overall I like the paper and would like to recommend its acceptance if the following question could be addressed:\n\nHow to know omega? The authors may consider the tabular setting for simplicity. \n\nTwo comments/questions:\n\nThe experiment does not show the empirical results of the proposed algorithm, but the results of some other algorithm (REINFORCE). Given that the paper's main contributions are theoretical, it is not necessary to include an experiment in the paper. And it is definitely not a good idea to include an experiment that tests an algorithm not proposed by the paper.\n\nWhy does the paper consider Assumptions 3.3 and 3.4 instead of the tabular case (direct parameterization) directly? First, it does not seem to be easy to come up with feature maps other than the tabular features if Assumption 3.3 and 3.4 are made. Secondly, algorithm 3 is already tabular -- it needs to learn a tabular model. \n\n[Update]\nAfter several two rounds of discussions with the authors and having read other reviewers' reviews and authors' replies, I decided to raise my score from 5 to 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "awkUal5JCmy", "reviewer": "Reviewer_jHzB", "summary": "This paper studied reinforcement learning with once-per-episode rewards. The rewards can be non-Markov and draw from an unknown logistic model. The algorithm has two parts in an optimistic estimation of the logistic model part and a policy learning part with the optimistic reward estimation. The second part can be computationally hard without further assumption, and the paper included a computationally efficient dynamic programming algorithm under a strong condition: the non-Markov features for the logistic model can be decomposed as a sum of Markov features.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem studied in this paper is common in practice but often neglected in theoretical treatments of RL. The theoretical contribution in this paper is also solid. Overall I think it is a good paper. My main concern for this work is the motivation of the particular reward setting and its practicality.\n\nPros:\n1. It studied an important problem, proposed a (computationally inefficient) algorithm with strong statistical guarantees.\n\nCons \n1. Comparing with the standard RL algorithm, the main difference is the proposed algorithm can deal with non-Markov rewards. However, in the motivating scenario, when it is fairly easy to check whether the task was successfully completed, this signal or related context can also be fairly easy to be included in the state features. Thus the reward signal can still be Markov. \n2. The logistic model settings seem does not to fit well in the scenario either. Is there that much stochastic to check the success/failure of a task? In control problems often the stochasticity is in transitions dynamics. I understand that the logistic model provides convenience for estimating the reward parameters, but does that really fit the problem motivation well?\n3. The algorithm in section 3.1 seems to be impractical due to the policy search oracle. The algorithm in section 3.2 requires the sum-decomposable features. Then it is the same as the setting considered by Efroni et al. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: While two of the reviewers are a bit skeptical about the contributions of the paper and consider them to be incremental, the two other reviewers find that the extensions presented in the paper are worthwhile. All reviewers agree that the current presentation does not sufficiently point out the technical contributions wrt previous work (in particular Efroni et al) nor are made assumptions sufficiently discussed. After having a brief look at it myself, I recommend to accept the paper. For the final version, please take into account the reviewers' comments. In particular, the technical novelties shall be highlighted as well as the made assumptions discussed in detail, that is, why are they needed and in which cases can they be expected to hold in practice.
Decision: Accept (Poster)