Reinforcement Learning with Segment Feedback

Thank you for your time in reviewing our paper! We will revise our paper according to your comments.

1. Determine the Feedback Type

We assume an MDP setting, so the sum of step-level rewards being the trajectory reward is natural. Given this model, we can ask a human to give a score to a trajectory, which is an approximation to the sum feedback and has been considered in prior works cited in our paper. Or we can ask for thumbs up/down feedback which is the binary feedback model. So we believe that in our context, it is reasonable to assume that the type of feedback is known ahead of time since the type of feedback is designed by us.

2. Assumption on Equal-Length Segments

We agree with the reviewer that in practice, the segment length may be unequal. However, studying segments of equal length is an important starting point which has uncovered non-trivial challenges, and we reveal a new and surprising result: segments help under binary feedback, but do not help much under sum feedback.

We believe that our algorithms and analysis can be extended to segments of variable length. For example, a natural extension is to consider that the arrival of reward feedback follows a point process. In this case, the variable segment length will affect the noise variance of reward feedback, and the sum analysis of segment visitation indicators. One idea to handle this case is to obtain high probability bounds of the segment length and the number of segments within a trajectory, and use these bounds in our analysis.

3. Experimental Comparison

We ran preliminary experiments to compare our algorithms with the adaptations of trajectory feedback algorithms [1, 2] (reviewer's reference numbers) to the segment setting.

In our experiments, we set $|\mathcal{A}|=5$, $r_{\max}=0.5$, $\delta=0.005$ and $m=2$. In the binary feedback setting, we set $|\mathcal{S}|=5$, $H=6$ and $K=1000$. In the sum feedback setting, we set $|\mathcal{S}|=3$, $H=10$ and $K=5000$. For each algorithm, we performed $15$ independent runs and presented the average regret with standard deviation, and average running time across runs.

As shown in the tables, under binary feedback, while our algorithm SegBiTS has a slightly higher regret than the adaptation of "UCBVI with trajectory labels" [1], SegBiTS achieves a significantly faster running time, since SegBiTS is computationally efficient while "UCBVI with trajectory labels" is not. Under sum feedback, our algorithm E-LinUCB attains a lower regret than the adaptation of OFUL [2], since E-LinUCB employs the experimental design technique to sharpen the regret.

The experimental results for $m\in\\{1,H\\}$ are similar. Here we only present the results for $m=2$ due to space limit. We will include more experiments in our revision.

4. Reviewer's Reference [2] ("Harnessing ...")

The problem and focus in [2] are very different from ours. [2] considers RL with bagged decision times, where the state transitions are non-Markovian within a bag, and a reward is observed at the end of the bag. This problem can be regarded as a periodic MDP with non-stationary state transitions and reward functions in a period, and [2] adapts an RL algorithm for standard stationary MDPs to this periodic MDP to solve this problem. The focus of [2] is to handle the non-Markovian state transitions within a bag using a causal directed acyclic graph, instead of investigating bagged rewards. [2] does not consider how to infer the reward function of state-action pairs from bagged rewards, or study how the frequency of reward feedback impacts learning performance like us.

We will cite [2] and include this discussion in our revision.

5. Structural Assumptions

We assume an MDP model, which is widely used in reinforcement learning. In the MDP model, the reward of any segment of any trajectory is the sum of the rewards of each individual step in the segment. So the type of reward aggregation is fixed by our MDP model. And for binary feedback, we assume that it is generated according to a sigmoid function, which is also widely accepted and used. Beyond these two assumptions, we didn't make any other structural assumptions. To the best of our knowledge, the fact that one gets extremely coarse information about the sum reward in the binary feedback case makes it impossible to have a common analytical technique for both feedback models.

Thank you for your time and effort in reviewing our paper! We will certainly incorporate your comments in our revision.

1. Comparison with [Chatterji et al., 2021] in Formulation

The objectives in [Chatterji et al., 2021] and our paper are different. In [Chatterji et al., 2021], the goal is to choose a policy which maximizes the probability of a trajectory getting a rating of $1$, i.e., getting positive feedback. Whereas, in our model, our goal is to maximize the expected sum of rewards over trajectories. In our opinion, both models have value and are applicable in different contexts. In particular, our model is better suited to situations where we want to solve an MDP but only get binary segment feedback.

Reference:

Chatterji et al. On the theory of reinforcement learning with once-per-episode feedback. NeurIPS, 2021.

Thank you for your time and effort in reviewing our paper! We will certainly incorporate your suggestions in our revision.

1. More Experiments

This is an excellent suggestion. However, it is difficult to perform experiments on the Atari environments before the rebuttal deadline since it would take some time to adapt our discrete state-space setting to Atari's continuous state space setting of images. However, following the reviewer's suggestion, we ran preliminary experiments on a more complex Grid World environment called Cliff Walking, which is used in the popular RL textbook [Sutton & Barto, 2018].

The above table depicts the Cliff Walking environment considered in our experiments. Each table cell denotes a state. An agent starts from the left bottom state (marked as "start") and aims to arrive at the right bottom state (marked as "end"). The reward of each state is marked in the bracket $(\cdot)$ in the state. The states with $\otimes$ denote a cliff and generate negative rewards $-r_{\max}$. The optimal path is the path close to the cliff, and the path close to the upper wall is suboptimal. In our experiments, $|\mathcal{S}|=18$, $|\mathcal{A}|=4$, $H=8$, $m\in\\{1,4,8\\}$, $K=50000$, $r_{\max}=2$ and $\delta=0.005$. We performed our algorithm SegBiTS for $3$ independent runs under binary segment feedback, and reported the average regret with standard deviation to see how the number of segments $m$ impacts learning performance.

As shown in the table, under binary feedback, as the number of segments $m$ increases, the regret significantly decreases, which matches our theoretical finding.

Due to time limit, here we only present the results for this instance and binary segment feedback. We will include more experimental results on larger instances in our revision.

Reference:

Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An introduction. 2018.

2. Non-tabular Settings

Yes, we expect that similar results will hold in non-tabular settings, e.g., linear function approximation. In the linear function approximation setting, it is assumed that each state-action pair is associated with a feature vector $\phi(s,a) \in \mathbb{R}^d$, there exists a global reward parameter $\theta^* \in \mathbb{R}^d$, and segment reward feedback is generated according to $(\sum_{h \in \mathcal{H}} \phi(s_h,a_h))^\top \theta^*$, where $\mathcal{H}$ denotes the set of step indices in a segment. Since our analytical procedure is mainly based on visitation indicators $\phi(s,a)$ and the fact that segment reward feedback is generated linearly with respect to $\phi(s,a)$, we believe that generalizing $\phi(s,a)$ from a visitation indicator in the tabular setting to a feature vector in the linear function approximation setting should be possible. We will further investigate non-tabular settings in our future work.