Reinforcement Learning with Segment Feedback

Thank you very much for your recognition of our work and insightful questions! We have revised our paper according to your comments, and highlighted the revised concent in purple font.

Response to Questions

1. The Implication of $\nu(k)$

With high probability, we have $|\phi^\top \theta^* - \phi^\top \hat{\theta}_k| \leq \sqrt{\alpha} \cdot \nu(k) \cdot$

$\\|\phi\\|_{\Sigma_k^{-1}} ,$

where $\theta^*$ is the true reward parameter, $\hat{\theta}_k$ is the MLE estimate, and $\phi$ is the visitation indicator of a trajectory. Thus, $\nu(k)$ is part of the bound for the error between the estimated reward and the true reward for a trajectory. (There is a break in the formula due to the formula display issue of OpenReview.)

2. Theorem 1

In Theorem 1, the regret bound contains a factor $\exp(\frac{H r_{\max}}{2m})$, which usually dominates the bound. Thus, when the number of segments $m$ increases, the regret bound decreases at an exponential rate. Therefore, under binary feedback, increasing the number of segments helps accelerate learning.

3. The Sigmoid Function's Derivative

Intuitively, we want to distinguish between "good" actions (which give high rewards) and "bad" actions (which give low rewards) from binary feedback, which is generated by the sigmoid function $\mu(x)=\frac{1}{1+\exp(-x)}$. If the binary feedback is generated from the range where the sigmoid function is flat, i.e., the derivative of the sigmoid function $\mu'(x)$ is small, then the generated binary feedback is likely always $0$ or always $1$, and it is hard to distinguish between a "good" action and a "bad" action, leading to a higher regret. On the contrary, if the binary feedback is generated from the range where the sigmoid function is steep, i.e., the derivative of the sigmoid function $\mu'(x)$ is large, then the generated binary feedback is more dispersed and will not always be $0$ or $1$, and it is easier to distinguish between a good action and a bad action, leading to a lower regret. Therefore, the regret bound depends on the inverse of the sigmoid function's derivative.

4. Theorem 4

We meant that in Theorem 4 (the sum feedback setting), as the number of segments $m$ increases, the regret bound does not decrease at a polynomial rate as one might expect, e.g., $\frac{1}{m}$ or $\frac{1}{\sqrt{m}}$, which is a little surprising, because larger $m$ means more observations.

Yes, since $m$ influences the regret bound by a multiplicative constant of the form $\log(1+\frac{H}{m})$, it is not a critical factor affecting the regret bound in Theorem 4.

Dear Author,

Thank you for the comments. Answers are reasonable and all of my concerns are addressed. I will keep my score and the confidence. Thanks!

Best, Reviewer

Thank you very much for your time and effort in reviewing our paper! We have revised our paper according to your comments, and highlighted the revised concent in blue font.

Response to Weaknesses

1. Prior Work [1] on Segments

Thank you for suggesting this reference! We were not familiar with [1] before. We acknowledge that [1] proposed the setting of RL with segment feedback earlier, and have cited and discussed [1] in our revision.

However, we would like to highlight the differences between our work and [1] below.

• Prior work [1] is mostly an empirical work. They design an algorithm based on transformers, and do not present any theoretical guarantee except a theorem proving that the optimal policies for MDPs with segment feedback align with those for standard MDPs. Different from [1], our work is mostly a theoretical RL work. We focus more on providing theoretical analysis to show how the number of segments $m$ influences learning performance. We design provably efficient algorithms, and establish rigorous regret upper and lower bounds for our algorithms and the problem itself, respectively.
• Prior work [1] only considers the sum reward feedback type, while we consider both the sum and binary reward feedback types. Binary reward feedback is more suitable for scenarios involving human feedback. For example, in autonomous driving, it is easier for humans to provide feedback on whether a driving segment is good than giving a score. We also design algorithms and present theoretical results to show that under binary feedback, as $m$ increases, the regret decreases at an exponential rate.
• Our work contributes new techniques. We use E-optimal experimental design to perform an initial exploration in our algorithm, which enables us to improve the result in prior trajectory feedback work [3]. We also develop a novel lower bound analysis for binary feedback, based on the KL divergence of Bernoulli distributions with the sigmoid function as parameters. Our techniques can be of independent interests, and applied to other related RL problems.

2. The Setting of Equal Length

We agree with the reviewer that considering segments of unequal lengths is more general and an interesting future direction, which was also mentioned in our future work section. However, we would like to highlight that studying segments of equal lengths is an important starting point and serves as a foundation for further investigation, especially for theoretical analysis. We believe that our result that segments help in the case of binary feedback and do not help in the case of sum feedback is quite surprising and not known previously.

Note that studying segments of equal lengths is already very challenging, due to the following reasons:

• This problem cannot be solved by simply adapting prior trajectory feedback works, e.g., [Efroni et al., AAAI 2021], because they use the martingale property of subsequent trajectories, while subsequent segments are not a martingale due to the dependence among segments within a trajectory.
• For sum feedback, there was a gap between existing upper and lower bounds for RL with trajectory feedback [Efroni et al., AAAI 2021]. So one cannot infer that segments would not help significantly in the sum feedback case (our result) from prior works.
• For binary feedback, there is no known lower bound to indicate that the exponential factor in the regret bound is inevitable.

Our paper has made a number of technical contributions to overcome these challenges.

3. Advantages and Innovation of Algorithm SegBiTS

The advantage of our SegBiTS algorithm compared to [2] is in computation. Algorithm "UCBVI with trajectory labels" [2] is computationally inefficient due to its confidence interval term. While [2] also provides another computationally-efficient algorithm called "UCBVI with trajectory labels and added exploration", this algorithm has a worse regret bound dependent on $K^{\frac{2}{3}}$, where $K$ is the number of episodes. In contrast, our SegBiTS algorithm is computationally efficient and easy to implement, and has a regret bound dependent on $\sqrt{K}$.

SegBiTS adopts the maximum likelihood estimator for binary feedback under the Thompson sampling framework. Its analysis is highly non-trivial. In the analysis, we decompose the regret into the error due to reward parameter estimation and the error due to sampled Gaussian noises, and carefully choose the conditional expectation to ensure the independence between sampled Gaussian noises and segment visitation indicators.

We would like to also note that our novelty in the binary feedback setting also includes a new lower bound (Theorem 2) to demonstrate the inevitability of the exponential factor $\exp(\frac{H r_{\max}}{m})$ in the regret bound. This lower bound is novel and, to the best of our knowledge, not known previously.

4. Advantages of Our Algorithms and Experiments

(1) Advantages of Our Algorithms

We would like to highlight that it is not straightforward to extend trajectory feedback algorithms to the segment feedback setting, especially for attaining theoretical results that clearly show the influence of the number of segments $m$ on learning performance. The challenges and the advantages of our algorithms include:

• At a high level, trajectory feedback algorithms cannot be directly used in the case of segment feedback, because segments are strongly correlated and do not lead to a martingale as in the trajectory feedback case. Therefore, learning algorithms in the case of segment feedback have to be carefully designed to account for this correlation.
• For sum feedback, prior trajectory feedback algorithm [3] is not optimal. To tackle this challenge, we design an algorithm E-LinUCB, which adopts E-optimal experimental design to sharpen the norm of visitation indicator $\\|\phi^{\tau}\\|$, and achieves an optimal regret bound with respect to $m$ and the length of each episode $H$. Our result improves on [3] when the problem degenerates to trajectory feedback, and reveals the optimal dependence on $m$ in the regret bound.
• For binary feedback, prior trajectory feedback algorithms [2] are either computationally inefficient or have an $O(K^{\frac{2}{3}})$ regret bound, where $K$ is the number of episodes. To handle this challenge, we develop algorithm SegBiTS, which incorporates the maximum likelihood estimator for binary feedback into the Thompson sampling framework. SegBiTS is both computationally efficient and has an $O(\sqrt{K})$ regret bound. We also carefully handle the error brought by such incorporation in analysis, e.g., using a variance-adaptive concentration analysis to bound the reward estimation error and choosing the appropriate conditional expectation to bound the error due to sampled Gaussian noises.

(2) Experiments to Compare with [2, 3]

Thank you for your suggestion on experiments. We ran preliminary experiments to compare our algorithms with the adaptations of prior trajectory feedback algorithms [2, 3] to the segment setting.

Since algorithm “UCBVI with trajectory labels” in [3] is computationally inefficient, in experiments, we use a small MDP with $|\mathcal{S}|=3$ and $|\mathcal{A}|=5$, and set $r_{\max}=0.5$, $\delta=0.005$ and $m \in \\{1,2,H\\}$. In the binary feedback setting, we set $H=6$ and $K=1000$, and in the sum feedback setting, we set $H=10$ and $K=5000$ (because ``UCBVI with trajectory labels" is slow for large $H$ and $K$). We perform $15$ independent runs for each algorithm, and present the average cumulative regret up to episode $K$, the standard deviation of the regret and running time across runs.

From the tables, we see that under binary feedback, while our algorithm SegBiTS has a slightly higher regret than the adaptation of algorithm “UCBVI with trajectory labels” [3], SegBiTS attains a significantly lower running time than the adaptation of ``UCBVI with trajectory labels", which demonstrates the computation efficiency of SegBiTS. Under sum feedback, our algorithm E-LinUCB achieves a lower regret than OFUL [2], which validates the effectiveness of its experimental design technique.

We will include experiments with more independent runs in the revision once they finish.

Response to Weaknesses

Thank you very much for your time and effort in reviewing our paper! We have revised our paper according to your comments, and highlighted the revised concent in red font.

1. Unclear Regret Bound

We would like to clarify that we used $\nu(K)$ in Theorem 1 just to keep the presentation of equations concise. Actually, such notation was also used in many prior logistic bandit works, e.g.,~[Faury et al., 2020; Russac et al., 2021], and we just followed their notation.

However, we agree with the reviewer that a complete regret bound will make the result clearer. We present the complete regret bound as follows, and have included it in our revision.

The dependence on $|\mathcal{S}|$, $|\mathcal{A}|$, $H$ in this regret bound are $|\mathcal{S}|^3$, $|\mathcal{A}|^3$, $\exp(\frac{H r_{\max}}{2m}) H^2$, respectively. Our focus was not on the polynomial factors; our main goal was to show the exponential dependence that arises due to binary segment feedback and, in this case, we note that we provide a lower bound that is also exponential (Theorem 2).

2. The Setting of Equal Length

We agree with the reviewer that considering segments of unequal lengths is more general and an interesting future direction, which was also mentioned in our future work section. However, we would like to highlight that studying segments of equal lengths is an important starting point and serves as a foundation for further investigation, especially for theoretical analysis. We believe that our result that segments help in the case of binary feedback and do not help in the case of sum feedback is quite surprising and not known previously.

Note that studying segments of equal lengths is already very challenging, due to the following reasons:

• This problem cannot be solved by simply adapting prior trajectory feedback works, e.g., [Efroni et al., AAAI 2021], because they use the martingale property of subsequent trajectories, while subsequent segments are not a martingale due to the dependence among segments within a trajectory.
• For sum feedback, there was a gap between existing upper and lower bounds for RL with trajectory feedback [Efroni et al., AAAI 2021]. So one cannot infer that segments would not help significantly in the sum feedback case (our result) from prior works.
• For binary feedback, there is no known lower bound to indicate that the exponential factor in the regret bound is inevitable.

Our paper has made a number of technical contributions to overcome these challenges.

Response to Questions

1. The Case $r_{max}>1$

Thank you for raising this question. Our algorithms and results also work for $r_{\max}>1$. We have revised $r_{\max}\in(0,1]$ to $r_{\max}>0$ in our updated version.

2. The Difference between the Two Feedback Types

(i) The reward estimation methods under the sum feedback and binary feedback are different. In the sum reward feedback setting, we mainly use the least square estimator to estimate the reward parameter, and the confidence interval is a confidence ellipsoid related to the variances of noises. In contrast, in the binary reward feedback setting, we use the maximum likelihood estimator to estimate the reward parameter, and the confidence interval is a confidence ellipsoid, related to not only the variances of noises but also the derivative of the sigmoid function. (ii) The analyses needed for these two feedback types are different. In the sum reward feedback setting, we mainly use the concentration analysis of least squares to bound the reward estimation error; In the binary reward setting, we use a more complex variance-adaptive concentration analysis and the self-concordance property of the sigmoid function's derivative to handle the reward estimation error.

We do not think that the binary reward feedback setting can be trivially solved by running the algorithm for sum reward feedback for $\exp(\frac{H r_{\max}}{m})$ times. An immediate reason is that the least squares estimator and confidence interval construction in the algorithm for sum reward feedback cannot directly handle binary reward feedback, and the analysis of the algorithm for sum reward feedback also cannot give a reward estimation concentration guarantee for binary reward feedback.