Efficient Action Robust Reinforcement Learning with Probabilistic Policy Execution Uncertainty

To weakness 1.

We agree with the reviewer that the contributions in Section 4 are incremental. However, the results in Section 4 are not the core contributions of our paper. The main purpose of results in Section 4 is to provide motivation and insights for the design of the proposed two efficient algorithms in later sections. The approaches of Pinto et al. (2017) and Tessler et al. (2019) used an alternating update method that repeatedly solves MDP by fixing either the adversary policy or the agent policy and are sample inefficient. In our proposed algorithm, we use the iteration of action robust Bellman equation to solve the robust problem. Our proposed method can avoid the alternating update between the adversary policy and agent policy. Thus, we need to first introduce the results in Section 4. The proposed action robust Bellman equation in Section 4 tells the reader how to directly solve the robust problem for finite-horizon setting when we know the reward function and transition probabilities, and makes ARRLC more easily understandable.

To reflect the discussion above, we have changed the Theorem 1 to Proposition 1 in the revised version so as to de-emphasize the results in Section 4, changed the description of the main contributions in page 2 and added the discussion about the importance of introducing action robust Bellman optimality equation in the revised paper.

To weakness 2.

ARRLC shares a similar form with ORLC, but is not an simple extension of ORLC with less technical challenges. Similar to ORLC, ARRLC considers the upper bound and the lower bound of $Q$-values and $V$-values. However, the trajectory sampling and the update of the value functions in ARRLC are different from those in ORLC, as we considered the action robust Bellman equation. More specifically, ARRLC uses two different actions $\overline{\pi}(s)$ and $\underline{\pi}(s)$ to update the value functions but only samples one of them at each step, while ORLC uses the sampled action $\pi(s)$ to update the value function (refer to Line 12 Algorithm 1 in Dann et al, (2019)). We need to do this because the update of the action robust Bellman equation requires both the maximum and minimum over the actions. Thus, some new technical challenges arises. For example, the empirical variance estimators $Var((\overline{V}+\underline{V})/2)$ sum not only over all episode $k$ and step $h$ but also over two different action $\overline{\pi}(s)$ and $\underline{\pi}(s)$, but only one action, $\overline{\pi}(s)$ or $\underline{\pi}(s)$, is sampled. Thus, the sum of variance is no longer simply the variance of the sum of rewards per episode, and we need new techniques to bound the sum of variance. We deal with this challenge in Appendix page 21-24. Some new techniques are then introduced, e.g., $\text{Var}((\overline{V}+\underline{V})/2)$ is further replaced with $C^{\pi^{k_*,\pi^k,\rho}}$, and different confidence bounds are used in our paper. We added these discussion in Section 5.1 at the top of page 6.

Dear reviewer N6KC,

Thank you for dedicating your time to reviewing our manuscript. Your insights have been invaluable, and we've crafted a detailed response to address the points you raised and polish the paper accordingly. We're confident that our responses and modifications have effectively addressed your concerns. With these changes in mind, we hope you might reconsider and adjust your evaluation of our work.

Should there be any remaining issues, we're more than ready to provide further clarifications. As the rebuttal phase is nearing its deadline, we're looking forward to engaging in a timely discussion. Thank you again for your expertise and guidance!

To weakness 1.

We agree with the reviewer that the concept of the probabilistic action robust MDP and the existence of its optimal policy is not novel, which was introduced by Tessler et al. (2019). However, Tessler et al. (2019) and other related papers did not discuss the action robust bellman equation. In Section 2, we showed that the optimal action robust policy can be solved via the iteration of the action robust Bellman optimality equation. This motivated us to use the action robust Bellman optimality equation to directly solve the robust problem, and then we designed two efficient algorithms based on the action robust Bellman optimality equation.

Using the iteration of the proposed action robust Bellman equation to solve the robust problem can avoid the alternating update between the adversary policy and agent policy. The alternating update method is used in the approaches of Pinto et al. (2017) and Tessler et al. (2019), and is sample inefficient.

Thus, we emphasize that the optimal action robust policy can be solved via the iteration of the action robust Bellman optimality equation in Section 2. and is the important idea of our proposed efficient algorithm.

To reflect the above, we changed the Theorem 1 to Proposition 1 in the revised version so as to de-emphasize the results in Section 4, changed the description of the main contributions in page 2 and added the discussion about the importance of introducing action robust Bellman optimality equation in the revised paper.

To Weakness 2.

We agree with the reviewer that the regret analyses in this paper highly depend on the choice of uncertainty sets. However, in the existing literature, it is a common practice to consider the property of the specific uncertainty set when designing efficient robust RL algorithms. For example, Wang et al. (2021) consider the R-contamination probability uncertainty set, and its convergence analyses highly depend on the property of the R-contamination uncertainty set. It utilizes the property that the minimum over the probabilities set is the minimum over the entire state space.

The proof techniques may not be extended easily to other uncertainty sets, but the idea of the robust algorithm designing can be potentially used in other action robust uncertainty sets. Directly using the iteration of the action robust Bellman equation and simultaneously updating adversary policy and agent policy is more sample efficient than the alternating update method in Pinto et al. (2017) and Tessler et al. (2019).

To Question 3.

This paper focuses on the tabular environment. It is true that the current theoretical guarantee on the sample complexity of the proposed algorithms is based on the tabular setting. However, the policy execution uncertainty set itself is also applicable for large-scale problems. For example, Tessler et al. (2019) introduced the probabilistic policy execution uncertainty set and perform extensive evaluation across several MuJoCo environments.

Designing provably sample efficient algorithm for large-scale problems is an important future direction for us to pursue. From our work, we found two insights that could be useful for large-scale problems: (1) The adversary policy and the agent policy can be simultaneously updated to efficiently sample trajectories; (2) The adversary policies at each episode does not necessarily need be the minimum over the actions, an approximation of the minimum also works. Based on these insights, a policy gradient method could potentially be designed handle the continuous action space in the robust problem. We can use policy gradient method, such like PPO, to find an approximation of the adversary policy (the minimum over actions).

We also thank the reviewer for bring the paper [Zhou et al., 2023, Natural Actor Critic for Robust Reinforcement Learning with Function Approximation] to our attention. Consider a variant of the proposed probabilistic policy execution uncertainty set is also a good idea. We added these discussions in the conclusion section of the revised version.

To weakness 4.

We added the discussion related to the paper [Iyengar'05, Robust dynamic programming] in the revised version.

Thank you for your reply to solve some of my concerns. I have increased my score.

To Question 1.

Our experimental results consists of three parts. (1) We compared our proposed method ARRLC with a non-robust algorithm ORLC and show the robustness of our algorithm. (2) We compared ARRLC with robust TD and demonstrates the efficiency of our ARRLC algorithm. ARRLC converges much faster than robust TD algorithm. (3) In the appendix, we compared our algorithm with the algorithms in Pinto et al. (2017) and Tessler et al. (2019) under different $\rho$ and $p$. We used a black-box MDP solver (Q-learning) to solve the optimal agent policy when the adversarial policy is given. We trained our method in 2000 episodes and others in 30000 episodes. Compared with our algorithm, the approaches of Pinto et al. (2017) and Tessler et al. (2019) are sample inefficient .

Due to the page limits, we put some experimental results of (3) into Appendix. We agree with the reviewer that providing the numerical comparison with the approaches of Pinto et al. (2017) and Tessler et al. (2019) in the main body of the paper can provide more insights. Hence, in the revised paper, we reorganized the experiment section. We moved the the numerical comparison with the approaches of Pinto et al. (2017) and Tessler et al. (2019) into the main body of the paper, and moved other experimental results into Appendix due to the page limit.

To Question 2.

We agree with the reviewer. The relationship between those two types of uncertainty sets does not impact the analysis. We deleted this discussion in the revised version.

To Question 3.

We agree with the reviewer that Tessler et al. (2019) proved the existence of an optimal policy for the action robust setting under probabilistic execution and showed the equivalence between this setting and one special robust MDP setting.

However the equivalent robust MDP setting in Tessler et al. (2019) is different with the setting in Iyengar et al. (2005). The equivalent robust MDP setting in Tessler et al. (2019) includes both the reward uncertainty and the transition probabilities uncertainty, while the Robust MDP setting in Iyengar et al. (2005) only considers the uncertainty in transition probabilities. Thus, the robust Bellman equations in two papers are different and the results in Iyengar et al. (2005) can not directly apply in action robust setting.

To weakness 1.

Although the probabilistic action robust MDP was discussed in Tessler et al. (2019), no theoretical guarantee on sample complexity or regret was provided in Tessler et al. (2019). The methods in Tessler et al. (2019), i.e. PR-PI and soft PR-PI, iteratively repeat two stages: (i) given a fixed adversary policy, it calculates the optimal counter policy, and (ii) update the adversary policy against the updated counter policy. Stage (i) may be performed by any MDP solver. Tessler et al. (2019) shows the convergence of this iterative approach. However, this form of iteratively updating requires repeating stage (1), i.e. repeatedly solving MDP to find the optimal policy. It is sample inefficient and computational inefficient.

In this paper, we fill this gap by designing a provably efficient action robust RL algorithm. Instead of modeling the problem as a Markov Game, we solve the minimax problem by the iteration of the proposed action robust Bellman equation. In our method, the adversary policy and agent policy are updated simultaneously. We update the adversary policy in each episode even if the agent policy is not optimal under the current adversary policy. At the same time, we update the agent policy in each episode even if the current adversary policy does not minimize the rewards. We prove that the adversary policy and agent policy gradually converge to the solution together. By this, ARRLC directly learn the robust policy. We further prove the efficiency and sample optimality of ARRLC.

To weakness 2.

We updated the discussion on the related works in the revised version (marked in red color). The main update are: (1) the previous works on action robust RL fail to design efficient algorithm with theoretical guarantee on sample complexity or regret. We develop a minimax sample efficient algorithm and fill in this gap. (2) the works on sample complexity guarantees for episodic tabular RL can not directly use in action robust MDP with small technical changes. We develop new adversarial trajectory sampling and action robust value iteration method in the proposed algorithm, and new techniques to bound the sum of variance so that our algorithm suits for action robust MDPs. (3) the efficient multi-agent RL algorithms, such as (Liu et al., 2021; Jin et al., 2021), can be used to solve the action robust optimal policy but are not minimax optimal. They are a factor of $A$ or $H^2$ above the minimax lower bound. Our algorithm ARRLC is minimax optimal.

To weakness 3.

We fixed typos in the revised version and changed the position of Algorithm 1. We agree with the reviewer that the original uncertainty set definition in Eq. (3) may by confusing. We have rewritten it in a form as the reviewer suggested.

To weakness 4.

Regarding the algorithmic approach, Tessler et al. (2019) requires repeatedly solving the optimal policy given a fixed adversary policy, which is sample inefficient and computationally inefficient. Our algorithm solves the robust problem by the iteration of the proposed action robust Bellman equation. The proposed algorithm directly learns the robust policy and simultaneously updates the adversary policy and the agent policy without fixing any of them.

Dear reviewer wBWc,

Thank you for dedicating your time to reviewing our manuscript. Your insights have been invaluable, and we've crafted a detailed response to address the points you raised and polish the paper accordingly. We're confident that our responses and modifications have effectively addressed your concerns. With these changes in mind, we hope you might reconsider and adjust your evaluation of our work.

Should there be any remaining issues, we're more than ready to provide further clarifications. As the rebuttal phase is nearing its deadline, we're looking forward to engaging in a timely discussion. Thank you again for your expertise and guidance!