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@microsoo....
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: := (Sh, .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 ((T) 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) j
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+e
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 - (() 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, a' E A. and h # h' E [H], suppose that
a)) ow (s'd'')) =
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)llx,1,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" (-|ax) [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 μit 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": "ySAIDAVGDaW", "reviewer": "Reviewer_ViC9", "summary": "The paper tackles RL problems where feedback is received only at the end of each episode. Specifically, they extend the trajectory-feedback model of Efroni et al.[10] in two aspects: first, the reward is logistic, and not the sum of state-action rewards, and second, they allow per-trajectory feature representation, instead of working with state-action-visitations. In this setting, they first combine UCBVI with a UCB algorithm for GLMs to derive $\\sqrt{N}$ regret bounds (where $N$ is the number of episodes). However, the resulting algorithms is computationally intractable, Then, under specific assumptions on the feature representation (‘sum-decomposable features’ and ‘explorability’) they provide an additional algorithm with $N^{2/3}$ regret and polynomial per-episode computational complexity.", "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": "I think that the setting of once-per-episode feedback (or trajectory feedback) is interesting for two reasons. First, as states in the paper, per-state feedback is not always available, and per-episode feedback is more natural in many applications. Then, this model actually bypasses the need for reward shaping. In addition, it is a good starting point for learning RL problems with non-Markovian rewards.\n\nHowever, I think that there is a major computational issue with the results of this work. First, although Algorithm 1 achieves an optimal regret rate of $\\sqrt{N}$ (up to problem-dependent constants of $S, A, H$), the algorithm is computationally intractable. Second, I have some concerns regarding the UCBVI algorithm with the added exploration:\n- The two parts of assumption 3.4 are somewhat contradicting each other. The most natural way to meet the condition of $\\phi_h(s, a)^T\\phi_{h’}(s, a)=0$ is to allocate different features (or orthogonal subspaces) to each timestep. However, this means that the second requirement of the assumption does not hold. Is there any reasonable problem instance with natural features for which both parts of the assumption simultaneously hold? \n- The main reason for this algorithm is its computation tractability, but the computational requirements are hidden in $O$-notations, and I found it hard to understand them even when looking at the appendix. Concretely, what is the computational complexity for any given $\\epsilon$, and specifically, for $\\epsilon$ such that the regret will not degrade any further? Even if it is polynomial but badly depends on $S, A,1/\\epsilon$, the algorithm is not necessarily tractable.\n- I want to ignore the logistic function for a moment. Then, if I understand correctly, the sum-decomposable assumption essentially results with a (structured) Markovian reward ($r_h(s,a)=w^T\\phi_h(s,a)$), and then, one could probably just use a variant of the algorithm in [10]. When adding the logistic function, one can then replace the linear TS with a GLM TS, and since GLMs are monotone, maximizing the internal linear function is equivalent to maximizing the GLM. Notably, doing so might lead to an algorithm that only requires GLM TS and standard planning. Of course, there are numerous small details to sort out, but if you agree that this should work (and I would love to hear your opinion on the matter), then this would result in a computationally efficient $\\sqrt{N}$ algorithm, and not $N^{2/3}$. Then I would expect this paper to prove comparable regret bounds and/or extend to feature maps that are not so easily covered.\n- Finally, another issue with assumption 3.4 is that the orthogonality requirement $\\phi_h(s, a)^T\\phi_{h’}(s', a')=0$ leads to a dimension constraint of $d\\ge SA(H-1)$ (assuming meaningful features $\\phi_h(s, a)\\ne 0$) - this is almost the same number of features as the direct parameterization, so there's no dimensionality reduction. If the sum-decomposable assumption indeed leads to a Markovian reward and there's no dimensionality reduction, is there any reason not to use the direct parameterization?\n\n***************************\n\nOther questions/comments:\n- Can you further explain why you specifically require the logistic function and whether the results could be extended to other GLMs?\n- In general, it would have been nice to see some examples of problems with natural feature maps that are not the direct parameterization. \n- Another issue that should be mentioned (but is arguably unavoidable) – the minimization of the regularized cross-entropy loss – maybe it can be mitigated by doing rare updates (e.g., according to some doubling trick)?\n- Algorithm 2: EULER is, in general, a regret minimization algorithm, so it usually does not output a policy – what is $U_n$?\n- Another comment/limitation – for lemma 3.5, one must know $\\omega$, which seems nontrivial, especially since it depends on the dynamics of the MDP.\n- Can you add an algorithm block (even in the appendix) for the planning algorithm of Proposition 3.7?\n- Simulations – what is the added value of simulating REINFORCE? In my opinion, simulations are a ‘nice-to-have’ in this work, but if you perform them, the interesting thing is to simulate your algorithm (and maybe measure its runtime and show that it is a no-regret algorithm, namely, converges to the optimal policy at a reasonable rate).\n\n***************************\n\nMinor issues:\n- Algorithm 3, step 2 – the if-else seems unnecessary.\n\n***************************\n\nI thank the authors for their response. Even after the clarifications, I still find the assumptions and the resulting bounds a bit too weak, so I decided to leave my score unchanged.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In general, most limitations are clear. I would only add explicit bounds on the computational complexity (as mentioned in the main review) and a comment about the requirement to know $\\omega$.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "gOLmmh4Jvm", "reviewer": "Reviewer_NZK6", "summary": "\nThe authors studied an RL setting in which the feedback is received once per-episode. Unlike previous works, the authors assumed the value of a policy is given by E_{\\tau~\\pi}[ logistic(w * \\phi(\\eta))] where \\tau is a trajectory sampled by following the policy \\pi. That is, the transition model is Markovian, but the model is not an MDP, since the value is a non-linear function of the cumulative reward.\n\nThe authors then studied two algorithms for this setting. \n1) A computationally hard algorithm, based on GLM-bandits analysis. \n2) Under additional assumptions -- 3.3 and 3.4 -- a computationally  tractable algorithm for this setting (nevertheless, the computational complexity of this approach scales poly(N), where N is the number of episodes, which makes this algorithm problematic from practical perspective).\n", "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": "Pros.\n1) The setting is of interest and the results extend what is currently known for the setting in feedback is received only once per episode.\n\n2) The planning algorithm (presented in Appendix E) which the authors suggested to solve line 9 of algorithm 1 is novel to the best of my knowledge.\n\nCons.\n1) I understand why the suggested model is natural from a theoretical perspective. However, it seems not very natural from practical point of view (and the authors do not motivate this model from the practical perspective). In which practical scenarios we can expect the value of a policy to be given as E_{\\tau~\\pi}[ logistic(w * \\phi(\\eta))]?\n\n2) The writing needs to be improved in several critical aspects in my opinion.\n\na) The assumptions made are quite restrictive (both the modelling assumption and the assumptions needed for the analysis). The authors do not elaborate on these assumptions - why these assumptions (especially assumption 3.4) are needed? why the analysis fails without them? It seems that assumption 3.4 is quite harsh on its own, let alone knowing the value of \\omega. Can the suggested algorithm be adaptive to an unknown value of \\omega?\n\nb) The relation to GLM is not explain well enough - what is special about the logistic mapping as oppose to GLM? in section 2 can't the result be established for a general GLM function instead of the logistic mapping? if not, why is it challenging? I believe that these questions are much important for a reader. Furthermore, does the parameter \\kappa arises in bandits with GLM parametrization? or is it a new parameter the authors introduce.\n\nc) In the experimental part a different algorithm is being implemented. I believe this can create confusion and harms the readability of this work. \n\nReference to previous works.\n1) Lemma C.1. can be found in \"Improved Algorithms for Linear Stochastic Bandits\". I believe the authors should cite it.\n\n-) Minor questions.\n-) What does equation 66 mean? why the LHS equal to the RHS?\n\n-) Minor\n1) Stating that this work deals with non-Markovian reward is confusing. Is there a reason not to explicitly mention the assumption 2.1 in the name? for example, logistic-reward function / trajectory logistic-reward function. This makes the parametric assumption much more apparent. \n2) I found the notation (s_h,a_h) in definition 8b confusing. Possibly it would be easier to follow if it would be stated explicitly after the equation that \\tau = ( s_1,a_1,.., s_H,a_H).\n3) As the authors stated, solving line 9 in algorithm 1 seems hard. Then, under additional assumptions, a computationally efficient algorithm is suggested. I believe that writing in line 10 in the abstract that the algorithm is computationally efficient is a bit misleading (further assumptions should be made to make the algorithm computationally efficient).\n4) The table of content in appendix contains the sections of the main paper. \n\n-) Typos.\nLine 853, \"and\" -> \"and any\".", "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": ["I don’t know"], "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "eQN26rRZy6A", "reviewer": "Reviewer_s9t9", "summary": "The paper studies a variant of the classical RL problem in which, instead of having a reward function depending on the state-action pairs, a reward function depending on the whole trajectory is considered. The rationale behind this choice is that, in some problems, the reward of the whole trajectory is revealed at the end only. After having formalized the setting, considering a binary reward governed by a logistic model, a first algorithm is proposed achieving sublinear regret for the case of finite states and actions. To overcome some limitations of the first algorithm (in particular the complexity in computing the optimal policy at every iteration), a second algorithm is presented, working under additional assumptions and achieving sublinear (although higher) regret. Finally, a small experiment is provided.", "questions": "", "limitations": "", "rating": 5, "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": "- Assumption 2.2: This assumption requires that the weights w_{\\star} are bounded in L2-norm by a finite constant B. As a consequence, from Assumption 2.1 and given that the features \\phi are bounded, the reward function must be a stochastic mapping from trajectories to {0,1} (that is, there always exists a non-zero probability that every trajectory is rewarded with either 0 or 1). What if the mapping between trajectories and reward were deterministic?\n- Section 3.1 and 3.2: The authors claim in Section 3.2 that Algorithm 1 could not be computationally efficient since finding the optimistic policy might be difficult. The optimistic policy is, in general, a non-Markovian policy. Did the author provide a (maybe intractable) algorithm to compute it?\n- Assumption 3.4: I couldn't grasp the intuition behind this assumption. The first condition seems a form of \"orthogonality\" between the features at different steps h and h'. Can the authors elaborate more on this assumption, possibly adding some explanation in the paper? \n- If I understood well, the problem with Algorithm 1 is the possible intractability in the computation of the optimistic (non-Markovian) policy. Requiring that the rewards are Markovian, as in Assumption 3.3, wouldn't already solve the problem? With Markovian rewards, the optimal policy is Markovian and I guess that the computation of the optimistic policy becomes tractable (you can use extended value iteration, for instance). I haven't understood the intuition behind the need for computing the exploration mixture policy. I would appreciate if the authors could explain this point in more detail. \n- The experiment seems detached from the rest of the paper. The only contact point is that the considered environment is non-Markovian. Indeed, the algorithms presented in the paper are not employed in the experiment (that uses policy gradient methods). What is the point of the experiment?\n- Concerning the related works, in [1], a similar setting is considered in which an optimization over the parameters of the policy is carried out, also achieving sublinear guarantees on the reget. The formulation is trajectory-based and actually does not need to observe the reward for the individual steps but just the trajectory return.\n- I haven't checked the appendix.\n\n***Minor***\n- Line 56: Section E - > Appendix E\n- Section 2.2: Since a finite-horizon MDP is considered, for the general case, the transition model P(\\cdot|s,a) should depend on the step h too. The fact that it is independent of h is a requirement for the presented algorithm? Considering P_h(\\cdot|s,a) would require changes in the analysis? In particular, would this affect the regret in Theorem 3.2?\n- Section 2.2: The paper assumes that the initial state distribution \\rho is known to the learner. What if it were unknown?\n- Equation 4: The confidence bound \\rho_t makes confusion with the initial state distribution \\rho. I suggest changing the symbol.\n- Line 145: hasn't been - > has not been\n- Algorithm 1 and 3, line 2: Shouldn't \\hat{\\mathbb{P}}_1 be initialized as uniform?\n\n***Overall***\nI think that the paper contains interesting ideas. However, I have some concerns about some of the presented assumptions. I will opt for a borderline score, although I am willing to adjust my score based on the author's response.\n\n[1] Papini, Matteo, Alberto Maria Metelli, Lorenzo Lupo, and Marcello Restelli. \"Optimistic policy optimization via multiple importance sampling.\" In International Conference on Machine Learning, pp. 4989-4999. PMLR, 2019.\n\n***Post Discussion***\nI thank the authors for the feedback. I read the reviews and the author's feedback. Although the once-per-episode feedback is an interesting setting, I found some choices of the formulation unmotivated; in particular, the fact that the episode reward can be just 0 or 1 and that cannot be deterministic. These assumptions are motivated by the analysis but seem not to be related to the nature of the problem. So, I remain inclined towards rejection.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is mainly theoretical, thus I do not forsee any societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "FZ_H0s8pVMX", "reviewer": "Reviewer_LW3y", "summary": "The authors consider the setting of reinforcement learning where the agent is provided with binary rewards with reward-probabilities determined by a logistic linear model. Unlike usual, the reward applies to the entire trajectory. The authors assume features to be available to the agent. The first algorithm proposed by the authors combines bounds on logistic bandits and bounds on model learning to learn an optimistic approximation of the reward which, if optimized with an unspecified algorithm, provides a sqrt(N) regret bound. In the second algorithm, the authors propose an approach to optimize said reward under additional assumptions on the structure of the trajectory features to obtain a N^2/3 regret bound. \n", "questions": "", "limitations": "", "rating": 4, "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 paper is well-written and easy to read. The problem studied in this work is relevant to a variety of practical applications. \n\nIn its most general form, as specified in Section 3, the algorithm and its accompanying regret bound depends entirely on finding the optimal trajectory given the learned reward function. In a sense, this simply defers the problem: the algorithm as written provides the framework for incorporating optimism in a way that is necessary to learn from learned rewards, but the solution of the reinforcement learning problem with once-per-episode feedback is left open. The best use-case of this framework is perhaps practical: learn a reward function with uncertainty bonus as defined in the algorithm, then use the learned bonus to solve the problem with episodic algorithms such as reward-weighted regression or ES; however, with the strong assumptions on the structure of the state-action space and the true reward function, it is unclear how much of a boon the derived bonus would give in practice and without specifying the algorithm fully, the given bound cannot actually be obtained in any scenario.\n\nIn Section 4, the authors aim to address this problem by providing an approach to iteratively decompose the reward into a per-step reward, to be optimized by an RL algorithm with theoretical guarantees. The issue here is that the additional assumptions made are highly restrictive: Assumption 3.3 says the features decompose additively, similar to the way in which successor states/features operate (a citation would be appropriate here). Assumption 3.4 goes further and defines features to be orthogonal to each other. With this assumption, the features cannot do any summarization of the trajectories anymore and instead fully characterize the state-action-distribution. This allows the authors to maximize the trajectory features in a desired direction and to specify the remainder of the algorithm.\n\nThe experimental section of this paper is puzzling, no comparison between algorithms is made and no empirical evaluation of the proposed algorithms seems to be present. It is unclear if the proposed algorithm is even used. Instead, it seems that the experiment serves only as a demonstration that REINFORCE is able to solve some arbitrary MDP with per-episode rewards. Clearly this is known.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewer were overall ambivalous about this paper, even after rebuttal and discussion.

The reviewers agreed that the proposed model is new, interesting, and that the authors provide the first regret bound for this formulation.

However, they were also concerned by a number of aspects of this work:
* several assumptions seem unnatural and are hard to verify without extensive discussion as of their meaning (e.g., the kappa parameter or the decomposability assumption)
* some choices of the formulation unmotivated (beyond being required in the analysis) and not properly explained in the rebuttal (eg, the nature of the reward)
* Alg 1 is intractable, the complexity of Alg 2 is still unclear after rebuttal (while the regret dependency to the number of episode is quite bad), and the Alg in the experimental section has little to see to the previous ones.

I think that a revision addressing these points would require another round of review, and therefore recommend rejecting this paper. 
Decision: Accept (Poster)