acceptodds
Under review as a conference paper at ICLR 2027

Best-of-both-worlds Policy Optimization for Heavy-tailed Markov Decision Processes

Abstract

We study finite-horizon tabular Markov decision processes (MDPs) with heavy-tailed loss functions (i.e., every one-step loss is assumed only to have a bounded -th raw moment for a known ). Previously, *best-of-both-worlds* (BOBW) guarantee for this problem has only been achieved by Chen et al. (2026) using an *occupancy measure* (OM)-based algorithm. In this work, we develop a *policy optimization* (PO)-based approach, which is preferable to OM-based approaches in practice because PO updates the policy locally at each state and does not require solving a global optimization problem. In addition to the computational advantage, for known transitions, the heavy-tail terms in our regret bounds improve upon those of Chen et al. (2026) by factors of and in the adversarial and stochastic regimes, respectively, where and denote the sizes of the state and action spaces. For unknown transitions, our method does *not* require the truncated non-negativity assumption imposed by Chen et al. (2026); moreover, our heavy-tail terms are smaller by factors of and in the adversarial and stochastic regimes, respectively, where denotes the number of episodes.

Primary area:
learning theory
Keywords:
Reinforcement Learning, Best-of-Both-Worlds, Policy Optimization, Heavy-Tailed Losses

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_jQUjOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies the problem of Best Of Both Worlds (BOBW) guarantees for MDPs with heavy-tailed losses (only finite moment less than or equal to 2), i.e., the loss distributions per round can either be fixed or chosen adversarially. This has previously been studied in a recent work by Chen et al. (2026). The authors' main contribution is to both improve the regret bounds (for both stochastic and adversarial settings) as well as to relax a truncated non-negativity assumption made by the previous paper. They also move to a policy optimization approach rather than an occupancy measure approach of the previous work.

Critical strengths
  • Impoved regret bounds for all settings (known/unknown transitions, and stochastic/adversarial losses) of an interesting and established problem.
  • Relaxing the truncated non-negativity assumption on the losses made by previous works.
Critical weaknesses

The main issue for me with this work is it's presentation and overall writing. While the problem is inherently complex, the authors should have made an effort to distill their key contributions and provide the reader with more insight on these key points. Instead the paper mostly describes the challenges with low details, and provides only boilerplate math in the actual analysis, deferring all informative details to the appendix.

I recognize the mathematical complexity of this problem, and how difficult it is to distill the key insights into human readable text/math. However, I believe this is a critical aspect of paper writing that cannot be overlooked.

Questions for authors

Could you narrow the presentation of the main text to focus either on a simpler setting (known transitions?) that still demonstrates the main techniques?

Can you cleanly connect to previous work analysis and then focus on the key points where your analysis differs and at least sketch how your approaches resolve the issues that arise?

4 comments
AuthorsOpenReview ↗

Response 1

We thank the reviewer for recognizing the significance of our results and our elimination of the truncated non-negativity assumption of previous work. Our response to each question is provided below.

Q1. "Instead the paper mostly describes the challenges with low details, ... to the appendix." "I recognize the mathematical complexity of this problem, ... cannot be overlooked." "Could you narrow the presentation of the main text to focus ... demonstrates the main techniques?"

We would like to thank the reviewer again for raising this suggestion, which we believe further improves the readability and the clarity of our paper.

We have now restructured our Section 3 to focus only on the algorithmic details for the known-transition setting (highlighted in orange). Further, we rewrote the part about the construction of our advantage function estimator and the centered clipping mechanism to provide more insights. In particular, we elaborate on why the canonical QQ-function estimator will make it difficult to achieve O(poly⁡(log⁡T))\mathcal{O}(\operatorname{poly}(\log T)) regret in the stochastic regime, and why our advantage function estimator can overcome this obstacle. We also provide a more accurate description of the intuition behind the design of our learning rate βt\beta_t. The discussion of these key insights is highlighted in red. We defer all the algorithmic details for the extension to the unknown-transition case to Appendices A.1-A.2 for better readability.

Q2. "Can you cleanly connect to previous work analysis ... resolve the issues that arise?"

Thanks again for this comment!

We have rewritten the proof sketch for our Theorem 4.1, which is now highlighted in orange and focuses only on the known-transition case. In particular, we now first invoke the global-to-local regret reduction lemma from previous works on policy optimization [1, 2] and then explain what the key differences and difficulties are and how we address them. We have further emphasized the insights underlying the key technical parts of our proofs and have tried our best to avoid going into too many low-level computational details. These key insights as well as the derivations associated with them are highlighted in red. The additional proof sketch for the unknown-transition case is deferred to Appendix A.3.


[1] Dann et al. Best of both worlds policy optimization. ICML, 23.

[2] Luo et al. Policy optimization in adversarial MDPs: Improved exploration via dilated bonuses. NeurIPS, 21.

Thank you for incorporating my suggestions.

  • The centered clipping explanation is very useful.
  • The rest of the proof sketches introduce 3 new pages, which are extremely math dense. I made a best effort to go over them given my time constraints. I found it somewhat hard to follow, though I am not sure how much this can be avoided.

Given that I could not fully go over the new 3 pages, I still have some reservations regarding acceptance. However, they are quite minor and I will not object to it.

Thank you for your positive feedback! We are glad to hear that our explanation of the centered clipping mechanism was helpful, and we appreciate the time you spent reviewing the additional proof sketches.

We agree that even the proof sketch for the known-transition case is a bit dense. Nevertheless, we would like to note that this is mainly due to the following two reasons:

  • First, although our algorithms build on the dilated-bonus policy optimization framework in [1,2], our approach to eliminating the dependence on the optimal action π⋆(s)\pi^\star(s) at each state ss differs from that in [1]. As mentioned, [1] achieves this through a sophisticated conditional “loss shifting” technique, whereas we achieve it directly through our advantage function estimator Q~t\widetilde{Q}_t and the carefully designed clipping threshold MtM_t. Thus, even without considering the effects of heavy-tailed noise, we believe this different approach to eliminating the dependence of the FTRL stability term on π⋆(s)\pi^\star(s) warrants an explanation. Providing that explanation takes a fair amount of space in the Bounding FTRL-Regretπ(s)\mathsf{FTRL\text{-}Regret}^\pi(s) paragraph of our proof sketch.
  • Second, heavy-tailed feedback introduces additional challenges. In particular, we need to explain how we control the signed bias rtr_t weighted by the comparator’s occupancy μπ\mu^\pi, which is the focus of the Bounding Estimator-Biasπ(s)\mathsf{Estimator\text{-}Bias}^\pi(s) paragraph. Moreover, since one of our motivations is to eliminate the truncated non-negativity assumption required in [3], we also devote space to explaining how we achieve this in the Bounding Clipping-Biasπ(s)\mathsf{Clipping\text{-}Bias}^\pi(s) paragraph.

Therefore, the proof sketch is indeed somewhat dense, but this was not intentional. Its density stems from the several new challenges posed by heavy-tailed noise and from the fact that, even without such noise, the key idea for eliminating the dependence on π⋆(s)\pi^\star(s) in our algorithm and analysis differs from that in [1] for studying BOBW PO for MDPs with bounded feedback. Our aim was to provide enough details to explain both the new challenges posed by heavy-tailed noise and the difference between our approach to eliminating the dependence on π⋆(s)\pi^\star(s) and that of [1].

We will include the above discussion in a future version of our paper to further clarify the role of each part of the proof sketch and help readers follow the main ideas more easily.


[1] Dann et al. Best of both worlds policy optimization. ICML, 23.

[2] Luo et al. Policy optimization in adversarial MDPs: Improved exploration via dilated bonuses. NeurIPS, 21.

[3] Chen et al. Best-of-both-worlds for heavy-tailed markov decision processes. ICML, 26.

Thank you for the additional clarifications. I understand the challenges. I will consider this positively in the post rebuttal discussion period.

Reviewer_sdnWOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies expected regret in finite-horizon tabular MDPs with fixed, known or unknown transitions and signed heavy-tailed losses, assuming a known moment bound Et∣Yt(s,a)∣ϵ≤σ\mathbb E_t|Y_t(s,a)|^\epsilon\le \sigma, 1<ϵ≤21<\epsilon\le2. Only losses along sampled trajectories are observed. Statewise Tsallis FTRL combines centered importance-weighted return estimates, clipping compensation, visitation-bias correction, dilated bonuses, and adaptive learning rates. Unknown transitions additionally require confidence sets and upper occupancy bounds. (Sections 2–4; Appendices B–C.)

Main results. Over TT episodes, both transition settings achieve O~(T1/ϵ)\widetilde O(T^{1/\epsilon})-type adversarial regret; unknown transitions incur an additional O~(T)\widetilde O(\sqrt T) estimation term. Positive-gap self-bounding conditions yield gap-dependent logarithmic fast rates for known transitions and polylogarithmic fast rates for unknown transitions, with corruption-dependent terms. These summaries suppress dimension dependence and substantial additive remainders.

Contributions.

  • Signed heavy-tail policy optimization. Explicit clipping and visitation-bias compensation remove the sign restriction imposed in the closest heavy-tail predecessor.
  • Analysis for unknown transitions. Fractional occupancy-count bounds and coordinatewise conversion from upper to true occupancy counts support the fast-rate analysis.
  • Improved principal bounds. The leading dimension dependence improves on the compared heavy-tail method; the bounded-loss comparison at ϵ=2\epsilon=2 is also supported. These are comparisons between stated upper bounds, subject to their remainder terms.
Critical strengths

The algorithmic designs for heavy-tailed loss are shown to yield a strong theoretical guarantee.

Critical weaknesses
  1. This paper lacks numerical evidence to support the claims.

  2. Full minimax optimality has not been reached for the theoretical results in the contribution.

Questions for authors

Mathematical correctness

  • Equation (21): The clipping-bias bound omits a factor of two; the subsequent inequality also requires an ϵ\epsilon-dependent constant rather than a unit constant.
  • Equation (24): The displayed statement omits an outer expectation and uses μπ⋆\mu^{\pi^\star} where the arbitrary-comparator statement requires μπ\mu^\pi.
  • Equation (25): The bound omits the loss-scale factor Lσ=σ1/ϵL_\sigma=\sigma^{1/\epsilon}.

Exposition and scope

W-01 — Moderate scope issue; Definition 2.2 and pp. 4–5. The usual stochastic specialization via Bellman gaps needs a unique-optimal-action qualification. Definition 2.2 requires strictly positive gaps for every off-comparator action, so it does not directly cover general stochastic MDPs with tied optimal actions.

W-02 — Moderate rate-description issue; Remark 4.2, p. 8. The unknown-transition fast rate is described as O(log⁡T)O(\log T), whereas Theorem C.3 contains higher powers of logarithms and further polylogarithmic remainders.

References and citation accuracy

R-01 — Moderate source-characterization issue; p. 4, lines 187–190. The description of Chen et al. (2026) incorrectly applies the condition to a conditional mean and a tail event. Their Assumption 5.1 instead concerns the retained portion of the random loss:

\quad\text{for every }M>0.$$
6 comments
AuthorsOpenReview ↗

Response 1

We thank the reviewer for recognizing the significance of our results and the contribution of removing the truncated non-negativity assumption of [1]. Our response to each question is provided below.

Q1. "This paper lacks numerical evidence to support the claims."

We thank the reviewer for this comment. We would like to note that our paper is a learning theory paper and we believe our contributions are mainly theoretical. In addition, all the existing works on BOBW MDPs [6, 7, 2, 1] also do not include experiments. In light of this, we did not include experiments when submitting our paper.

Nevertheless, we do agree that including empirical results might be beneficial and we have now conducted empirical evaluations and incorporated them into Appendix B of our paper (highlighted in orange). For the convenience of the reviewer, we present the figures and the discussion of the experiments here.

Figure 1: Regret over T=105T=10^5 episodes on the instance with S=50S=50, H=4H=4 and A=3A=3 (mean ±\pm standard error over 10 seeds). Top: known transitions; bottom: unknown transitions.

Figure 2: Scaling with the number of states SS (H=4H=4, A=3A=3) with known transitions. Top: regret after T=105T=10^5 episodes (mean ±\pm standard error over 10 seeds). Bottom: per-episode wall-clock time in milliseconds (logarithmic scale).

Figure 3: Scaling with the number of states SS (H=4H=4, A=3A=3) with unknown transitions. Top: regret after T=105T=10^5 episodes (mean ±\pm standard error over 10 seeds). Bottom: per-episode wall-clock time in milliseconds (logarithmic scale).

Experiment Setup The experiments are conducted on several instances with varying state-space sizes SS in both known- and unknown-transition settings. The detailed setup is as follows.

  • MDP instances. We evaluate the methods on layered episodic MDPs with A=3A=3 actions, H=4H=4 layers and random transitions. The main instance has S=50S=50 states (layers of sizes 1,16,16,16,11,16,16,16,1). We also evaluate the methods on instances with S∈{10,20,100}S\in\{10,20,100\}. Each loss is ℓt(s,a)=mt(s,a)+ξ\ell_t(s,a)=m_t(s,a)+\xi, where ξ\xi is Student-tt noise with 1.751.75 degrees of freedom. Hence E[∣ℓ∣ε]<∞\mathbb{E}[|\ell|^{\varepsilon}]<\infty for ε=1.5\varepsilon=1.5, while the variance is infinite. The moment bound σ=max⁡s,aE[∣ℓt(s,a)∣ε]≈2.48\sigma=\max_{s,a}\mathbb{E}[|\ell_t(s,a)|^{\varepsilon}]\approx 2.48 is computed numerically, and (ε,σ)(\varepsilon,\sigma) is given to all learners.

  • Regimes. We consider three regimes: (i) stochastic, with fixed means; (ii) corrupted stochastic, where during the first 3,0003{,}000 episodes the optimal actions are made to look suboptimal; (iii) adversarial, where two loss tables with different optimal policies alternate every 250250 episodes. Each regime is run with known and with unknown transitions. With unknown transitions, all methods use the same Bernstein-type confidence sets.

  • Baselines. We compare our PO-based method with the OM-based method of [1] and the PO-based method of [2]. We formulate the OM-FTRL step of [1] using the convex optimization modeling framework CVXPY [8, 9], which solves it with the interior-point conic solver Clarabel [10]. For each method we tune a learning-rate scale, a bonus scale and, where applicable, the truncation constant, with the same grid search for all methods, using T=5×104T=5\times10^4 and 3 seeds in the stochastic and adversarial regimes with known and unknown transitions. Then, we use a single configuration per method for all regimes, both transition settings and all problem sizes: the one with the smallest normalized regret averaged over the tuning settings. We report the regret against the best fixed deterministic policy in hindsight, over T=105T=10^5 episodes, as mean ±\pm standard error over 10 seeds.

AuthorsOpenReview ↗

Response 2

Q1. (Cont.) "This paper lacks numerical evidence to support the claims."

Regret Comparisons The full regret curves of all the algorithms on the main instance with S=50S=50 are shown in Figure 1, and the regret at T=105T=10^5 on instances with S=10,20,50,100S=10,20,50,100 is shown in the top rows of Figures 2 and 3. In general, when PP is known, the regret of our algorithm is competitive with that of the algorithm in [1] in the stochastic and corrupted stochastic regimes, and our algorithm is outperformed by the algorithm of [1] in the adversarial regime. However, in the unknown-transition case, on all instances with S=10,20,50,100S=10,20,50,100 and in all three regimes, our algorithm significantly outperforms the algorithm of [1]. This corroborates the improvement in our theoretical guarantees over those of [1]. The detailed comparisons are as follows.

  • Known-transition case. On the instance with S=50S=50 in the known-transition case (Figure 1, top), our algorithm slightly outperforms the OM-based algorithm of [1] in the corrupted stochastic regime but is slightly outperformed by the algorithm of [1] in the stochastic and adversarial regimes. In particular, our method improves over the PO baseline of [2] in every regime (49%, 61% and 18% lower regret) and over [1] in the corrupted stochastic regime (18% lower). In the stochastic and adversarial regimes, its regret is about 25% above that of [1]. Besides, our method is markedly more stable than that of [1]: in the stochastic and corrupted regimes with known transitions, the standard error for the method of [1] is 4–7 times larger.

    On all instances with SS varying in {10,20,50,100}\{10,20,50,100\}, with known transitions (top row of Figure 2), our method performs similarly to the method of [1] for small SS and better in the corrupted regime up to S=50S=50. In contrast, in the adversarial regime, the regret of the method of [1] is smaller than ours for all S∈{10,20,50,100}S\in \{10,20,50,100\}.

  • Unknown-transition case. On the instance with S=50S=50 in the unknown-transition case, our algorithm significantly outperforms the algorithm of [1] in all regimes. In specific, compared with [1], it reduces the final regret by 56% (stochastic), 62% (corrupted) and 34% (adversarial); compared with [2], the reductions are 45%, 54% and 24%.

    On all instances with S∈{10,20,50,100}S\in\{10,20,50,100\}, with unknown transitions (top row of Figure 3), our method has the lowest regret for every SS in every regime. Its regret is 0.36–0.48, 0.09–0.48 and 0.57–0.70 times that of [1] in the stochastic, corrupted and adversarial regimes, respectively.

Comparisons of Computational Efficiency In terms of computation (bottom rows of Figures 2 and 3), our method only performs closed-form statewise updates. Its per-episode wall-clock time is comparable to that of [2]. With known transitions, our method and the method of [2] are 3–4 times faster than the method of [1] at S=10S=10 and 24–28 times faster at S=100S=100, since the method of [1] solves a constrained convex program over the occupancy polytope in every episode. With unknown transitions, our method and the method of [2] are still 2–4.5 times faster.

AuthorsOpenReview ↗

Response 3

Q2. "Full minimax optimality has not been reached for the theoretical results in the contribution."

Thank you for pointing this out. We fully agree that our results do not establish full minimax optimality in all problem parameters, and that closing the remaining gaps is an important research direction.

However, we would like to note that our primary objective in this work, as mentioned in our abstract and introduction, is to address several limitations in the prior work [1] on best-of-both-worlds (BOBW) learning in MDPs with heavy-tailed feedback: the computational burden of global OM-based optimization, the additional truncated nonnegativity assumption required for unknown transitions, and the unfavorable parameter dependence in heavy-tail regret terms. Our method replaces global OM updates with local policy updates, removes this additional truncated nonnegativity assumption, and substantially improves the corresponding heavy-tail regret terms. Achieving these improvements simultaneously requires controlling heavy-tail estimation errors and signed biases, propagating the local regret guarantees through the MDP, and preserving adaptation to stochastic and adversarial regimes. Therefore, we believe the established techniques and the improvements in the regret guarantees already have their own merits, and are meaningful and valuable to the literature.

In addition, we would also like to note that achieving full minimax optimality is challenging even in the simpler setting of bounded losses, unknown transitions, and bandit feedback, without requiring BOBW adaptation. For example, the PO method in [3] does not achieve full minimax optimality in this setting. Even the global OM-based approach in [4] can only achieve O~ ⁣(HSAT)\widetilde{\mathcal O}\!\left(HS\sqrt{AT}\right) regret, which leaves a multiplicative gap of S\sqrt S compared to the lower bound Ω ⁣(HSAT)\Omega\!\left(H\sqrt{SAT}\right).

A very recent PO-based method in [5] also attains the O~ ⁣(HSAT)\widetilde{\mathcal O}\!\left(HS\sqrt{AT}\right) upper bound of the OM-based method in [4] for bounded losses, unknown transitions, and bandit feedback, without requiring BOBW adaptation, while retaining the same S\sqrt S gap to the lower bound. Hence, the difficulty extends beyond heavy-tailed feedback and BOBW adaptation. In other words, we believe achieving full minimax optimality in our setting might be part of a broader research program, and before devising a PO-based method with O(poly⁡(log⁡T))\mathcal{O}(\operatorname{poly}(\log T))-type regret in the stochastic regime and full minimax optimality in the adversarial regime with heavy-tailed noise, one might first need to achieve the following substantial milestones:

  1. Closing the full minimax gap for OM-based methods under bounded adversarial losses and unknown transitions.
  2. Closing the full minimax gap for PO-based methods under bounded adversarial losses and unknown transitions.
  3. Developing a BOBW PO method that simultaneously achieves the full minimax guarantee in the adversarial regime and O(poly⁡(log⁡T))\mathcal{O}(\operatorname{poly}(\log T))-type regret in the stochastic regime under bounded feedback.
  4. Extending these BOBW guarantees to heavy-tailed feedback without additional truncated nonnegativity assumptions.

We believe each milestone already constitutes a substantial research problem in its own right. Resolving all of them would go considerably beyond the scope of our current paper. We therefore leave the pursuit of full minimax optimality to future work, considering it an important research direction.

Reviewer_EHA7OpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies tabular MDPs under heavy-tailed loss and proposes a method to guarantee BOBW through state-by-state policy updates, covering both known and unknown transition cases. The key is the centralized advantage function estimation and the corresponding bias compensation, which allows the cost of heavy-tailed estimation to be controlled by the access volume of suboptimal actions. Compared to existing methods of Chen et al. (2026),, this paper avoids global constraint optimization, improves the parameter dependence of the heavy-tailed main term in the regret bound, and removes the truncated non-negativity assumption under the unknown transition case.

Critical strengths
  • The paper addresses the compatibility issue between heavy-tailed robustness and BOBW adaptive policy optimization, covering both known and unknown transitions uniformly, and eliminates the truncation non-negativity constraint in unknown transition scenarios, advancing the existing theory of heavy-tailed MDPs.
  • The algorithm avoids global occupancy measure constrained optimization by using a per-state policy update, while significantly improving the state and action size dependence of the heavy-tailed main terms in existing results.
  • Centralized estimation allows the truncation compensation cost to vanish as the strategy becomes deterministic, and be controlled by local quantities independent of the optimal action. Combined with the transformation of visit counts before taking fractional powers, it provides a clear and substantive technical approach for handling random fast rates under unknown transitions.
Critical weaknesses

The paper has a clear technical contribution, but the granularity of the proof explanations is uneven: ordinary algebra is repeatedly expanded, and the technical choices in some proofs are also given an excessive level of contribution. I suggest the authors to compress routine derivations and highlight the key steps truly involving measurability, symbolic control, and access distribution.

Questions for authors
  • Could the parameter-free techniques of Chen et al. (2025) be adapted to the per-state policy updates, for example through adaptive skipping and clipping of the loss estimates? It would be helpful to discuss whether this could yield BOBW guarantees with unknown heavy-tail parameters and what additional assumptions might be needed.
3 comments
AuthorsOpenReview ↗

Response 1

We thank the reviewer for recognizing the technical innovations in our centralized advantage function estimation, the significance of our results, as well as the computational advantage of our method over the previous occupancy measure-based approach. Our response to each question is provided below.

Q1. "The paper has a clear technical contribution, but the granularity of the proof explanations is uneven: ... and access distribution."

We have rewritten the proof sketch for our Theorem 4.1 (highlighted in orange), focusing only on the known-transition case and deferring the additional proof sketch for the unknown-transition case to Appendix A.3. We invoke the global-to-local regret reduction lemma from previous works on policy optimization [1, 2] and then explain what the key differences and difficulties are and how we address them. We further emphasize the insights underlying the key technical parts of our proofs and try our best to defer straightforward and standard calculations to the appendix. These key insights as well as the derivations associated with them are further highlighted in red.

In addition, we have also shortened the proofs for some lemmas that are standard in the literature or can be directly adapted from those in the literature. The modifications to the proofs of these lemmas are also highlighted in orange.

We would like to thank the reviewer again for making this suggestion, which we believe further improves the readability of our paper.

Q2. "Could the parameter-free techniques of Chen et al. (2025) be adapted to the per-state policy updates, ... what additional assumptions might be needed."

We thank the reviewer for pointing out this interesting direction. We would like to answer this question on two levels. First, [3] does not require knowledge of the parameters (ε,σ)(\varepsilon, \sigma) of the heavy-tailed loss distribution, yet it imposes the truncated non-negativity assumption. If imposing this assumption is acceptable, we believe it might be promising to eliminate the requirement to know (ε,σ)(\varepsilon, \sigma). One caveat might be that our learning rate in Eq. (13) depends on the state occupancy measure μ~t(s)\widetilde{\mu}_t(s), while their learning rate depends on their adaptive clipped loss estimate as shown in their Eq. (4) (note that the meaning of 'clipping' differs slightly between our work and [3]). A carefully re-designed learning rate that simultaneously adapts to (a) the state occupancy measure μ~t(s)\widetilde{\mu}_t(s) under the (unknown) transition kernel PP in the MDP; and (b) the heavy-tailed distribution by exploiting the adaptive clipped loss estimate in [1] might be needed.

Second, [5] has shown that if either ε\varepsilon or σ\sigma is unknown, the minimax-optimal regret bound for the case with known (ε,σ)(\varepsilon, \sigma) cannot be obtained without imposing any additional assumptions. Further, [6] proves that there does not exist a parameter-free algorithm that can achieve sublinear regret uniformly over all ε∈(1,2]\varepsilon \in (1,2]. Also, as mentioned in our abstract and introduction, one of the main motivations of our work is to eliminate the truncated non-negativity assumption required by [4]. Therefore, we believe requiring knowledge of (ε,σ)(\varepsilon, \sigma) is a natural first step toward eliminating the truncated non-negativity assumption. We do agree that finding an assumption that is milder and more general than both (a) knowing (ε,σ)(\varepsilon, \sigma); and (b) the truncated non-negativity assumption is a valuable and interesting research direction, yet whether such an assumption exists is still not very clear even in the special case of BOBW MAB, so we leave this for future work.


[1] Dann et al. Best of both worlds policy optimization. ICML, 23.

[2] Luo et al. Policy optimization in adversarial MDPs: Improved exploration via dilated bonuses. NeurIPS, 21.

[3] Chen et al. uniINF: Best-of-both-worlds algorithm for parameter-free heavy-tailed MABs. ICLR, 25.

[4] Chen et al. Best-of-both-worlds for heavy-tailed Markov decision processes. ICML, 26.

[5] Genalti et al. (ε,σ)(\varepsilon,\sigma)-adaptive regret minimization in heavy-tailed bandits. COLT, 24.

[6] Genalti et al. Parameter-Free Heavy-Tailed Bandits. arXiv, 26.

Thanks for your response which largely resolve my concerns. I would like to increase my rating to 4.

Thank you again for your positive feedback on our work and for raising your score!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.