Online Robust Reinforcement Learning Through Monte-Carlo Planning

We thank the reviewer for their positive review of our paper. We will revise our paper based on these comments.

Computation efficiency We want to emphasize that the robust value under all ambiguity balls with radius $\rho_T$ can be computed in at most $O(S \log(S))$ time. Thus requiring only marginally more computation than standard Bellman operators $O(S)$. It is an open research direction to design and showcase computation efficiency for other kind of robust ambiguity sets. We have only considered some popular ones from the $f$-divergence class and the Wasserstein ball. Our contribution in this work has been to adopt robust optimization tools for the standard MCTS planning that has seen historical successes in many sequential decision-making applications.

Scaling to higher dimensions As a next step for high-dimensional settings, we want to test our robust MCTS approach for Go. We recently found that there have been some interest [R1] in discovering adversarial plays for Go and algorithms to mitigate such plays. We believe our approach can handle such adversarial Go strategies. This is our future focus. We think as further next steps, our robust MCTS approaches can resolve some parameter uncertainty in real-world robotic problems [R]. We are excited for all these next steps from this initial contribution we have made to bring in robust optimization for traditional MCTS approach.

[R1] Tseng, T., McLean, E., Pelrine, K., Wang, T. T., & Gleave, A. (2024). Can Go AIs be adversarially robust?. arXiv preprint arXiv:2406.12843.

[R2] Dam, T., Chalvatzaki, G., Peters, J., & Pajarinen, J. (2022). Monte-carlo robot path planning. IEEE Robotics and Automation Letters, 7(4), 11213-11220.

We look forward to hearing from you and providing any other clarifications during the discussion period (up to Apr 8). Thank you!

We thank the reviewer for their thoughtful and constructive comments on our paper. We are encouraged by the fact that they found our paper: provide a good overview and comparison to prior work, our test suites are at the right level of challenge. We'd like to address several important points below. We will revise our paper based on these comments.

FrozenLake results

We thank the reviewer for raising this important point about our FrozenLake results. They identified a pattern that seems counterintuitive at first glance - where more conservative planning doesn't always translate to better performance in less stochastic execution environments. This behavior stems from several key aspects of our experimental setup:

1.Episode Structure: We do implement a maximum episode length (200) in our FrozenLake environment. This creates two possible failure modes: (a) falling into a hole (terminal state with zero reward) or (b) timing out (exceeding the maximum steps without reaching the goal).

2.Fixed Simulation Budget: To ensure fair comparison across all experimental conditions, we standardized the number of MCTS rollouts for each planning process. This design choice significantly impacts our results. When planning with higher slip probabilities ( $p_{slip} = 0.5$), the search space becomes substantially more stochastic, requiring more simulations to converge to an optimal policy. The key insight for understanding why planning with $p_{slip} = 0.3$ outperforms planning with $p_{slip} = 0.5$ (even when executed in a $p_{slip} = 0.5$ environment) lies in the convergence rate of policy search under different noise levels. In highly stochastic planning environments, the reward signal becomes noisier and the effective search space expands dramatically. With our fixed simulation budget, planning with $p_{slip} = 0.3$ benefits from clearer reward signals and a more focused search space, allowing it to discover strategies that balance safety and efficiency. In contrast, planning with $p_{slip} = 0.5$ with limited rollouts often results in overly conservative policies that increase the likelihood of timeout failures, even when executed in the same stochastic environment used for planning. We fundamentally agree with your expectation that "an agent that plans more conservatively (higher, e.g., 0.5) does not transition to unfavorable states in MDPs with less stochasticity than anticipated (lower, e.g., 0.1)." This principle would likely emerge if we allowed sufficient computational budget for full policy convergence at each slip probability level.

Table 1 parameters used in each experiment The parameters in Table 1 were chosen specifically to achieve the optimal convergence rate shown in Theorem 3. To obtain the optimal simple regret of $\mathcal{O}(n^{-1/2})$, we need $\frac{b_i}{\beta_i} = \frac{1}{4}$ and $\frac{\alpha_i}{\beta_i} = \frac{1}{2}$, which follows directly from the proof of Theorem 3. These ratios ensure that the algorithm can obtain the optimal rate of $\mathcal{O}(n^{-1/2})$. With these parameter settings, the exploration bonus term in our action selection rule becomes: $C \cdot \frac{(T_{s_h}(t))^{\frac{1}{4}}}{(T_{s_h,a}(t))^{\frac{1}{2}}}$ This specific form of the exploration term provides the necessary balance between exploring uncertain actions and exploiting promising ones under model ambiguity. We chose the exploration constant C = 2 for all the experiments. We apologize for the ambiguity and will update the details in the revised version.

Improved documentation We appreciate this valuable suggestion regarding code documentation. We will update the provided code with clear docstrings and comments that explicitly connect implementation blocks to their corresponding steps in Algorithm 1, along with a mapping document that shows the direct relationship between notations and implementation.

Related works We thank the reviewer for pointing us to [R1, R2]. As the reviewer mentions, these are not mathematically rigorous works - but nonetheless, they propose heuristic methods to address environmental uncertainty. We will include these works in our revised paper.

[R1] Rostov, M., & Kaisers, M. (2021). Robust online planning with imperfect models. In Adaptive and Learning Agents Workshop

[R2] Farnaz Kohankhaki, Kiarash Aghakasiri, Hongming Zhang, Ting-Han Wei, Chao Gao, Martin Muller: Monte Carlo Tree Search in the Presence of Transition Uncertainty

We look forward to hearing from you and providing any other clarifications during the discussion period (up to Apr 8). Thank you!

We thank the reviewer for their thoughtful feedback.

Baseline comparisons Our work focuses specifically on robust online planning using MCTS, and to the best of our knowledge, this work is the first to provide theoretical guarantees for robust online planning using MCTS, with convergence bounds matching those of standard MCTS while providing robustness to model misspecification. Our method differs fundamentally from offline learning approaches like robust value iteration or Q-learning. This distinction is critical for several reasons:

1. Online vs. Offline Paradigm: MCTS performs dynamic tree expansion from the current state during execution, while methods like robust value iteration [1,2] require pre-computing policies across the entire state space. This fundamental difference makes direct comparisons methodologically problematic.
2. Controlled Comparison: By comparing Robust-Power-UCT against Stochastic-Power-UCT, we isolate the specific impact of our robustness modifications while controlling for all other algorithmic components, providing a clear assessment of our contribution.
3. Principled Exploration: MCTS naturally incorporates optimism-under-uncertainty for exploration, adapting to each state encountered during execution. This contrasts with offline methods that require separate exploration strategies or complete model knowledge.
4. Integration with Deep Learning: Recent breakthroughs like AlphaZero [3] and MuZero [4] have demonstrated the power of integrating MCTS with neural networks. This would allow us to leverage value functions learned through offline methods (like robust value iteration) to guide online planning while maintaining robustness guarantees. This integration represents a promising direction where our work complements, rather than competes with, offline robust RL methods - creating a hybrid approach that benefits from both paradigms.

The empirical results across both environments consistently demonstrate that Robust-Power-UCT significantly outperforms non-robust approaches under model mismatch conditions.

[1] Nilim, A. and El Ghaoui, L. (2005). Robust control of Markov decision processes with uncertain transition matrices.

[2] Iyengar, G.N. (2005). Robust dynamic programming. Mathematics of Operations Research.

[3] Silver, D. et al. (2018). A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play.

[4] Schrittwieser, J. et al. (2020). Mastering Atari, Go, chess and shogi by planning with a learned model.

Gambler's problem performance We agree that our phrasing could be improved for clarity. When discussing "superior performance," we should have been more precise. What we intended to highlight was our algorithm's ability to maintain consistent performance across different execution environments, particularly when the execution probability is lower than the planning probability. This consistency under model mismatch is what defines robustness in our context, rather than achieving the highest possible reward in matched conditions. We'll clarify this important distinction between optimality and robustness in the revised paper to avoid any confusion.

Confidence intervals We report success rates as the proportion of successful episodes over 100 independent runs, which directly measures the algorithm's ability to complete the task. Success rate is a binary outcome metric (success/failure), so traditional error bars aren't applicable - the reported percentage itself represents the statistical performance. We chose this metric over average reward with confidence intervals as it provides a more interpretable and direct evaluation of performance in environments with sparse rewards. However, if preferred, we can supplement our analysis with mean reward and standard deviation in our revised paper.

Frozen Lake performance The reviewer's observation about planning with different slip probabilities highlights an important point that we should clarify. When planning with lower slip probabilities (e.g., $p=0.3$), the environment is more deterministic, allowing the algorithm to find more reliable paths within a fixed computational budget. The Frozen Lake environment has a particular characteristic where reducing slippage improves performance up to a certain point - with too little slippage, the agent might fail to consider important failure modes. With the same number of rollouts, planning in a lower-noise environment naturally leads to better policies. As the planning slip probability increases (e.g., $p=0.5$), the higher stochasticity requires significantly more rollouts to converge to optimal paths since the signal-to-noise ratio decreases. This explains why planning with $p=0.3$ can outperform planning with $p=0.5$ even when executed in matching environments.

We look forward to hearing from you and providing any other clarifications during the discussion period (up to Apr 8). Thank you!

We thank the reviewer for their thoughtful and constructive comments on our paper. We are encouraged by the fact that they found our paper: well-written, technically sound, aligns with prior work on robust RL. We'd like to address several important points below. We will revise our paper based on these comments.

Robustness and Conservative Policies The reviewer correctly notes that robust planning can lead to more conservative policies. This is indeed an intentional feature rather than a limitation. In many high-stakes applications (autonomous vehicles, medical robotics, financial systems), conservative policies that prioritize worst-case performance are precisely what is needed when the cost of failure is high. Our approach enables this safety-oriented planning while maintaining theoretical guarantees.

Lack of ablation studies While we appreciate the concern about ablation studies, we believe there may be a misunderstanding of our experimental approach. In our paper, we already provide explicit comparisons between different ambiguity set formulations (Total Variation, Chi-squared, and Wasserstein) across all experiments, with Tables 2 and 4 showing comprehensive results for each formulation under various planning-execution scenarios. In particular, the robust policies across Total Variation, Chi-squared, and Wasserstein are separately trained, and none of them affects the other. If the reviewer is suggesting a different form of ablation beyond comparing these different uncertainty sets, we would appreciate clarification on what specific ablation studies would be most valuable to include in our revised paper.

Performance Trade-offs We appreciate the observation about trade-offs between robustness and performance. Section E.3 in the supplementary material provides a detailed analysis of this trade-off. The ambiguity set radius parameter ρ provides direct control over this trade-off. When ρ = 0, our approach reduces exactly to standard Power-UCT, while increasing ρ progressively enhances robustness at the potential cost of optimality under matched conditions.

Evaluation Environments As mentionned by reviewer k1UW, the selected environments are well-known benchmarks in RL literature that effectively capture the robustness/uncertainty problems we're addressing. While not as complex as some benchmark suites, they provide the right level of challenge to highlight our solution's properties while remaining computationally tractable for robust planning experiments.

Scalability and Computational Cost The robust value under all ambiguity balls with radius $\rho_T$ can be computed in at most $O(S \log(S))$ time. Thus requiring only marginally more computation than standard Bellman operators $O(S)$. It is an open research direction to design and showcase computation efficiency for other kind of robust ambiguity sets. We have only considered some popular ones from the $f$-divergence class and the Wasserstein ball.

Broader Application Domains Thanks for this constructive review. As a next step for high-dimensional settings, we want to test our robust MCTS approach for Go. We recently found that there have been some interest [R1] in discovering adversarial plays for Go and algorithms to mitigate such plays. We believe our approach can handle such adversarial Go strategies. This is our future focus. We think as further next steps, our robust MCTS approaches can resolve some parameter uncertainty in real-world robotic problems [R2]. We are excited for all these next steps from this initial contribution we have made to bring in robust optimization for traditional MCTS approach.

[R1] Tseng, T., McLean, E., Pelrine, K., Wang, T. T., & Gleave, A. (2024). Can Go AIs be adversarially robust?. arXiv preprint arXiv:2406.12843.

[R2] Dam, T., Chalvatzaki, G., Peters, J., & Pajarinen, J. (2022). Monte-carlo robot path planning. IEEE Robotics and Automation Letters, 7(4), 11213-11220.

We look forward to hearing from you and providing any other clarifications during the discussion period (up to Apr 8). Thank you!