Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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. 

main_review: - The related work section can be strengthened. The difference and novelty of the results should be better highlighted. 
- 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. 
- 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. 

limitations_and_societal_impact: The paper needs improvement in motivation, related work, and also the presentation of the technical contents.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

Pros:
1. It studied an important problem, proposed a (computationally inefficient) algorithm with strong statistical guarantees.

Cons 
1. 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. 
2. 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?
3. 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. 
limitations_and_societal_impact: See main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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:

How to know omega? The authors may consider the tabular setting for simplicity. 

Two comments/questions:

The 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.

Why 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. 

[Update]
After 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.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: ## Quality and Clarity
The 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.

## Originality and Significance

1. 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].  

2. 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.


## Comments and Questions:

* 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?

* Why does the optimization problem in eq. 3 use L2 regularization and not shannon-entropy? It seems more natural with the cross-entropy loss.

* 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.
limitations_and_societal_impact: n/a
review_title: null

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)