Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback

Thank you for your constructive review. Below is our response to your comments and questions.

Aside from the innovation of U-function and corresponding performance difference lemma, are there other technical innovations that might be independent interest?

Major contributions of our work:
The key novelty lies in the introduction of the U-function, which is easy to estimate under aggregate bandit feedback, and the regret decomposition with respect to it. This contrasts with previous approaches that directly tried to estimate the loss function, inducing several challenges under aggregate bandit feedback such as controlling the estimation bias—this results in a relatively complex algorithm and technical analysis. We believe that the U-function is an interesting concept that elegantly circumvents previous technical challenges and results in an intuitive and simple technical analysis. We believe that this new concept could be insightful for future research on RL with aggregate bandit feedback.

The removal of dilated bonuses may sound hand-waving... It'd be good to refer the readers to (Lancewicki et al., ICML'23)...

Thank you for your suggestion - we will add a reference to Lancewicki et al. (2023) and discuss the technical differences from Luo et al. (2021).

Thank you for the positive review and the great questions. We would be happy to discuss any of the points below in the final version that the reviewer believes will improve the paper.

Q1: Indeed, our bounds are specific to the PO framework. The only 'occupancy measure + FTRL/OMD' algorithm for aggregate bandit feedback (ABF) is by Cohen et al. (2021b), where it is still unclear how to improve them using the occupancy measure approach. Given the regret structure in terms of occupancy measures, it is natural to attempt estimating the loss function itself; however, handling estimation bias under unknown dynamics is quite challenging since the learner does not precisely know the played occupancy measure. Under known dynamics, it might be possible to achieve the optimal bound using 'occupancy measure + FTRL/OMD'. While the optimal bound for linear bandits over general convex sets is $d\sqrt{T}$, in some special cases, such as the simplex, it is possible to achieve tighter bounds. Therefore, there may be room to improve the bounds for the set of occupancy measures. This is an important and interesting open challenge for future research.

Q2: Yes, the key novelty lies in the introduction of the U-function, which is easy to estimate under aggregate bandit feedback, and the regret decomposition with respect to it.

Q3: No, in fact, one does not need the dilated component of Luo et al., 2021 (i.e., the $(1+\frac{1}{H})$ factor in the backup operator), even in the semi-bandit case. For prior evidence, see [1].

[1] Lancewicki, T., Rosenberg, A., & Sotnikov, D. "Delay-adapted policy optimization and improved regret for adversarial MDP with delayed bandit feedback." ICML 2023

Q4: That is a great question. The challenge in improving the lower bound under unknown dynamics is that ABF is not less informative about the dynamics, since the agent still observes the transitions. Thus, unlike in the semi-bandit case, under ABF it remains unclear whether unknown dynamics make the problem statistically harder.

Q5: In the known dynamics case, full-bandit feedback is in fact statistically harder than semi-bandit feedback—the optimal bound in the semi-bandit case is $H \sqrt{SAK}$, and our lower bound for the full-bandit case is $H^2 \sqrt{SAK}$. As for the known dynamics case, it remains highly unclear, partly because the optimal bound in the semi-bandit case is also an open question. Under semi-bandit and unknown transitions, the best known upper bound is $H^2 S \sqrt{AK}$ (Jin et al., 2020), while the best known lower bound is $\Omega(H^{3/2} \sqrt{SAK})$ (Jin et al., 2018). If the latter is optimal under semi-bandit, then due to our lower bound, ABF is statistically harder. We also conjecture that the $H^2$ dependency in our lower bound is optimal and that the extra $H$ in our upper bound is an artifact of the PO method (as PO currently has this artifact in the semi-bandit case). If this conjecture is true, and if $H^2 S \sqrt{AK}$ is optimal under semi-bandit, then full-bandit would statistically be as easy as semi-bandit.

Thank you for the positive and constructive review. Below is our response to your comments and questions.

despite the paper’s theoretical focus, it would be interesting to include some experimental demonstrations of the U-functions in practice.

Our work is theoretically focused. Previous theoretical work has taken a more direct approach and faced challenges such as directly estimating the loss function and controlling the estimation bias in the regret bound. In our work, we introduce the concept of U-functions, which allows us to circumvent these challenges and handle aggregate bandit feedback much more elegantly. We hope this new concept will be insightful for future research, particularly for empirical studies and more practical applications. However, we believe that tabular MDPs would not be a good framework for demonstrating the practical applications of the U-function. Instead, an extensive empirical study that incorporates the U-function into a practical deep RL method, tested under a well-chosen set of benchmarks with large state spaces, would be more appropriate. We believe that this is an important area for future research and will include it in the future work section.

…for the case with known dynamics… I wonder if a similar result could also be obtained without the exploration bonuses (as here the dynamics are known), using similar results as the Appendix B.3 from Jin et al 2020.

Jin et al. 2020 employs an occupancy-measure-based algorithm where, indeed, one does not need to incorporate bonuses in the known dynamics case. On the other hand, in the Policy Optimization method, it is not clear how to achieve $\sqrt{K}$ bounds without an exploration bonus. As mentioned in the paragraph starting at line 240, the purpose of the bonus in the known dynamics case is to address the distribution mismatch between $\mu^\star(s)$ and $\mu^k(s)$ that appears in the regret bound (e.g., line 294, right column). This distribution mismatch is rather orthogonal from the additional challenges in the unknown dynamics case, and stems mainly from the fact that the value difference lemma breaks the regret over states with weights $\mu^\star(s)$, and that we run the OMD locally in each state (unlike the method in Jin et al. 2020, which is the framework that Cohen et al. (2021b) builds upon).

Thank you for the positive and constructive review. Below is our response to your comments and questions.

I think that the bonus b(s) should not have π in the denominator (see, for example, the analysis in line 684)

Note that in line 684 the denominator has $\mu_h^k (s,a)$ which is by definition $\mu_h^k (s) \pi_h^k (a \mid s)$ (as in the bonus).

Line 695: The variance term must contain E[Yk], since the martingale difference is Yk−E[Yk]. However, I believe that such minor errors across the analysis do not change the complexity results of the paper.

Thank you for spotting that. This is indeed not a proper use of Lemma E.2 but has a simple fix: for the martingale difference, $|Y_k - \mathbb{E}[Y_k]| \leq \max(Y_k, \mathbb{E}[Y_k]) \leq \frac{H^2}{\gamma}$, and the variance is bounded by the second moment: $\mathbb{E}[(|Y_k - \mathbb{E}[Y_k]|)^2] \leq \mathbb{E}[Y_k^2]$. We will correct this in the final version in line 695 and also in line 990 (which has the same minor error).

(Line 326) Can the authors provide indicative works where the Bernstein sets are used?

Yes, in the context of Policy Optimization see for example Shani et al. (2020); Luo et al. (2021). But it is also widely used in other types of algorithms such as in occupancy-measure-based algorithms (Jin et al., 2020) and FTPL (Dai et al., 2020). We will reference those in line 326.

Dai, Yan, Haipeng Luo, and Liyu Chen. "Follow-the-perturbed-leader for adversarial markov decision processes with bandit feedback."

Can the authors provide the time complexity of the proposed algorithms?

For the known dynamics case, the state occupancy measure can be computed using the following recursive formula: $\mu_{h+1}^{\pi}(s') = \sum_{s,a} \mu_{h}^{\pi}(s) \pi_{h}(a \mid s) P(s' \mid s,a)$, so that the full occupancy measure can be computed in $O(H S^2 A)$. The bonus $B$ is calculated via backward dynamic programming also in $O(H S^2 A)$, and the policy computation is done in $O(H S A)$. Thus, the total complexity per iteration is $O(H S^2 A)$.

For the unknown dynamics case, the upper/lower confidence occupancy measure computation can be done using Algorithm 3 in (Jin et al., 2020), with a complexity of $O(H S^2 A)$ per state. The same can be done for the computation of the bonus $\hat{B}$.

We will include these details in the final version.

In the unknown dynamics setting, how does Algorithm 2 compute μ? What is the time complexity per episode for these steps?

See above.

Have the authors tried a model-free approach?

To the best of our knowledge, all existing regret minimization algorithms for MDPs with non-stochastic losses are model-based, even in the semi-bandit case. Achieving sub-linear regret under non-stochastic losses using a model-free algorithm is a very interesting future direction, already in the simpler context of semi-bandit feedback.