Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback

We thank the reviewer for their review. We address their concerns below.

Reviewer’s comment: The dependency in $S, A$ is not optimal in some of the studied cases.

Author’s response: While we agree that the dependence on $S$ and $A$ is not optimal, the same holds for prior works in the standard feedback setting. Improving these bounds in both the standard and aggregate feedback settings remains an important open question.

Reviewer’s question: Can you explain the general algorithm framework and provide pseudo-code?

Author’s response: Our algorithmic framework has the following main components:

1. Building the confidence set of the true state transitions.
2. Building an optimistic loss estimator.
3. Determine a policy using an FTRL with a suitable regularizer which contains both Tsallis-INF and log-barrier.
4. Generate a trajectory using the policy computed and update the estimates.

The main novel aspect of our algorithmic framework is the loss estimator, which eliminates the need for the loss-shifting techniques used in prior work and avoids the additional scaling of the bonus term by a factor of $L$. In addition, our approach generalizes the estimator of Maiti et al. (2025), originally developed for shortest paths in DAGs, to the more general setting of MDPs with aggregate feedback. For the detailed pseudo-code of our algorithm, we refer the reviewer to Algorithm 1 on Page 41 of the supplementary material.

Maiti et al. (2025). Efficient near-optimal algorithm for online shortest paths in directed acyclic graphs with bandit feedback against adaptive adversaries.

Reviewer’s comment: The algorithm is not properly stated in the main paper.

Author’s response: In the revised version, we will prioritize including the algorithm in the main body, space permitting, and adjust the surrounding discussion accordingly.

We thank the reviewer for their review. We address their concerns below.

Reviewer’s question: What specific aspect of the loss estimator allows to avoid scaling the bonus term by an additional factor of $L$? [...] Does this suggest that in the standard episodic MDP setting a similar loss estimator could be used to eliminate this additional term in the regret bound while keeping the same dependencies on the other MDP parameters?

Author’s response: In Eq. (9) on page 7, the presence of the terms $(1 - \pi_t(a \mid s))$ in the numerator of the fraction and $-(1 - \pi_t(a \mid s))$ after the fraction eliminates the need for loss-shifting techniques used in prior work, thereby avoiding the additional scaling of the bonus term by a factor of $L$. Our bounds also improve upon the instance dependent regret guarantees by Jin et al. (2021), who considered the standard episodic MDP setting.

Jin et al. 2021. The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition

We thank the reviewer for their review. We address their concerns below.

Reviewer’s comment: If the authors believe that there is a reason I am underestimating the potential impact of their work, I am open to changing my mind. However, since this is ultimately a very subjective assessment, I think this is unlikely.

Author’s response: We thank the reviewer for their thoughtful assessment and constructive feedback. We acknowledge that parts of the presentation, particularly the transition into the technical sections, could benefit from more intuition and a high-level roadmap. We will address this in the final version.

Regarding the impact of our work, we address a fundamental gap in online learning for MDPs with aggregate bandit feedback, where the learner observes only the total reward over a trajectory. This setting is strictly more challenging than the standard one, where feedback is observed at each step, and it also arises naturally in many practical applications where intermediate rewards are inaccessible or costly to obtain. Existing methods either rely on policy-optimization approaches or linear bandit reductions, neither of which achieve best-of-both-worlds (BOBW) guarantees.

Our technical contribution is twofold:

• Novel estimator and first FTRL algorithm: We build on the recent estimator of Maiti et al. (2025) for shortest paths in DAGs and generalize it in a non-trivial way to design the first FTRL algorithm for aggregate feedback MDPs. This directly leads to the first BOBW guarantees in this setting.

• Simplified analysis and improved bounds: Unlike prior BOBW work in standard MDPs, which required complex loss-shifting techniques, our estimator avoids these techniques and yields a cleaner, more general analysis while improving the regret bounds.

We believe that introducing FTRL to the aggregate-feedback setting, achieving BOBW where prior methods failed, and simplifying the analysis via a more general estimator together lay the groundwork for future advances in online learning with partial feedback.

Reviewer’s comment: “TC” is not defined in Tables 1-3. I understand that it is defined later, but I think everything that is used in the table should be defined in the table.

Author’s response: We apologize for the confusion. “TC” refers to time complexity, and a checkmark indicates that an efficient implementation is possible. We will clarify this in the table for better readability.

Reviewer’s comment: Is there no way to simplify the expression on line 92?

Author’s response: Currently, we are not aware of any way to simplify the expression. Improving upon this remains an important open question.

Reviewer’s comment: Lines 98–107: Why not instead assume that the aggregate losses are in $[0, L]$? That seems simpler.

Author’s response: We assumed that the aggregate losses lie in $[0,1]$ purely for simplicity of presentation. To compare with the $[0,L]$ case, one can simply scale the regret bounds by $L$. Moreover, as explained in Remark 1 of the supplementary material, choosing aggregate losses in $[0,1]$ (or $[0, L]$ when scaled) corresponds to a more general setting than assuming per-layer losses are $O(1)$.

Reviewer’s comment: Line 136: What is this expectation over? Isn’t $c_t$ a constant conditioned on $((s_k, a_k))_k$?

Author’s response: In the stochastic setting, $c_t$ is a noisy reward, and the expectation is taken over the randomness in the noise.

We thank the reviewer for their review. We address their concerns below.

Reviewer’s question: Why is it necessary to assume that the MDP is layered?

Author’s response: Note that this assumption introduces no loss of generality: any finite-horizon MDP can be transformed into a layered one by replicating the state space across $H$ layers. We assume a layered MDP primarily to simplify notation and analysis. This is standard in the literature, for instance, in works like (Jin et al., 2020, Jin et al., 2021), and is often referred to as a loop-free stochastic shortest path problem.

Jin et al. 2020. Learning Adversarial Markov Decision Processes with Bandit Feedback and Unknown Transition

Jin et al. 2021. The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition

Reviewer’s comment: Clarity could be improved by moving the algorithm definition to the main text. In the current version, the main text focuses on explaining the ideas behind building the algorithm, but without clearly presenting the algorithm itself.

Author’s response: We thank the reviewer for this helpful suggestion. We agree that presenting the full algorithm in the main text would improve clarity. In the revised version, we will prioritize including the algorithm in the main body, space permitting, and adjust the surrounding discussion accordingly.

Thank you very much for the clarifications! After reading the other reviewers responses, I decided to maintain my rating.