acceptodds
Under review as a conference paper at ICLR 2027

Adversarial Reinforcement Learning with Transition Predictions

Abstract

We study episodic adversarial Markov decision processes with unknown transition dynamics, where the learner is additionally given a potentially misspecified prediction of the transition kernel. We propose Transition-Prediction Follow-the-Regularized-Leader (TP-FTRL), an occupancy-based algorithm that combines empirical transition confidence sets with likelihood-calibrated confidence sets induced by the prediction. We establish simultaneous high-probability coverage of the true transition kernel without assuming prediction accuracy. We further prove a prediction-independent worst-case regret bound of , matching the state-of-the-art bound by Jin et al. (2020), and showing that arbitrarily inaccurate transition predictions do not degrade the worst-case regret guarantee. When the prediction is close to the empirical transition estimates, the likelihood-calibrated constraints tighten transition uncertainty and yield a sharper regret bound. These results show that TP-FTRL can exploit informative transition predictions while remaining robust to misspecification.

Primary area:
learning theory
Keywords:
Adversarial Markov Decision Processes, Online Learning, Learning with Predictions, Bandit Feedback, Transition Uncertainty

Reviews

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

this paper studies online learning in adversarial tabular MDPs (transition is fixed but losses change arbitrarilly over episodes) with bandit feedback. the only difference with Jin et al. (2020) is that the learner additional has access to a "potentially misspecified prediction of the transition kernel"

this paper gives an FTRL-based algorithm, whose regret is no worse that the state-of-the-art bound in Jin et al. (2020), and can be sharper whenever the predition has good quality.

Critical strengths
  1. this paper is studying a reasonable problem in online learning, which generally lies under the framework of "algorithm with predictions", "learning-augmented algorithms", and "robust-consistency tradeoff"
  2. this paper proposes a novel detection/test of identifying the "accuracy"/"quality" of prediction, so that the final guarantee is shaper when prediction is good, while the worst-case guarantee is never hurt.
Critical weaknesses
  1. I'm concerned about some of the proofs. please see details in "Questions For Authors"
  2. the writing&presentation can be improved
Questions for authors
  1. the update rule in your main algorithm is FTRL-style, but the corresponding regret analysis (lemma 10) is for OMD?
  2. the proof for the general $\kappa $ part is unclear to me: if I look at the proof of lemma 20 (general κ\kappa), it simply says that lemma 20 is implied by lemma 16. However, seems to me that lemma is only for κ=0\kappa = 0?
  3. In the proof of lemma 20, is it true that Term 1 always dominates Term 2? What if κ\kappa is super large?

some comments/feedback for writing:

  1. Abstract should be self-contained in general. in this case you may want to briefly define K,S,A,TK,S,A,T.
  2. "we characterize" between lines 363 and 364 should be capitalized?
  3. in the contribution list (sec. 1.2) you may want to talk about the range of κ\kappa so that the readers know what the final regret could be.
  4. wrong reference format in line 583 : "Ali Nouri. A bayesian sampling approach to exploration in reinforcement learning. In Proceedings of the. . . , 2009."
3 comments

We sincerely thank the reviewer for the careful reading and constructive feedback. We particularly appreciate the reviewer for identifying several issues and ambiguities in our theoretical analysis. We have carefully revisited the proofs and revised the manuscript accordingly. Our detailed responses are provided below.

Q1. The update rule in your main algorithm is FTRL-style, but the corresponding regret analysis (Lemma 10) is for OMD.

We thank the reviewer for pointing out that the connection between the FTRL update in our algorithm and the regret analysis in Lemma 10 was not sufficiently clear in the original manuscript.

We have carefully revisited the proof and revised the derivation to explicitly establish the regret inequality from the stated FTRL optimization problem. In particular, we derive the required inequality using the optimality condition of the FTRL objective and the associated KL-divergence identity, while explicitly accounting for the nested feasible sets.

Importantly, the resulting bound in Lemma 10 for FTRL remains unchanged.

Corresponding revisions: The revised proof is provided in Lines 1166–1241, highlighted in blue.

We sincerely appreciate the reviewer for helping us improve the clarity and rigor of our theoretical analysis.

Q2. In the proof of Lemma 20, it is unclear to me if Lemma 20 is implied by Lemma 16. However, Lemma 16 seems to be only for κ=0\kappa=0.

We thank the reviewer for this insightful observation. We agree that the original presentation did not sufficiently explain how the analysis for the general κ\kappa case follows from the zero-discrepancy case.

To clarify this point, we have revised the proof of Lemma 20. Rather than directly invoking Lemma 16, we follow its proof strategy and replace the transition error bounds used in the zero-discrepancy analysis with the corresponding bounds established in Lemma 19.

More specifically, Lemma 19 provides two bounds under arbitrary κ\kappa: an upper bound on the total transition error, which is used to control Term 1; and a coordinate-wise upper bound on the transition error, which is used to control Term 2. Both bounds incorporate the factor 1+κ1+\kappa. Substituting these bounds into the corresponding steps of the proof of Lemma 16 allows us to extend the analysis to arbitrary κ\kappa.

Thus, the general κ\kappa analysis does not rely on the zero-discrepancy assumption of Lemma 16. Instead, it follows the same proof strategy using the more general transition error bounds established in Lemma 19. We have clarified this argument in the revised manuscript (lines 1742-1745). The corresponding revisions are highlighted in blue.

We appreciate the reviewer for pointing out that this distinction needed to be made explicit.

Q3. In the proof of Lemma 20, is it true that Term 1 always dominates Term 2? What if κ\kappa is super large?

We thank the reviewer for raising this question. We would like to clarify the relationship between the two terms.

Following the analysis of Jin et al. (2020, Appendix B.2) [2], we bound the two terms separately. In our setting, Term 1 grows as O~(T)\widetilde{O}(\sqrt{T}), whereas Term 2 grows as O~(ln⁡T)\widetilde{O}(\ln T), with the remaining problem parameters fixed. Consequently, as the episode horizon TT increases, Term 1 asymptotically dominates Term 2. Furthermore, both terms contain the same factor (1+κ)(1+\kappa). Therefore, even when κ\kappa is arbitrarily large, it does not change the asymptotic relative growth of the two terms.

Finally, we emphasize that our unified regret bound takes the minimum of the discrepancy-dependent and prediction-independent guarantees. Thus, regardless of the magnitude of κ\kappa, the prediction-independent worst-case guarantee remains valid.

[2] Jin, Chi, et al. ``Learning adversarial markov decision processes with bandit feedback and unknown transition." International Conference on Machine Learning. PMLR, 2020.

Additional revisions

Following the reviewer's suggestions, we have also improved the presentation of the manuscript and highlighted the corresponding revisions in blue.

  1. We have revised the abstract to make the problem setting more self-contained by briefly introducing the notation.
  2. We have clarified the interpretation and possible range of the discrepancy parameter κ\kappa in the contribution section.
  3. We have corrected the capitalization and other grammatical issues throughout the manuscript.
  4. We have corrected the reference formatting and verified the corresponding bibliography entry.

We sincerely thank the reviewer again for the constructive comments, which have helped us improve the rigor, clarity, and presentation of our work.

AuthorsOpenReview ↗

Final Reminder: Follow-up on Our Rebuttal

Dear Reviewer q4dg,

As only a few hours remain in the discussion period, we would like to kindly follow up on our rebuttal. We have provided detailed clarifications addressing all your technical concerns. We would sincerely appreciate it if you could review our responses before the deadline and reconsider your rating in light of these clarifications.

Thank you very much for your time and consideration.

Best regards,

Authors

AuthorsOpenReview ↗

Reviewer q4dg: Final Follow-up on Our Rebuttal and Rating Reconsideration

Dear Reviewer q4dg,

Thank you again for your time and constructive feedback.

Although we have not yet received a follow-up response to our rebuttal, we have carefully addressed all your concerns. We would sincerely appreciate it if you could review our clarifications and consider increasing your rating accordingly.

Thank you very much for your time and consideration.

Best regards,

Authors

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

This paper studies episodic adversarial MDPs, where the transition is unknown but fixed. They propose TP-FTRL algorithm. The algorithm maintains a convex confidence set Ct\mathcal{C}_t of valid transitions using both empirical transition prediction (by counting the number of visits) and likelihood-ratio (by comparing to a potentially misspecified prior). It then applies the standard FTRL update on the policy.

The paper then analyzes the algorithm. They provide a worst-case regret bound of O~(K∣S∣∣A∣T)\tilde{\mathcal{O}}(K|\mathcal{S}|\sqrt{|\mathcal{A}|T}), showing the algorithm is robust against arbitrarily prior prediction. Moreover, when maximum normalized discrepancy ratio between empirical and prior transition estimate (defined in paper) is given by κ\kappa, they provide a regret bound O~(K3/2(1+κ)∣S∣∣A∣T)\tilde{\mathcal{O}}(K^{3/2}\sqrt{(1+\kappa)|\mathcal{S}||\mathcal{A}|T}), indicating that the algorithm can perform better when the prior is good.

Critical strengths
  • The study on prior transition prediction is meaningful. The algorithm not only achieves a optimal worst-case regret up to logarithmic factors, but can also reduce the regret when the prior prediction is close to the real transition.
  • The presentation and storyline is clear, especially for the proposed algorithm.
Critical weaknesses
  • The maximum normalized discrepancy ratio is defined using empirical transition prediction Pˉ\bar{P} and the prior P~\tilde{P}, which depends on the run (i.e., depends on the randomness). However, one may expect a discrepancy between the true transition PP and the prior prediction P~\tilde{P}. The relation between κ\kappa, PP and P~\tilde{P} is not directly established in the paper.
Questions for authors
  • See also weaknesses. Is it possible to explain how κ\kappa is related to the discrepancy between PP and P~\tilde{P} directly?
5 comments

The maximum normalized discrepancy ratio is defined using empirical transition prediction Pˉ\bar{P} and the prior P~\tilde{P}, which depends on the run (i.e., depends on the randomness). However, one may expect a discrepancy between the true transition PP and the prior prediction P~\tilde{P}. Is it possible to explain how κ\kappa is related to the discrepancy between PP and P~\tilde{P} directly?

Thank you for pointing out this important distinction. We agree that the original manuscript does not explicitly characterize the relationship between the maximum normalized discrepancy κ\kappa and the prediction error relative to the true transition kernel.

In our setting, the prior transition prediction P~\widetilde P is supplied before the interaction and remains fixed throughout learning. The randomness in κ\kappa comes from the empirical transition estimates and the learner's visitation history.

To address your concern, we introduce a prediction error measure relative to the true transition kernel. Specifically, let ϵ\epsilon (0≤ϵ<∞0\le\epsilon< \infty) satisfy P~(s′∣s,a)≥e−ϵP(s′∣s,a)\widetilde P(s'|s,a)\ge e^{-\epsilon}P(s'|s,a) for each admissible transition triple (s,a,s′)(s,a,s'). Here, ϵ=0\epsilon=0 corresponds to the exact-prediction case, i.e., Pˉ=P~\bar{P}=\widetilde P. Note that ϵ\epsilon is independent to the observed trajectory, although it is generally unknown to the learner.

We establish a high-probability upper bound on κ\kappa that explicitly captures its dependence on the episode count, prediction error, and maximum layer size. Specifically, letting d=max⁡k∣Sk∣d=\max_k|\mathcal S_k|, we show that, with probability at least 1−δ1-\delta,

\frac{2\left[(d-1)\ln 2+ \ln\left(\frac{T|\mathcal S||\mathcal A|}{\delta}\right) \right]+T\varepsilon}{\ln\left(\frac{2|\mathcal S||\mathcal A|}{\delta}\right)}$$ Moreover, we establish an explicit sufficient condition on the prediction error under which the discrepancy-dependent regret bound is sharper than the prediction-independent worst-case bound. In particular, if $$\varepsilon< \frac{ \left(\frac{|\mathcal S|}{K}-1\right) \ln\left(\frac{2|\mathcal S||\mathcal A|}{\delta}\right) -2\left[(d-1)\ln 2+ \ln\left(\frac{T|\mathcal S||\mathcal A|}{\delta}\right)\right]}{T},$$ then $K(1+\kappa)<|\mathcal S|$ holds with probability at least $1-\delta$, provided the right-hand side is positive. This result also covers the exact-prediction case by setting $\varepsilon=0$, and explicitly accounts for finite-sample fluctuations of the empirical transition estimates. The proof is provided in Appendix C.6, where we use the multinomial KL concentration result of Agrawal (2020, Theorem I.3) and a union bound over all state-action pairs and episodes, followed by a decomposition of the KL divergence between the empirical transition estimate and the prediction. **Corresponding revisions:** The prediction-error characterization and Corollary 1 have been added to the main text (Lines 473–490). The complete proof is provided in Appendix C.6 (Lines 1836–1943), highlighted in blue. [1] Agrawal, Rohit. "Finite-sample concentration of the multinomial in relative entropy." IEEE Transactions on Information Theory 66.10 (2020): 6297-6302.

Thanks for the response, and I think the revision addresses my concern. I will keep my score for this paper.

Dear Reviewer SSVW,

Thank you very much for your follow-up and for acknowledging that our revisions have addressed your concern. We sincerely appreciate your time and thoughtful assessment.

Given that your concern has been addressed, we would be very grateful if you could kindly reconsider whether an adjustment to your rating might be warranted in light of our clarifications and revisions.

We fully respect your assessment and would be happy to address any remaining concerns that may influence your rating.

Thank you again for your time and consideration.

Best regards,
Authors

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

The paper introduces TP-FTRL for episodic adversarial MDPs with unknown transition dynamics, bandit feedback, and potentially unreliable transition predictions. The method integrates empirical and prediction-informed likelihood confidence sets into an occupancy-based FTRL framework. The analysis guarantees high-probability coverage and retains the baseline worst-case regret bound irrespective of prediction quality, while providing a tighter bound when predictions align closely with empirical transitions. Validation relies on theoretical proofs and a convex reformulation, with no empirical experiments presented.

Critical strengths
  1. The likelihood-calibrated confidence sets preserve high-probability coverage without assuming prediction accuracy. Combined with empirical confidence sets, they retain the baseline worst-case regret guarantee, making the approach relevant when prior models are informative but unreliable.

  2. The discrepancy-dependent regret bound identifies when predictions improve the guarantee, while the unified bound retains worst-case protection. This provides a concrete theoretical account of the value of prior transition information in adversarial RL with bandit feedback.

Critical weaknesses
  1. The bound depends on an instance- and trajectory-dependent discrepancy: both the visited state–action pairs and their sample counts are determined by the learner’s policy. Thus, this quantity does not characterize prediction quality independently of the algorithm. It is unclear how to assess whether it will be small in a given problem, and guarantees under different policies are not directly comparable because they are evaluated on different visitation histories. This limits the bound’s usefulness for establishing when, and by how much, transition predictions improve learning.

  2. The algorithm retains historical confidence constraints and repeatedly solves policy-optimization and upper-occupancy problems. Although the paper provides a convex formulation of the FTRL update, it offers neither a detailed overall computational analysis nor experiments demonstrating scalability or realized prediction gains. This leaves the practical value of the proposed method uncertain.

Questions for authors
  1. Since κ\kappa depends on policy-induced visitation counts and empirical transitions, can it be bounded using properties of the underlying MDP and prediction that are independent of the learner’s realized trajectory? In particular, under what conditions does the improvement criterion K(1+κ)<∣S∣K(1+\kappa)<|S| hold with high probability, including when P~=P\widetilde P=P? This would clarify whether the bound provides a meaningful basis for assessing prediction benefits and comparing algorithms.

  2. What is the overall per-episode computational cost, including both the FTRL update and upper-occupancy calculations, as historical constraints accumulate? Does the convex formulation yield an implementable algorithm at a reasonable scale?

5 comments

Thank you for the careful assessment and for recognizing the high-probability coverage and prediction-independent regret guarantees. We appreciate your questions regarding the interpretation of the discrepancy parameter and the computational cost of the complete algorithm. We have added further theoretical characterization and a detailed computational analysis in the revised manuscript, as explained below.

Q1. Since κ\kappa depends on policy-induced visitation counts and empirical transitions, can it be bounded using properties of the underlying MDP and prediction that are independent of the learner's realized trajectory? In particular, under what conditions does the improvement criterion K(1+κ)<∣S∣K(1+\kappa)<|\mathcal S| hold with high probability, including when P^=P\widehat{P}=P? This would clarify whether the bound provides a meaningful basis for assessing prediction benefits and comparing algorithms.

We agree that the discrepancy parameter κ\kappa depends on the empirical transition estimates and the learner's realized visitation history. To better characterize the benefit of transition predictions, we introduce a prediction error measure relative to the true transition kernel, denoted by ε\varepsilon. Specifically, we let ε∈[0,∞)\varepsilon\in[0,\infty) satisfy $\widetilde P(s'\mid s,a) \geq e^{-\varepsilon}P(s'\mid s,a)$ for each admissible transition triple (s,a,s′)(s,a,s'). Here, ε=0\varepsilon=0 corresponds to the exact-prediction case, i.e., P~=P\widetilde P=P. Note that ε\varepsilon is independent of the observed trajectory, although it is generally unknown to the learner.

We establish a high-probability upper bound on κ\kappa that explicitly captures its dependence on the episode count, prediction error, and maximum layer size. Specifically, letting d=max⁡k∣Sk∣d=\max_k|\mathcal S_k|, we show that, with probability at least 1−δ1-\delta,

\leq \frac{ 2\left[ (d-1)\ln 2+ \ln\left(\frac{T|\mathcal S||\mathcal A|}{\delta}\right) \right]+T\varepsilon }{ \ln\left(\frac{2|\mathcal S||\mathcal A|}{\delta}\right) }.$$ Moreover, we establish an explicit sufficient condition on the prediction error under which the discrepancy-dependent regret bound is sharper than the prediction-independent worst-case bound. In particular, if $$\varepsilon< \frac{ \left(\frac{|\mathcal S|}{K}-1\right) \ln\left(\frac{2|\mathcal S||\mathcal A|}{\delta}\right) -2\left[ (d-1)\ln 2+ \ln\left(\frac{T|\mathcal S||\mathcal A|}{\delta}\right) \right] }{T},$$ then $K(1+\kappa)<|\mathcal S|$ holds with probability at least $1-\delta$, provided the right-hand side is positive. This result also covers the exact-prediction case by setting $\varepsilon=0$, and explicitly accounts for finite-sample fluctuations of the empirical transition estimates. The proof is provided in Appendix C.6, where we use the multinomial KL concentration result of Agrawal (2020, Theorem I.3) [1] and a union bound over all state-action pairs and episodes, followed by a decomposition of the KL divergence between the empirical transition estimate and the prediction. **Corresponding revisions:** The prediction-error characterization and Corollary 1 have been added to the main text (Lines 473–490). The complete proof is provided in Appendix C.6 (Lines 1836–1943), highlighted in blue. [1] Agrawal, Rohit. "Finite-sample concentration of the multinomial in relative entropy." IEEE Transactions on Information Theory 66.10 (2020): 6297-6302.

Q2.What is the overall per-episode computational cost, including both the FTRL update and upper-occupancy calculations, as historical constraints accumulate? Does the convex formulation yield an implementable algorithm at a reasonable scale?

We agree that the convex formulation of the FTRL update alone does not fully characterize the computational cost of TP-FTRL. The complete algorithm involves both the FTRL update and the upper-occupancy calculations. We therefore provide an explicit accounting of the optimization variables, linear constraints, and exponential-cone blocks for both operations.

FTRL update. Let $E=\sum_{k=0}^{K-1} |\mathcal S_k||\mathcal A_k||\mathcal S_{k+1}|, ; M=\sum_{k=0}^{K-1} |\mathcal S_k||\mathcal A_k|$ denote the numbers of admissible transition triples and nonterminal state-action pairs, respectively. In each episode tt, the FTRL update has at most 2E+M+(t−1)∣S∣2E+M+(t-1)|\mathcal S| variables, at most E+(t−1)∣S∣E+(t-1)|\mathcal S| exponential-cone blocks, and at most 2E+M+(t−1)K2E+M+(t-1)K linear constraints.

Upper-occupancy calculations. For a fixed policy πt\pi_t and a visited state-action pair (s,a)(s,a), the upper-occupancy calculation maximizes q(s,a)q(s,a) subject to the occupancy-flow constraints (18), empirical confidence constraints (19), likelihood-calibrated constraints (21)–(22), and the policy-consistency constraints $q(s,a)=\pi_t(a\mid s) \sum_{b\in\mathcal A_k}q(s,b), s\in\mathcal S_k, a\in\mathcal A_k$. Each upper-occupancy calculation has at most E+M+(t−1)∣S∣E+M+(t-1)|\mathcal S| variables, at most (t−1)∣S∣(t-1)|\mathcal S| exponential-cone blocks, and at most 2E+2M+(t−1)K2E+2M+(t-1)K linear constraints. At most KK upper-occupancy problems are solved per episode, corresponding to the KK state-action pairs visited in the current trajectory.

Both the FTRL update and the upper-occupancy computations admit finite-dimensional exponential-cone formulations and can be solved numerically using standard conic optimization solvers. Thus, the proposed algorithm provides a concrete convex optimization-based implementation of both policy updates and upper-occupancy estimations.

Our complexity analysis also reveals that the number of likelihood-related auxiliary variables and exponential-cone blocks can grow linearly with the number of episodes. Although standard exponential-cone solvers provide a direct means of implementing both optimization steps, repeatedly solving these problems may become computationally expensive for large-scale instances or long horizons. Developing more computationally efficient algorithms for both the FTRL update and upper-occupancy calculations, particularly by exploiting the structure of the occupancy constraints, is therefore an important direction for future work.

Corresponding revisions: The computational complexity of the FTRL update has been added to the revised manuscript (Lines 818–837), followed by the computational complexity of the upper-occupancy calculations (Lines 840–852). The corresponding revisions are highlighted in blue.

We hope that these additional theoretical and computational characterizations address your concerns and clarify both the conditions under which transition predictions improve the regret guarantee and the computational requirements of the complete TP-FTRL algorithm.

AuthorsOpenReview ↗

Final Reminder: Follow-up on Our Rebuttal

Dear Reviewer Te87,

As only a few hours remain in the discussion period, we would like to kindly follow up on our rebuttal.

We have addressed both of your questions with detailed theoretical clarifications and computational complexity analyses. Reviewer SSVW, who raised a similar concern, has also acknowledged that our revisions addressed their concern. We would sincerely appreciate it if you could review our responses and reconsider your rating before the deadline.

Thank you for your time and consideration.

Best regards,

Authors

Comments on the paper

2 comments

As the discussion period is approaching its end, please take a moment to review the authors’ responses and share any remaining thoughts or updates to your assessment. Thanks for your thoughtful reviews and discussion!

AuthorsOpenReview ↗

Summary of Rebuttal and Manuscript Revisions

We sincerely thank the Area Chair Kf78 and all reviewers for their careful evaluation and constructive feedback. During the rebuttal period, we addressed the reviewers' concerns and made substantial revisions to the manuscript, highlighted in blue. We would like to summarize the key improvements and their corresponding locations in the revised manuscript.

1. Theoretical characterization of prediction quality (Reviewers Te87 and SSVW).

Both reviewers raised closely related concerns about the trajectory dependence of the discrepancy parameter κ\kappa and its relationship to the true prediction error. To address these concerns, we introduced a trajectory-independent prediction error measure ε\varepsilon relative to the true transition kernel. We established a high-probability upper bound on κ\kappa and derived an explicit sufficient condition under which the prediction-dependent regret bound improves upon the worst-case guarantee. These results also cover the exact-prediction case and account for finite-sample estimation errors.

Importantly, Reviewer SSVW explicitly acknowledged in their follow-up that our revision addresses their concern, which closely overlaps with the first concern raised by Reviewer Te87.

Corresponding revisions: Corollary 1 and the prediction-error characterization have been added to the main text (Lines 473–490), with the complete proof in Appendix C.6 (Lines 1836–1943).

2. Clarification of the regret analysis (Reviewer q4dg).

We carefully revisited and expanded the presentation of our theoretical proofs to address the reviewer's questions. Specifically, we (i) clarified the derivation of Lemma 10 directly from the FTRL update, importantly, without changing the resulting bound for FTRL stated in Lemma 10; (ii) expanded the explanation of Lemma 20 to make explicit how the proof extends to general κ\kappa using the bounds established in Lemma 19; and (iii) clarified the relative contributions of the two regret terms, including their dependence on κ\kappa.

Corresponding revisions: The expanded proof of Lemma 10 is provided in Lines 1166–1241, and the clarification of the general-κ\kappa argument in Lemma 20 is provided in Lines 1742–1745. These revisions improve the clarity and accessibility of the theoretical analysis while preserving the original regret guarantees.

3. Computational complexity and implementability (Reviewer Te87).

We added a detailed computational complexity analysis of both the FTRL update and upper-occupancy calculations, explicitly accounting for optimization variables, linear constraints, and exponential-cone blocks. Both operations admit finite-dimensional convex formulations that can be solved numerically using standard conic optimization solvers. We also discuss the computational growth with the number of episodes and acknowledge scalability as an important direction for future work.

Corresponding revisions: The computational complexity analyses of the FTRL update and upper-occupancy calculations are provided in Lines 818–837 and Lines 840–852, respectively.

4. Presentation improvements (Reviewer q4dg).

We revised the abstract to make the problem setting more self-contained, clarified the interpretation and possible range of κ\kappa in Section 1.2, and addressed the identified grammatical and reference-formatting issues.

Final consideration.

We are grateful that Reviewer SSVW confirmed that our revisions addressed their concern, although the score remained unchanged. Since the central concern raised by Reviewer Te87 substantially overlaps with the concern acknowledged as addressed by Reviewer SSVW, we respectfully hope the Area Chair Kf78 will also consider this new theoretical characterization when evaluating Reviewer Te87's assessment. We have additionally provided a detailed computational complexity analysis addressing Reviewer Te87's remaining concern.

Although we have not received further feedback from Reviewers Te87 and q4dg, we have provided detailed responses and corresponding manuscript revisions addressing their substantive questions.

We believe these revisions substantially strengthen the theoretical characterization, clarity, and completeness of the paper. We respectfully hope the Area Chair Kf78 will take the revised manuscript and our detailed responses into account when making the final recommendation, particularly since the substantive improvements may not be fully reflected in the numerical review scores.

Thank you very much for your time and consideration.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.