Efficient Action Robust Reinforcement Learning with Probabilistic Policy Execution Uncertainty
Authors: Guanlin Liu
Zhihan Zhou
Han Liu
Lifeng Lai
Venue: Accepted by TMLR ()

Abstract: Robust reinforcement learning (RL) aims to find a policy that optimizes the worst-case performance in the face of uncertainties. In this paper, we focus on action robust RL with the probabilistic policy execution uncertainty, in which, instead of always carrying out the action specified by the policy, the agent will take the action specified by the policy with probability $1-\rho$ and an alternative adversarial action with probability $\rho$. We show the existence of an optimal policy on the action robust MDPs with probabilistic policy execution uncertainty and provide the action robust Bellman optimality equation for its solution. Based on that, we develop Action Robust Reinforcement Learning with Certificates (ARRLC) algorithm that achieves minimax optimal regret and sample complexity.  Our results highlight that action-robust RL shares the same sample complexity barriers as standard RL, ensuring robust performance without additional complexity costs. Furthermore, we conduct numerical experiments to validate our approach's robustness, demonstrating that ARRLC outperforms non-robust RL algorithms and converges faster than the other action robust RL algorithms in the presence of action perturbations.

Published in Transactions on Machine Learning Research (08/2024)
Efficient Action Robust Reinforcement Learning with Prob- abilistic Policy Execution Uncertainty
Guanlin Liu
ginliu@radavis.co edu
University of California, Davis One Shields Avenue, Davis, CA 95616
Zhihan Zhou
ahihanchon@@..orrbunsttt...c.m
Northwestern University 633 Clark Street, Evanston, IL 60208
Han Liu
kanliu@hhorthuusstrmr.cc
Northwestern University
633 Clark Street, Evanston, IL 60208
Lifeng Lai
Iflai@rodavis..o edu
University of California, Davis One Shields Avenue, Davis, CA 95616
Reviewed on OpenReview: https: // openreview. net/ forum? id= 9sZs j
Abstract
Robust reinforcement learning (RL) aims to find policy that optimizes worst-case per- formance in the face of uncertainties. In this paper, we focus on action robust RL with the probabilistic policy execution uncertainty, in which, instead of always carrying out the action specified by the policy, the agent will take the action specified by the policy with probability 1 - p and an alternative adversarial action with probability p. We show the existence of an optimal policy on the action robust MDPs with probabilistic policy exccu- lion uncertainty and provide the action robust Bellman optimality equation for its solution. Based that, develop Action Robust Reinforcement Learning with Certificates (AR- RLC) algorithm that achieves minimax optimal regret and sample complexity. Our results highlight that action-robust RL shares the same sample complexity barriers as standard RI, ensuring robust performance without additional complexity costs. Furt hermore, we conduct numerical experiments to validate our approach's robustness, demonstrating that ARRLC outperforms non-robust RL algorithms and converges faster than the other action robust RL algorithms in the presence of action perturbations.
1
Introduction
Reinforcement learning (RL), a framework for solving control-theoretic problem that involves making deci- sions over time under an unknown environment, has many applications variety of scenarios (Zhao et al., 2018 Nazari al. 2018 O' Kelly et al. 2018 Liu et al. 2020 However, the solutions to standard RL meth- ods not inherently robust to uncertainties, perturbations, structural changes in the environment, which are frequently observed in real-world settings. A trustworthy reinforcement learning algorithm should be competent in solving challenging real-world problems with robustness against perturbations and uncertain- ties. Robust. RL aims to improve the worst-case performance of algorithms deterministically or statistically in the face uncertainties in different MDP components, including observations /states (Zhang et al.) 2020a
Sun al.] 2022), actions (Tsssler al.] 2019 Klima al.) (201)) transitions (Nilim El Ghaoui 2005
Iyengar 2005 Tamar al. 2014
Wang & Zou 2021), and rewards (Huang & Zhu 2019 Lecarpentier &
Rachelson, 2019

---

Published in Transactions on Machine Learning Research (08/2024)
In this paper, we consider action uncertainties, also called policy execution uncertaintics, and probabilistic uncertainty set proposed in Tessler et al. (2019). Robust RL, against action uncertainties focuses on the discrepancy between the actions generated by the RL agent and the conducted actions. Taking the robot control as an example, such policy execution uncertainty may come from the actuator noise, limited power range, or actuator failures in the real world. Taking the medication advice healthcare as another example, such policy exccution uncertainty may come from the patient's personal behaviors such as drug refusal, forgotten medication, or overdose etc.
To deal with the policy execution uncertainty, robust RL methods (Pinto et al., 2017 Tessler et al. 2019 adopt the adversarial training framework [Goodfellow et al.) 2014] Madry et al. 2018) and assume an adversary conducting adversarial attacks to mimic the naturalistic uncertainties. Training with an adversary can be formulated as a zero-sum game between the adversary and the RL agent. However, these interesting works do not provide theoretical guarantee on sample complexity or regret. In this paper, we aim to fill this gap.
The approaches in Pinto et al. 20177) and Tessler al. (019 iteratively apply two stages: (i) given fixed adversary policy, it calculates the agent's optimal policy; and (ii) update the adversary policy against the updated agent's policy. The repetition of stage (i) requires repeatedly solving MDP to find the optimal policy, which is sample inefficient. Motivated by the recent theoretical works on transition probability uncertainty that use the robust dynamic programming method [yengar (2005) and achieve efficient sample complexity Wang & Zou [2021); Panaganti & Kalathil (2022); Xu et al. (2023), we introduce the action robust Bellman equations and design sample efficient algorithms based on the action robust Bellman equations. Our methods simultancously update the adversary policy and agent's policy instead of updating one after another is converged. Our major contributions are summarized follows:
We show that the robust problem can be solved by the iteration of the action robust Bellman optimality equations. Motivated by this, we design two efficient algorithms.
We develop a model-based algorithm, Action Robust Reinforcement Learning with Certificates (AR- RLC), for episodic action robust MDPs, and show that it achieves minimax order optimal regret and minimax order optimal sample complexity.
We develop a model-free algorithm for episodic action robust MDPs, and analyze its regret and sample complexity.
We conduct nunerical experiments to validate the robustness of our approach. In our experiments, our robust algorithm achieves a much higher reward than the non-robust RL algorithm when being tested with some action perturbations; and our ARRLC algorithm converges much faster than the robust TD algorithm in [Kima et al. 2019
2
Related work
We mostly focus on papers that are related to sample complexity bounds for the episodic RL. and the two- player zero-sum Markov game, and action robust RL, that are close related to our model. We remark that there are also related settings, e.g., infinite-horizon
horizon discounted MDP (Li et al. 2020: He et al. 2021), robust
RI. with other uncertainties [Tyengar 2005
Lecarpentier & Rachelson 2019 Zhang et al. 2020al] Wang &
Zou 2021), robust offline RL (Guo et al. 2022 Shi & Chil (202)), adversarial training with generative RL
model (Zhou et al., | Yang al.) 2022 P Panaganti & Kilathil 2022 Xu et al., 2023 Shi al. 2023)
adversarial attacks on RL (Zhang et al. 2020b Liu & Lai| 2021 Sun et al. 2021). etc. Most of robust RL
papers considered the robust MDP setting, which have been proposed to handle these problems by letting the transition probability vary in an uncertainty (or ambiguity) set. Table proviidss the sample complexity comparisons of our result. with that of the existing Robust MDP works.
Action robust R.L. Pinto et al. (017)) introduces robust adversarial reinforcement learning to address the generalization issues reinforcement learning by training with destabilizing adversary that applies distur- bance forces the system. Tessler et al. (2019) introduces two new criteria of robustness for reinforcement
2

---

Published in Transactions on Machine Learning Research (08/2024)
Sample
Algorithm
Uncertainty
Sample from
complexity
(2+pp) p²
Transition
Yang al.
2022
Generative environment
probability
Transition
Panaganti & Kalathil
2022
s AHH
Generative environment
e²
probability
Xu et al.
2023
SAH
Transition
Generative environment
probability
Transition
Wang & Zou 2021
Asymptotic
Online environment
probability
Policy execu-
This work
SAM*
Online environment
tion
(Non-robust) Zhang et al. 2020c
Lower
bound
SAM e²
Table 1: Sample complexity comparisons of previous results and our results, where S, A are the size of the state space and action space, H the length of the horizon, K the number of episodes, P is the uncertainty parameter, and e is the level of suboptimality.
learning in the face of action uncertainty. We follow its probabilistic action robust MDP (PR-MDP) in which, instead of the action specified by the policy, alternative adversarial action is taken with probability p. They generalize their policy iteration approach to deep reinforcement learning (DRL) and provide extensive experiments. A similar uncertainty setting was presented in Klima et al. (2019), which extends temporal difference (TD) learning algorithms by a new robust operator and shows that the new algorithms converge to the optimal robust Q-function. However, no theoretical guarantee on sample complexity or regret is provided in these works. We develop a minimax sample efficient algorithm and fill this gap.
Sample complexity bounds for the episodic RL. There a rich literature on sample complexity
guarantecs for episodic tabular RL, for example (Kearns & Singh 2002 Strehl et al.) 2006; Auer et al.
2008 Azar et al. 2017 Dann et al., 2017 Jin et al. 2018 Dann et al. 2019
Simchooitz & Jamieson) 2019
Zhang et al.) 2020c 2021). However, these methods can not be directly applied in action robust MDP with small technical changes. Most relevant to our paper is the work about policy certificates (Dann et al. 2019). The algorithm ORLC in Dann et al. 2019) calculate both the upper bound and lower bound of the value functions, and outputs policy certificates that. bound the sub-optimality and return of the policy. Our proposed ARRLC shares a similar structure with ORLC, but we develop new adversarial trajectory sampling and action robust value itcration method in ARRLC, and new techniques to bound the sum of variances that our algorithm suits for action robust MDPs.
Sample complexity bounds for the two-player zero-sum Markov game. Training with an adversary can naturally be formulated as a zero-sum game between the adversary and the RL agent. Some sample efficient algorithms for two-player zero-sum Markov game can be used to train the action robust RL agent. The efficient multi-agent RL algorithms (Liu et al., 2021 Jin al.] 2021) can be used to solve the action robust optimal policy but are not minimax optimal. They are factor of A or H² above the minimax lower bound. Our algorithm ARRLC is minimax optimal.
3 Problem formulation
Tabular MDPs. We consider tabular episodic MDP M (.,,H,, where S is the state space with [S] 5, A is the action space with A = A, H H is the number of steps in each episode, P is the transition matrix so that (- a) represents the probability distribution over states if action a is taken for state at step h E [H], and RA : S x A + [0, 1] represents the reward function at the step h. In this paper, the probability transition functions and the reward functions can be different at different steps.
The agent interacts with the MDP in episodes indexed by k. Each episode is a trajectory (sf, at, r.., st "
at rH) of H states sf E S, actions Ot A, and rewards r E [0, 1]. At each step
3

---

Published in Transactions on Machine Learning Research (08/2024)
h [H] of episode k the agent observes the state si and chooses action at. After receiving the action, the environment generates random reward rf E [0, 1] derived from distribution with mean RĄ (s% of)) and next state s/4+ that is drawn from the distribution Pa a.). For notational simplicity, we assume that the initial states of 81 are deterministic in different episode k.
A (stochastic) Markov policy of the agent is a set of H maps :: := {TA : S + Aahhem where Aa denotes the simplex over A. We use notation Tr (als) to denote the probability of taking action a in state s under stochastic policy т at step h. A deterministic policy is a policy that maps each state to a particular action. Therefore, when is clear from the context, we abuse the notation Ty (s) for deterministic policy æ denote the action a which satisfies TA (alss) 1.
Action robust MDPs. In the action robust case, the policy execution is not accurate and lies in some uncertainty set centered on the agent's policy и. Denote the actual behavior policy by क where म E (x))) and (TT) is the uncertainty set of the policy execution. Denote the actual behavior action at episode k and step by af, where at ~ #h. Define the action robust value function of a policy т as the worst-case expected accumulated reward over following any policy in the uncertainty set 11(T) centered on a fixed policy x
H
Vg
min E. =Ell(T)
Σ
Ra
(sw (aeeaan)) 1sh =
V represents the action robust value function of policy a at step h. Similarly, define the action robust Q-function of policy m:
H Σ
(T(saa)= min E; #Ell(T)
Rw ane = s, an
(2)
L
The goal of action robust RL is to find the optimal robust policy xt that maximizes the worst-case accumu- lated reward: x² max, VTT Vs E S. We also denote V and Q" by V and Q"
Probabilistic policy execution uncertainty set. We follow the setting of the probabilist action ro- bust MDP (PR-MDP) introduced in (Tessler et al.] (201)) to construct the probabilistic policy execution uncertainty set. For some 0 I p I 1, the policy exccution uncertainty set is defined as:
(T) = { : Vs, wh, (+Is) E A such that (-1s) = (1 - () + pm
(3)
The policy execution uncertainty set can also be expressed as II((T) = (1 - p) + ((A SXH
In this setting, an optimal probabilistic robust policy is optimal w.r.t. scenario in which, with probability at most p. an adversary lakes control and performs the worst possible action. We call n' the adversarial policy. For different agent's policy x, the corresponding adversarial policy x' that minimizes the cumulative reward may be different.
Additional notations. We set = (0g(2SAHK/)) for 8> 0. For simplicity of notation, we treat P as a linear operator such that Vs, == Fg Vs*',, and we define two additional operators and W as follows: [Dr. (1)) == Q(s, and
Vn- = Σ (V++1(8') - ())
(Pa( - ((P.
4 Existence of the optimal robust policy
For the standard tabular MDPs, when the state space, action space, and the horizon are all finite, there always exists an optimal policy. In addition, if the reward functions and the transition probabilities are known the agent, the optimal policy can be solved by solving the Bellman optimality equation. In the following theorem, we show that the optimal policy also always exists in action robust MDPs and can be solved by the action robust. Bellman optimality equation.
4

---

Published in Transactions on Machine Learning Research (08/2024)
Proposition 4.1 If the uncertainty set of the policy exccution has the form in equation 3 the following perfect duality holds for all E S and all [H]:
H Σ
H
Ry (sw, aw)]sn = 3.
max min a (F)I((R)
ER
Ra ax = = min max Ex (Elle(a) x
Σ
(4)
There always erists deterministic optimal robust policy x². The problem can be solved by the iteration of the action robust Bellman optimalily equation on h H, ... 1. The action robust Bellman equalion and the action robust Bellman optimality equation are:
(T)(s) (1 p)[D nq QM((s) pmin (T,
@N(s, a) - R2 (8, a) + IPA V (s,,,a))
(5)
(8)+((8) = O, Vs E S.
(i)(s) (1 p) max (7 a) + pmin (s, BEA () = (s, a) + P
(6)
(i) = 0, Vs ES
We define
C%
(P() -r.
= Ex Σ
Ry (swssaa)))ls as)) =
(7)
Since (-1s) = p-)s + (-1s,, min is equivalent to minggnp(s)) when fixing л. The perfect
duality of the control problems in equation 4 is equivalent to max, ming' C% (P() ) ming' max, 0% (s). We provide the dctailed proof of the perfect duality and the existence of the optimal policy in Appendix B
Our proposed model-based algorithu Section and model-free algorithu in Appendix D are based on the action robust Bellman optimality equation. Using the iteration of the proposed action robust Bellman equation solve the robust problem simultancously update the adversary policy and agent policy and avoid inefficient alternating updates.
5 Algorithm and main results
In this section, we introduce the proposed Action Robust Reinforcement Learning with Certificates (AR- RLC) algorithm and provides its theoretical guarantee. The pseudo code is listed in Algorithm [ Here, we highlight the main idea of our algorithm. Algorithm [ trains the agent in a clean (simulation) environment and learns policy that performs well when applied to perturbed environment with probabilistic policy execution uncertainty. To simulate the action perturbation, Algorithm probability p. To learn the agent's optimal policy and the corresponding adversarial policy, Algorithm com-- putes an optimistic estimate Q of Q" and a pessimistic estimate Q of Q=*. Algorithm uses the optimistic estimates explore the possible optimal policy and uses the pessimistic estimates to explore the possible adversarial policy म. As shown later in Lemma 6.2 V > V* y V holds with high probabilities. The optimistic and pessimistic estimates V and V can provide policy certificates, which bounds the cumulative rewards of the return policy z and V - V. bounds the sub-optimality of the return policy 7 with high probabilities. The policy certificates can give us some insights about the performance of x* in the perturbed environment with probabilistic policy execution uncertainty.
| chooses an adversarial action with
5.1 Algorithm description
We now describe the proposed ARRLC algorithm in more details. In each episode, the ARRLC algorithm be decomposed into two parts.
5

---

Published in Transactions on Machine Learning Research (08/2024)
Algorithm 1 ARRLC (Action Robust Reinforcement Learning with Certificates)
Initialize (s(5) H - + 1, (8, a) H h + 1, (s) O, (v, a) 0, fa(s, a), Na a) = 0 and
(s, s') = 0 for any state 8 E S, any action a E A and any step h E [H]. VH+1(s) = (u+1(s) = and QH+1 a) = H+ (s) 0 for any and A H. for episode k 1, 2. K do
for step h = 1,2,..... ................................ H do
Observe sh 5: Set (s) = arg max, Qn( (s) = arg arg min, Q (s) # = (1- =11=11 p) + +
Take action of # (11s))-
7:
Receive reward 1 and observe +
8:
Set (s a <- Nn at) + +1, (s a +x+))) No a st +11
9:
Set (o a + (6 at) + (rh- - - (
10:
Set P att (o at (
11:
end for
12:
Get policy म" with certificates Ia = (+7),,,, (+t)) and ex = 1Ixl
13:
if EN < then
14:
A f Cg and yout < nh.
15:
end if
16:
for step h = H, H- 1, ,...., do
17:
for each (s, E S x A with (s, > 0 do
Set () 24 r2 K[ V n41 (z.a))
(x.a)
A Pv(Vo-I [oa.
(74
18:
Na(o,)
Nx(a,))
H
+ (N,(),a)
(s,0) t min(H h + (s, + PVV (s, + a).
19:
20:
(s,a)) < max (0x
P. P. -
(s, a)},
21:
Th (s) = arg max, (s, T k- (s) = arg
aar min, Q (s,a).
22:
Vn(s) + (1 - -p) (s. u
(s)) + (s. (s))
23:
(s) + (1 - p] (, / (s) + p0, ( (s)).
24:
end for
25:
end for
26:
end for
27: Return out
Line 3-11 (Sample trajectory and update the model estimate): Simulates the action robust MDP, executes the behavior policy ã, collects samples, and updates the estimates of the rewards and the transitions.
Line 16-25 (Adversarial planning from the estimated model): Performs value iteration with bonus to estimate the robust value functions using the empirical estimate of the transition P, computes new policy ग that is optimal respect to the estimated robust value functions, and computes new optimal adversarial policy I respect to the agent's policy म.
At a high-level, this two-phase policy is standard in the majority of model-based RL algorithms AAzr et al. 2017 Dann et al. 2019). Algorithm [ shares similar structure with ORLC (Optimistic Reinforcement Learning with Certificates) in Dann et al. (2019) but has some significant differences in line 5-6 and line 18-23. The first main difference is that the ARRLC algorithm simulates the probabilistic policy execution uncertainty by choosing an adversarial action with probability p. The adversarial policy and the adversarial actions are computed by the ARRLC algorithm. The second main difference is that the ARRIC algorithm simultaneously plans the agent policy से and the adversarial policy z by the action robust Bellman optimality equation.
These two main difference bring two main challenges in the design and analysis of our algorithm.

---

Published in Transactions on Machine Learning Research (08/2024)
(1) The ARRLC algorithm simultancously plans the agent policy and the adversarial policy. However the planned adversarial policy is not necessarily the true optimal adversary policy towards the agent policy x because of the estimation error of the value functions. We carefully design the bonus items and the update role of the value functions so that (s) 2 ( (s) 2 V (s) 2 (s) and On (8, a) 2 (s,ss 2 (5, a) 2 2n (s, a) hold for all 8 and a.
(2) A crucial step in many UCB-type algorithms based on Bernstein inequality is bounding the sum of variance of estimated value function across the planning horizon. The behavior policies in these UCB-type algorithms are deterministic. However, the behavior policy in our ARRLC algorithm is not deterministic due to the simulation of the adversary's behavior. The total variance is the weighted sum of the sum of variance of estimated value function across two trajectories. Even if action #(sh) or I(s)) is not sampled at state s it counts in the total variance. Thus, the sum of variance no longer simply the variance of the sum of rewards per episode, and new techniques are introduced. For example, the variance of V + V can be connected to the variance of C =z" iP, where n is the optimal policy towards the adversary policy x² with ** (s) = arg max, C " ((s) Then the variance of C _ ip can be bounded via recursion on the sampled trajectories.
5.2 Theoretical guarantee
We define the cumulative regret of the output policy Th at each episodes is as Regret(KK) (V VIT (sf)).
Theorem 5.1 For any E (0, 1], letting 1 = log(2SAHK/0), then with probability at least 1 1-5, Algorithm achieves:
+ (s1) - VT"""((S (s1) c, if the namber of episodes K (/
Regret(K)) = EK= - VT (st)) & K AHH
For small S H/S, the sample complexity scales as 0(SAF3 For the case with a large number of episodes K 2 53 AHAHS, the regret scales as O(VSAH&K)) For the standard MDPs, the information- theoretic sample complexity lower bound ((SAH /e2) provided in Zhang et al. (2020c) and the regret lower bound is ((VSAH**) provided in Jin et al. (2018). When P = O, the action robust MDPs is sample complexity lower bound and the
equivalent the standard MDPs. Thus, the mffommtion-thcore regret. lower bound of the action robust MDPs should have same dependency on S, A, H, K or The lower bounds show the optimality of our algorithm up to logarithmic factors. The action-robust reinforcement learning maintains the samn sample complexity barriers traditional RL, which indicates that robustness can be achieved without additional sample complexity overhead.
6 Proof sketch
In this section, we provide sketch of the proof, which will highlight our the main ideas of our proof. First, we will show that (s(s) Z (s) 2 (s) 2 (s) hold for all s and a. The regret can be bounded by Vi-K, and then be divided by four itemss, each of which can be bounded separately. The full proof can be found in the appendix contained in the supplementary material.
We first introduce a few notations. We use 2 vh, N P and 0% to denote the values of Qn. V.. V..Vn,Q,4. V,, max(N,, 17, Pr, Fh and 6g in the beginning of the k-th episode in Algorithm 1
6.1 Proof of monotonicity
We define g to be the event where
2F a)
7t (s, ((N)(s))))
(s) - Rn) <
(8)

---

Published in Transactions on Machine Learning Research (08/2024)
holds for all (s, E Ax [H] []]. We also define PV to be the event where
[PA - Pa) (i) SV
2W 2Wp
Ag V (s, (5, a)
THe (s,
(9)
and
2 V
pa h+1 (8,
(8,
(PA - Ps) S
7Hc
(10)
(s, (s,
hold for all (s,a,h,k) S AX [ [K].
Event E means that the estimations of all reward functions stay in certain neighborhood the true values. Event gPV represents that the estimation the value functions at the next step stay in some intervals. The following lemma shows 8 and g hold with high probability. The analysis will be done assuming the successful event E NvPV holds in the rest of this section.
Lemma 6.1 IE n (EE)) 1- 35.
Lemma 6.2 Condilioned on event E NEPV (x))) 2 (3)) 2 VT ( kh(s) and ( a) 2 (7( 2 QR (s, a) 2 0f, (s) hold for all (s, h, E 8 A [M] x [K].
6.2 Regret analysis
We decompose the regret and analyze the different terms. Set (s, = 88 py (xtt1zt
32
Ni
(s.a
SH where k is the optimal policy towards the adversary policy x²t with (s) = arg max, C -. .p (8)
(s,a))
We set
K H
M
Da (V M
[+1
P. ( - Vl ( at)).
(11)
k= A=1
M2 Σ
Day
(a h+1 ((h) PL K+1 (sh
(12)
H
k=1h=1
K Σ
M3
PV h+1 (sh att (V (i
(13)
k=1h=1
K H
(SH + SH2) NE
M4
+ +Da
(14)
Here Mj and M2 are the cumulative sample error from the random choices of the adversarial policy or agent's policy. M3 is the cumulative sample error from the randomness of Monte Carlo sampling of the next state. M4 is the cumulative error from the bomus item 0. Lemma 6.3 shows that the regret can be bounded by these four terms.
Lemma 6.3 With probabilily at least 1 (S + 5)ō
Regret K) < - vt((t) S 21 + M2 + M3 + M4).
(15)
We bound each of these four items separately.

---

Published in Transactions on Machine Learning Research (08/2024)
Lemma 6.4
With probability at least 1 6, MM & HV2HKI.
Lemma 6.5
With probability at least 1 8, M22 I V2HKi.
Lemma 6.6
With probability at least 1 8, Maal S Hv2HKL
Lemma 6.7 With probability at least 1- 26, |Mal < 2 ANS AA 6vSAH.
Putting all together. By Lemmas 6.3
6.4
6.5
6.6
and 6.7
we conclude that, with probability 15
Rkg <O(V K. AH.
(16)
By rescaling 6, log( 2SAHK
S et for some constant e and we finish the proof of regret. As Ex= (V
8/(
(st)) & O(VSAHOK, AHH we have that (i1 vi"" (s1) s ming (st) ((() S
SAHS K
++
5² S and we finish the proof of sample complexity.
K
7 Model-free method
Algorithm 2 Action Robust Q-learning with Hoeffding Confidence Bound (ARQ-H)
Set 04 = H41
#+1
Initialize (*()) = H - + 1, Qn (x,0) a) = - h + 1, Vn (s) = 0, Q (8, = 0, fn(s, a):
(s) = 0 for any state S, any action A and any step h E [H]. V V*+i(s) (s) 0 and
QH+1(5,)) a) = ( = 0 for all and a. = H. Initial policy // (als) and (als) = 1/A for any
stale 8, action and any step h E [H]. for episode k = 1,2, K do
for step = 2......... H do
Observe 5 Set a = arg max, (5t, a) at argmin, a), = - and (*(a)(s)) = p.
Take action of ~ (+())
Receive reward r and observe 4+1
Set 6 (n af) Nn a
+ 1; b. /H.//..
Qn az) (1- an) a
+ az + ( be),
Qg ( a t (1-a1) (sh, a + (r( ( - bt).
Set (stt) arg max, (sh a), In (stt arrgging Q (sh ( aa.
(*())) + min(Va(s)),
p)Qx ( +s()))))) + p k+1 (x)))) (s()) +- max (b)) (1 p)Q, (0h - ( + +p2, (bhh
if V (s > (1 0), (5 7 (5))) + p2 (s), h (s))) then
++1
#b+1 =
end if end for end for
Return #
In this section, we develop model-free algorithm, called Action Robust Q-learning with Hoeffding confidence bound (ARQ-H), and analyze its thcoretical guarantec. The pscudo code is listed in Algorithm 2 Here, we highlight the main idea of Algorithm 2 Algorithm 2 follows the same idea of Algorithm [ which trains the agent in a clean (simulation) environment and learns a policy that performs well when applied to a perturbed environment with probabilistic policy execution uncortainty. To simulate the action perturbation, 2 chooses an adversarial action with probability p. To learn the agent's optimal policy and the corresponding adversarial policy, Algorithm computes optimistic estimate Q of Q* and pessimistic
Algorithm
9

---

Published in Transactions on Machine Learning Research (08/2024)
estimate Q of Q=a Algorithm uses the optimistic estimates to explore the possible optimal policy т and uses the pessimistic estimmaees to explore the possible adversarial policy л. The difference is that Algorithm uses model-free method to update Q and V values.
Here, we highlight the challenges the model-free method compared with the model-based method. In the model-based planning, we perform value iteration and the Q values, V values, agent policy मे and adversarial policy H are updated on all (s,a), a). However, in the model-free method, the Q values and V values are updatod only on (sh a which are the samples on the trajectories. The variances of the Q values and V values in model-free method are larger than the model-based method. Compared with the modell-aseed method, the update of the Q values and V values in the model-free method is slower and less stable.
To deal with this challenges, we design a special update rule of the output policy. In line 14-16, Algorithm 2 does not update the output policy until the lower bound on the value function of the new output policy is improved. By this, the output policies are stably improved after every update. The adversary policy is still updated at each episode.
We provide the regret and sample complexity bounds of Algorithm 2 in the following:
Theorem 7.1 For any 8 E (0, letting log(2SABHK/)), then with probability at least 1 - 6, Algo-
rilhm 2 achieves:
if the number of episodes K 2 0/SAH2// SAIf//e). Regre((k)=Eiii
(i((s) -
(51) S "(1"
- VT* (st)) < OL SAH
The detailed proof is provided in Appendix E The model-free method is more computationally efficient than the model-based method but is less sample efficient.
8 Simulation results
We use OpenAl gym framework [Brockman et al. 2016), and consider two different problems: Cliff Walking, a toy text environment, and Inverted Pendulum, a control enviromment with the MuJoCo (Todorov et al. 2012) physics simulator. We set H 100. To demonstrate the robustness, the policy is learned in a clean environment, and is then tested in the perturbed environment. Specifically, p is the uncertainty parameter used during training. Then, during testing, set a probability p such that after the agent takes action, with probability p, the action is chosen by an adversary. The adversary follows fixed policy. A Monte-Carlo method is used to evaluate the accumulated reward of the learned policy in the perturbed environment. We take the average over 100 trajectorics.
Inverted pendulum. The inverted pendulum experiment is a classic control problem RL. An inverted pendulum is attached by a pivot point to a cart, which restricted to linear movement in a plane. The cart can be pushed left or right, and the goal is to balance the inverted pendulum the top of the cart by applying forces on the cart. The observation space of InvertePPendulums along the linear surface, vertical angle of the pole on the cart, linear velocity of the cart, angular velocity of the pole on the cart. We ignore the position of the cart along the linear surface. The vertical angle of the pole on the cart is discretized to 10 intervals between [- inf, -0.2, -0.1, 0.05, - -0.025, 0, 0.025, 0.05, 0.1, 0.2, inf]. The linear velocity of the cart. discretized to 4 intervals between [- inf, 0.05, 0, 0.05, inf]. The angular velocity of the pole on the cart discretized to intervals between [- inf, 00.05, 0, 0.05, inf]. A reward of +1 is awarded for each time step that the inverted pendulum stand upright within a certain angle limit. The fixed adversarial policy in the inverted pendulum environment is force of 0.5 N in the left direction.
has 4 dimensions: position of the cart
Cliff walking. The cliff walking experiment is classic scenario proposed in Sutton & Barto (0018p. The game starts with the player al location [3. 0] of the 4 x 12 grid world with the goal located at [3, 11]. A cliff runs along [3, 10). If the player moves to a cliff location, it returns to the start location and receives a reward of 1000. For every move which does not lead into the cliff, the agent receives reward of 11 The player makes moves until they reach the goal. The fixed adversarial policy the cliff walking environment is walking step to the bottom.
10

---

Published in Transactions on Machine Learning Research (08/2024)
(a) p = 0.1, p = 0.2, Cliff Walking
HAN.
(b) p= 0.2, p 0.2, Cliff Walking
(c) p= 0.1, p = 0.2, Inverted Pendulum
APRIC
Make
(d) p 0.2, p= 0.2, Inverted Pendulum
Evaluation returns during training. We plot the accumulated reward of each algorithms under different p and different environment. We set p 0.2 for our algorithm, which is the uncertainty parameter used during training.
Figure 1:
To show the robustness, compare our algorithm with non-robust RL algorithm that is ORLC (Optimistic Reinforcement Learning with Certificates) in Dann et al. (2019). It can be seen that overall our ARRLC algorithm achieves a much higher reward than the ORLC algorithm. This demonstrates the robustness of our ARRLC algorithm to policy execution uncertainty. To show the efficiency, we compare our algorithm with the robust TD algorithm Klima et al. (2019), which can converge the optimal robust policy but has no theoretical guarantee on sample complexity or regret, the RARL algorithm in Pinto et al. (2117) and the PR-PI algorithm in Tessler et al. (2019), which model the robust problem zero-sum game and alternating update the agent policy and adversary policy. In our implementation, Pinto et al. (2017) fixes one policy and updates another for 25 episodes, then alternatively updates another in the next 25 episodes. (Tessler et al. 2019) does not alternate the updating until the current policy is converged. Figure 1 shows the efficiency of our ARRLC algorithm. ARRLC algorithm more stable than the other algorithms. Compared with our model-free ARQ-H algorithm, the mosel-based ARRIC algorithm is more stable and more efficient. The shaded areas shows the statistical variance, since the evaluated rewards are averaged over 100 trajectories. Our robust algorithm ARRLC has lower variances compared with the others.
11

---

Published in Transactions on Machine Learning Research (08/2024)
We provide additional experimental results in Appendix A In these additional experiments, implement the ablation study by setting different, p and and try different adversary policies in the testing environment. We also perform comparison experiments in which we use the learned worst-case policies to disturb the different robust agents.
9 Conclusion and Discussion
In this paper, we have developed novel approach for solving action robust RL problems with probabilistic policy execution uncertainty. We have theoretically proved the sample complexity bound and the regret bound of the algorithms. The upper bound of the sample complexity and the regret of proposed ARRLC algorithm match the lower bound up to logarithmic factors, which shows the minimax optimality of our al- gorithm. In addition, our results reveal that action-robust reinforcement learning maintains the same sample complexity barriers as traditional RL. This finding underscores the efficiency of our approach, indicating that robustness can be achieved without additional sample complexity overhead. Moreover, we have carried out numerical experiments to validate our algorithm's robustness and efficiency, revealing that ARRLC surpasses non-robust algorithms and converges more rapidly than the robust TD algorithm when faced with action perlurbations.
The current theoretical guarantee on the sample complexity and regret of our algorithms are derived for the tabular setting. In the future work, we will explore action robust RL contimuous state or action space. Studying efficient. action robust. RL with function approximation also an important direction pursue. For this purpose, two insights from our work might be useful: (1) The adversary policy and the agent's policy can be simultancously updated to efficiently sample trajectories; (2) The adversary policies each episode do not necessarily need be the minimum over the actions, approximation of the minimum also works. Based on these insights, a policy-gradient method could potentially be designed to handle the continuous action space. We could use policy gradient method, such like PPO, to find an approximation of the adversary policy (the minimum over actions). In addition, similar to (Zoou et al. 2023 scalable uncertainty set is also an interesting direction.
considering a
10 Acknowledgement
The work of G. Liu and L. Lai was supported by the National Science Foundation under Grant CCF-2232900
References
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pp. 263 272, 2017.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv:1606.0155 2016.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for
episodic reinforcement learning, Advances in Neural Information Processing Systems, 30, 2017.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable rein- forcement learning. In International Conference on Machine Learning, pp. 1507-1516, PMLR, 2019.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint ar 14x.:4412.651 1572 2014.
Kaiyang Guo, Shao Yunfeng, and Yanhui Geng. Model-based offline reinforcement learning with pessimism- modulated dynamics belief. Advances in Neural Information. Processing Systems, 35:449-461 2022.
12

---

Published in Transactions on Machine Learning Research (08/2024)
Jiafan He, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for discounted mdps. Advances in Neural Informalion Processing Systems, 34:22288 34:22288-22300, 2021.
Yunhan Huang and Quanyan Zhu. Deceptive reinforcement learning under adversarial manipulations on cost signals. In Decision and Game Theory for Security: 10th International Conference, GameSec 2019, Stockholm, Sweden, Oclober 30 November 1, 2019, Proceedings 10, pp. 217 237. Springer, 2019.
Garud N. Iyengar. Robust dynamic programming. Mathematics of Operations Reseorch, 30(2):257 2802 may 2005.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:2110.14555, 2021.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning polynomial time. Machine learning, 49:209 232, 2002.
Richard Klima, Daan Bloembergen, Michael Kaisers, and Karl Tuyls. Robust temporal difference learning for critical domains. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '19, pp. 350-358 2019.
Erwan Lecarpentier and Emmanul Rachelson. Non-stationary markov decision processes, a worst-case approach using model-based reinforcement learning. Advances in neural information processing systems, 32, 2019.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asynchronous q- learning: Sharper analysis and variance reduction. Advances in neural information processing systems, 33: 7031 7043, 2020.
Guanlin Liu and Lifeng Lai. Provably efficient black-box action poisoning attacks against reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis model based reinforcement learning with self-play. In International Conference on Machine Learning, pp. 7001 7010. PMLR, 2021.
Xiao- Yang Liu, Hongyang Yang, Qian Chen, Runjia Zhang, Liuqing Yang, Bowen Xiao, and Christina Dan Wang. Finrl: A deep reinforcemeent learning library for automated stock trading in quantitative finance. Deep RL Workshop, NewrIPS 2020, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXic:0907.3740, 2009.
Reha Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. Reinforcement learning for solving the vehicle routing problem. In Advances in Newral Information Processing Systems, volume 31, 2018.
Arnab Nilim and Laurent El Ghaoui. Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(6):780-795, 2005.
Matthew O' Kelly, Aman Sinha, Hongscok Namkoong, Russ Tedrake, and John C Duchi. Scalable end-to- end autonomous vehicle testing via rare-event simulation. In Advonces in Neural Information Processing Systems, volume 31, 2018.
13

---

Published in Transactions on Machine Learning Research (08/2024)
Kishan Panaganti and Dileep Kalathil. Sample complexity of robust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statislies, pp. 9582-9600 PMLRR, 2022.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement
learning. In International Conference on Machine Learning, pp. 2817-2826, 2017.
Laixi Shi and Yuejie Chi. Distributionally robust model--ased offine reinforcement learning with near- optimal sample complexity, arXiv preprint KXw:2208.00766 2022.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, Matthieu Geist, and Yuejie Chi. The curious price of distribu- tional robustness reinforcement learning with a generative model. In Advances in Neural Information Processing Systems, volume 36, pp. 79903 79917, 2023.
Max Simchowitz and Kevin Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32, 2019.
Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. Pac model-free reinforcement learning. In Proceedings of the 23rd international conference on Machine learning, pp. 881 881,888,00 2006.
Yanchao Sun, Da Huo, and Furong Huang. Vulnerability-wware poisoning mechanism for online rl with unknown dynamics. In International Conference on Learning Representations, 2021.
Yanchao Sun, Ruijie Zheng, Yongyuan Liang, and Furong Huang. Who is the strongest enemy? towards optimal and efficient evasion attacks in deep RL. In International Conference on Learning Representations, 2022.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust mdps using function approximation. In Pro- ceedings of the 31st International Conference Machine Learning, volume 32, pp. 181-189, 2014.
Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and applications continuous control. In International Conference on Machine Learning, pp. 6215 6224. PMLR, 2019.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, pp. 5026 5033. IEEE, 2012.
Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty, Advances in Newral Information Processing Systems, 34:7193-722 10099 2021.
Tsachy Weissman, Erik Ordentlich, Gadiel Scroussi, Sergio Verdu, and Marcelo J Weinberger. Incqualities for the I1 deviation of the empirical distribution. Hewlett-Packard Labs, Tech. Rep, 2003.
Zaiyan Xu, Kishan Panaganti, and Dileep Kalathil. Improved sample complexity bounds for distributionally robust reinforcement learning. In International Conference on Artificial Intelligence and Stalistics, pp.
PMLR, 2023.
Wenhao Yang, Liangyu Zhang, and Zhihua Zhang. Toward theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, (0(6))322333244 2022.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho-Jui Hsieh. Robust deep reinforcement learning against adversarial perturbations on state observations. Advances in Neural Information Processing Systems, 33:21024 21037, 2020a.
Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu. Adaptive sward-poisooing attacks against reinforcement learning. In Proceedings of the 37th International Conference Machine Learning, volume 119, pp. 11225-11234 2020b.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free free reinforcement learningvia reference- advantage decomposition. Advances in Neural Information Processing Systems, 13:15198-15200 2020c.
14

---

Published in Transactions on Machine Learning Research (08/2024)
Zihan Zhang, Xiangyang Ji, and Simon Du Is reinforcement learning more difficult than bandits? near- optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pp. 4528-4553 PMLR, 2021.
Xiangyu Zhao, Long Xia, Liang Zhang, Zhuoye Ding, Dawei Yin, and Jiliang Tang. Deep reinforcement learning for page-wise recommendations. In Proceedings of the 12th ACM Conference Recommender Systems, pp. 95 103. ACM, 2018.
Ruida Zhou, Tao Liu, Min Cheng, Dileep Kalathil, P. R. Kumar, and Chao Tian. Natural actor-critic for robust reinforcement learning with function approximation, 2023.
Zhengqing Zhou, Zhengruan Zhou, Qinxun Bai, Linhai Qiu, Jose Blanchet, and Peter Glynn. Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 3331 3339, 13 15 Apr 2021.
15

---

Published in Transactions on Machine Learning Research (08/2024)
A Additional Numerical Results
A.1 Ablation study and more comparisons
In Section we compared our algorithm with the robust TD algorithm in (Klima et al. 2019 Here, we compare our algorithm with algorithms in (Pinto et al.) 2017 Tessler ct al. 2019). The method in (Tessler
et al. 2019) requires an MDP solver to solve the optimal adversarial poliey when the agent policy given and the optimal agent policy when the adversarial policy is given. The white-box MDP solver requires knowledge of the underline MDP so that there is no learning curve and sample complexity discussion in
(Tessler ct al. 2019). Thus, we implement the algorithms in (Pinto et al. 2017 Tessler et al.] 2019) with a Q-learning MDP solver, and compared the final evaluation rewards and the learning curve. In addition, we implement the ablation study by setting different & and p. In our experiments, the policy is learned in a clean environment, and is then tested in the perturbed environment. P is the parameter in algorithm when learning the robust policy. a can be considered as the agent's guess about the probability of a disturbance occurring. However, p is the probability that the perturb happens in the perturbed environment. In the perturbed environment, with probability p, the action is perturbed by an adversarial action.
Inverted Pendulum
Inverted Pendulum
Inverted Pendulum
Inverted Pendulum
Eveluctioo returns
Eveluation refumns
Evoluction returns
109
Evaluction returns 8 8 a 8 B
ARGLG
AT/LG
APRLC
Training episodes
Training episodes
Training episodes
Training episodes
(a) p = 0.1, p 0.1
(b) 0.2, p 0.1
(c) 0.2, = 0.2
(d) 0.2, 0.3
Inverted Pendulum
Inverted Pendulum
Inverted Pendulum
Inverted Pendulum
Evaluution relume #
Evaluetion relume
Evaluction returee
Evaluction returns 8
AVOLL
NeBLCC
Training epleodes
Training epieodes
Training epieodes
Training epleodes
(e) p 0.3, p 0.3
(f) 0.3, 0.4
(g) 0.4, p 0.4
(h) 0.5, P 0.5
Clff' Walking
Ciff Walking
Cliff Walking
Clift Walking
Exaluaaioo relums
En relurn
Evaluctton refurss
Evaluetion refums
-200
-230
-790
-100
17
-1500
Training apisodes
Training episodes
Training apisodes
Training opisodes
ii) p 0.1, 0.1
p 0.2, p 0.1
(k) 0.2, p 0.2
(1) p 0.2, 0.3
ClHff Walking
Cliff Walking
Cliff Walking
Clft' Walking
Evallutton returns
1000 -900
Evaluction retume
-042
Evalustion reture
Evaluction
1200
1120
-008
-100
2500
-
2500
nrainin episodee
Training epeedee
Training epieodes
Trainin eplsodee
(m) p == =0.3, p 0.3
(n) p 0.3, p = 0.4
(0) p 0.4, p= 0.4
(p) p 0.5, p p= 0.5
Figure 2: ARRLC VS. RARL
PPnto et al.
2017 VS. PR-PI
Tessler et al. 2019
16

---

Published in Transactions on Machine Learning Research (08/2024)
In Figure 2 algorithm RARL (Pinto et al. 2017 and "Tessler 19' stands for the algorithm PR-PI (Tessler et al. 2019). It can be seen that our ARRLC algorithm converges faster than the other algorithms. This demonstrates the efficiency of our ARRLC algorithm to learn optimal policy under policy exccution uncertainty.
we show the learning curves under different p and p. In the legend, 'Pinto 17' stands for the
Ablation study on InvertedPendulum--44 with fixed rho
rho: 0.0
rho: 0.3
rho: 0.4
rho: 0.5
Tesster ASALC
Tesseer
Tessier ABBLIC
Iespeer ABBLC
"essle AaBiC
ABALE
ABRLC
Rewerd
00
60-
20-
00
011
02
0.6
0.
0.
611
0.3
0.4
0.5
0/0
0.5
0.4
0.0
01
0.5
01
02
03
01
02
04
03
Figure 3: Ablation study InvertedPennuuuu--4 with fixed p.
In Figure 3 given the agents trained with fixed (rho), we test the agents in different disturbed environments with different p. In Figure 1 we compare the different agents trained with different p. The x-axis is the different choice of p or p. The y-axis is the final evaluation rewards.
Ablation study on InvertedPendulum-ee with fixed p
p: 0.0
0.2
0.3
p: 0.4
p: 0.5
Pinto 17 Teadier AM/LC
Fnto Tessler 19
Films -wele-10 10 ARTLC
Teadier ARALCC
AnnLC
Reward
00
02-
Arto 17
Anto Teeder 12
Teeder 30
ABALE
ASRLC
50
011
02
0.3 0.6
05
00
4.1
02
0.3 0.6
0.5
00
0.1
57
0.3
0.8
0.
02
0.3
0.4
0.5
0.0
0.
07
0.3
0.4
0.5
0.0
0.1
022
04
05
rho
tho
rho
/ho
rho
rho
Figure 4: Ablation study InvertedPenduluumvá with fixed p.
A.2 Robustness to different adversary
In this section, we consider different adversary policies include both the fixed policy in the main page and a random adversary policy. After the agent takes an action, with probability p, the random adversary will uniformly randomly choose an adversary action to replace the agent's action. In Figure 5 and Figure 6 'fix" represents that the actions perturbed by fixed adversarial policy during the testing, 'random' represents that the actions are randomly perturbed during the testing, p is the action perturbation probability.
The theoretical guarantee on sample complexity and regret of our algorithm relies on the assumption of known uncertainty parameter. However, in the experimental results shown in Figure g the parameter can mismatch with the true disturb probability. In Figure 5. we test the mismatch of the uncertainty parameter p and true uncertainty probability p. We train the agent with p = 0.2, but we use p = 0.1 proposed robust algorithm still outperforms the non-robust algorithm.
0.1 in the test. The
Since we do not know whether the fixed policy the random policy is the strongest adversary policy against the agent, a more direct comparison is to use the learned worst-case policy in different algorithms to do a crosa-comparison. We use the learned worst-case policies to disturb the different robust. agents. We report the final evaluation rewards in Table 2 We train our method in 2000 episodes and the approaches of Pinto let al. (2017): Tessler et al. (2019) in 30000 episodes. We set that p = p = 0.2. The ARRLC agent performs the best against three different adversaries and the ARRLC adversary impacts the most on three different agents.
17

---

Published in Transactions on Machine Learning Research (08/2024)
Inverted Pendulum
Inverted Pendulum
Inverted Pondulum
Inverted Pondulum
Evallaaioon relurns
Evalustion returns
Evalustion returns
10 10
0600
APRSO
ABSLO
ATRJ
Training episodes
Training episodes
Training episodes
Training episodes
p 0.1, p= 0.2, fix
(b) p
0.2, fix
(c) p
0.2, random (d) p 0.2, p 0.2, random
Cliff Walking
Cliff Walking
Cliff Walking
Cliff Walking
Fvallntioo returns
Evaluaton ratums
Evaluaton returne
Evalluation returns
A950
ABRLE
ARRL
4050
Training episodes
Training episodes
Training episodes
Training episodes
0.1, p 0.2, fix
0.2, 0.2, fix
(x) 0.1, 0.2, random (h) p 0.2, p 0.2, random
Figure 5: ARRLC vs.
ORLC.
Inverted Pendulum
Inverted Pendulum
Inverted Pendulum
Inverled Pondulum
Evalusaton relums 5
Evaluation returns
Evaluation retums
Evsluslion
Training episodes
Training episodes
Training episodes
Training episodes
p 0.1, p 0.2, fix
(b) p 0.2, 0.2, fix
(c) p
0.2, random (d) p 0.2, p 0.2, random
Cliff Walking
Cliff Walking
Cliff Walking
Cliff Walking
Fvalication returns
Evaluation returss
Evaluation retums
Evalusation returss
Enter D4eseing
Sibeer Cleaeing
Training episodes
Training episodes
Training episodes
Training episodes
(e) 0.1, 0.2, fix
(f) 0.2, 0.2, fix
(g) p 0.1, p 0.2, random (h) p 0.2, p 0.2, random
Figure 6: ARRLC vs. Robust TD
Table 2: Final rewards under cross-comparison between ARRLC, PR-PI and RAPL
ARRLC ADVERSARY
RAPL ADVERSARY
PR-PI ADVERSARY
ARRLC AGENT
72.536
81.736
89.824
RAPL, AGENT
49.936
72.216
70.6
PR-PI AGENT
52.788
63.784
86.648
We also show the performance of the non-robust, approach orle trained without action-failures, the non-robust approach when trained against the worst adversary learned by ARRLC, and ARRLC against the worst adversary learned by ARRIC. Figure 7 shows how much better ARRLC performs against the adversary than the the non-robust approach, and how far is the performance of ARRLC from the optimal. We set p 0.2 and p 0.2 in this experiment.
18

---

Published in Transactions on Machine Learning Research (08/2024)
Inwated Pandulur
Lowed TENENNT ORLC acverary ATRL
apicades
Figure 7: Evaluation returns during training. We compare the performance of the non-robust approach orle trained without action-failures, the non-robust approach when trained against the worst adversary learned by ARRLC, and ARRLC against the worst adversary learned by ARRLC.
B Proof of Proposition 4.1
The uncertainty set of the policy execution has the form in:
(T) == (x = (1- - ()=(-)) + (T)( AA).
(17)
We define
H
Ch Cor (s)
(sw, ax)) = s, aN ~ tx (-
=
w'=h
D (s,
E
Σ
(sw, a s,an a, aw t (+|sw)
==h
Robust Bellman Equation First we prove the action robust Bellman equation holds for any policy T,, state action a and step h. From the definition of the robust. value function in equation have VI ( 0, Vs S.
We prove the robust Bellman equation by building policy ".. Here, policy x is the optimal adversarial policy towards the policy æ.
At step H, we set (s) arg min RH(s,a). We have
(*(s) = min 0 ' (s)
DD TM (s) + pmin (D Rul(s)
(18)
= (1 - (D (5)(s) + +mmnn (8, = =C -P(s), (TT.
aEA
VH41 0.
The robust Bellman equation holds at step and ming E. w ((s) E. ((s)smmmn min C 0 (P(s)
E. w(s) (ss) for any state s and any weighted function w + As.
Suppose the robust Bellman equation holds at step h + 1 and min E. [.s(s)0Hr('0()) Σ. w(() min, "hrt'"(s) E. w(s) "(s) for any state and any weighted function w As-
19

---

Published in Transactions on Machine Learning Research (08/2024)
Now we prove the robust Bellman equation holds at step h. From the definition of the robust Q-function in equation 2 and the form of uncertainty set, we have
(x, = min *ell(a)
E
Rer(sw an )88 8, on = Tee (-188))
R'=h
= -min Dr 2x (s,a)
(19)
-RA(s,a) + min E. Ev (1 Chti "
=Rn(s,a) + Eg Px min ' (s)
=s,(s, a) P
We also have that ()( D a)s
Recall that a (stochastic) Markov policy is a set of H maps a == (m : S ΔлhEEHH- From the definition of the robust value function in equation [ and the form of uncertainty set, have
(s)
E *)
min
Σ
Ry (Sw, s, an ~ fN (+[sw)
LK=A
min CRTTT (s))
min min
(S))
w's (n' wwlk
(20)
2(1 p)
min
Ba Dh. ass + pmmn x'n (w' 2011
min (as Di "p. (s,
(a' d'ull 1a
21 p) E (-1o)
min (or {
D (s, + pmin E B (16) x'p
min ( M=+1
D
n. -p (s.
=(1 TD) (s) + pmin (s)
aEA
We set n (s) = arg min (s. = arg min DT :(ssa).
At step h, we have
(s) SCh," (sss)
=(1 - p) D D "I((s) pin D ((s,a)
(21)
aEA
=) (7) + pmin (s,a), aEA
where the last equation comes from the robust Bellman equation at step h + and
D P (s, = (s a) + [PAC (s, = RA(s, + [PAVA
Thus, the robust Bellman equation holds at stop h. Then, we prove the commutability of the expectation and the minimization operations at step h. For any weighted function w, we have ming E, w(s) ((s) 2 E. w(s) min, C ((s). Then, min, E, w(s) C *((s) < E. w(s) +((s) = E. w(s) min C By induction on H, ... 1, we prove the robust Bellman equation.
o (s)).
Perfect Duality and Robust Bellman Optimality Equation holds and can be solved by the optimal robust Bellman equation.
We now prove that the perfect duality
20

---

Published in Transactions on Machine Learning Research (08/2024)
The control problem in the LHS of equation 4 is equivalent to
H
max min (T)
Σ
(s (s))ss = 8, an ~ th (-Isw)
= max min Ch -F.TT'((s) (P().
(22)
The control problem in the RHS of equation 4 is equivalent to
H
min max E (alle(a)
Σ
(SN (s) = s, an ~ (-1sw)
= min max C (s).
(23)
=|=h
For step H, we have CH
( (s) = [11 RH|(s) = (1 (1- () + plD xi, RH((s). Thus, we
have
max min CH1 (8)) =(1 - p) max Dr [+) p Rs)(s)
(24)
=(1 p) max (s, + p pmin (s,
atA
beA
and
min max CH O' ((s = - p) max D Rs)(s) + pmmi RH((s)
(25)
-(1 p) max (s a) + pmin (s,
aaA
DEA
At step H, the perfect duality holds for all s and there always exists an optimal robust policy (s)
arg max Qi (8, arg max (s, and its corresponding optimal adversarial policy TH [ (s)
arg min (s, a) which are deterministic. The action robust Bellman optimality equation holds at step H for any stats and action
In addition, max, ming E. C()
(s) Es w(s) max, min, C (f) for any weighted function
S + As. This can be shown
max min
w CH
. P(ss
SES
=(1 p) max
w(s) ID nm (s)(s) + pmmnn Σ w(( (D. RH((s)
(26)
=(1 p) Σ
w(s)
max aeA
Ry (2,(s,,0 a) + w(st min Ru (s,
DEA
SES
SES
Suppose that at steps from h + to H, the perfect duality holds for any 8, the action robust Bellman optimality equation holds for any state s and action a, there always exists an optimal robust policy Th arg max.eA Qh, (s.a) and its correspouding optimal adversarial policy Tा = arg min Qi a), Vh' > h + 1, which is deterministic, and max, min,' E. (() (((s) E. wo(s) max, min,/ C (Ps) for any state s, any weighted function w S - As and any h' 2 h+1. We have (s) V (s) C x (sss and (s, a) Q a) D *((s a) for any state and any h' 2 h + We first prove that the robust Bellman optimality equation holds at step h.
We have
Q7 max min D PP),
max min Rr (s, (PACHA "a (s),))
(27)
(s, [Pa min Chd C ))(
= (s, + [PAV (
21

---

Published in Transactions on Machine Learning Research (08/2024)
and also (=, = 07 (s, = "* ((s,a). (s,
From the robust Bellman equation, we have
max V/ (8) = =max (1 - [) [hl(s) + pmin Q% (3( OEA
5(1 p) max max
[D (8) +
max
min (7, a)
{ W-h11
18
f aEA
<( p) max max
[D (N((s) + P min
max (%(s,
(28)
( -h41
acA (Th
<(1 max D mp Qhl(s) + p (8,
-(1 - p) max Q% (s. a) + p min (s) aεA
aEA
We set (8) = max (8, a). According to the robust bellman equation, we have
max V/ (s) 2 V (s) = (1 p)[ x Q% ((s) + min Q (s,a)
aEA
(1 - p) max Ti (8, + min Th (s,a) aaA
(29)
aed
(1 p) max
Q ss a) + pmin (%,
acA
aeA
Thus, the robust Bellman optimality equation holds at step There always exists an optimal robust policy "A arg max Q% (s, and its corresponding optimal adversarial policy Th (s) arg min Q7 (s. a)
that is deterministic so that C% x (s)(s) Vi((s)
Then, we prove the commutability of the expectation, the minimization and the maximization operations at step h.
In the proof of robust Bellman equation, we have shown that
min Σ ( ((s) = Σ w(s) min CT,
((()) (s))
for any policy and any weighted function w. Hence
max min
Σ w(s (() (()s) Σ max Σ w(s) min C. (s)..
First, we have
max Σ w(s) min ch ((s) s Σ w(s) max min C.. (s).
Then, we can show
max wis min Ch 0 (s)
Σ w(s) min C (s)
= Σ ((s) (()(ss)))))))))))))))))){{{))(
= Σ w(s) max min C C. -p Pss).
(30)
In summary,
Σ T
(w()) (s)) Σ w(()) max min )TT)'' (ss).
max min
31
x²
We can show the perfect duality at step h by
max min Ch Cr. ((()) = C (()) max C (((s) 2
min max C -P (s).
(31)
x
"²
By induction h = H, 1, we prove Proposition 4.1
22

---

Published in Transactions on Machine Learning Research (08/2024)
C Proof for Action Robust Reinforcement Learning with Certificates
In this section, we prove Theorem 5.1 Recall that we use कh o No: P and 0% to denote the values of Qn V Va. max (N,, 11, Ph. rh and 0n at the boginning of the k-th episode in Algorithm
C.1 Proof of monotonicity
C.1.1 Proof of Lemma 6.1
When ( a) < 1, equation equation and equation hold trivially by the bound of the rewards and value functions.
For every [H] the empiric Bernstein inequality combined with union bound argument, to take into account that (s, a) > 1 is random number, leads to the following inequality w.p. 1-SAH8 (see Theorem in (Maurer & Pontil 2009h)
2W p. Vi Vitii (8.
(PA PNViita(s.a) s\
THe
(32)
(s.
(s,))
and
2V PA Vi* V (s,
7H.
(33)
(s,
((NN
Similarly, with Azuma's inequality, w.p. - SAHH
2Var(rk(s,a)) ()
7 3(N)(s $ 2Fh a)e ()(s,a) (sN)
Te (34)
(s) an) s
where Var(rh(s, a)) is the empirical variance of (s) computed by the (s, samples and Var(r)(s,a)) I a))
C.1.2 Proof of Lemma
We first prove that (s) 2 (s, for all hs,a,h,k) S A [H] x [K], by backward induction conditioned on the event & n gVV Firstly, the conclusion holds for H + because (*+)(*)
(s) and (H+)(s,a) = Q #+ (s, = for all s and a. For h E [H], assuming the conclusion holds for h + 1, by Algorithm we have
(8 a) + h+1 (s, + (8 Q7 a)
-s) a) V h+1 (s,a) + (s, Rs a) Pa PAV (s,
= (s, a) (n, a) + P/: (Vn+1 - Vh+tt) (s, a) + (Ptt Pa)Vi+t + (s,
2 pe ((V h+1 1)/] P# (vh
1hit1) (s,
8H2
(35)
2(th (s,
(H,
H
N/ (s)
2 PV h41 + h+ 1 (/2
Pk l
(V Vhrtt (8,
8
12W pa Vx (s,aaa
(s,a)
H
(s,
23

---

Published in Transactions on Machine Learning Research (08/2024)
where the first incquality comes from event ER, (s+ ( and the definition of (s. a) and the last inequality from event EPV, By the relation of V-values in the step (h + 1),
V
Viet1
W 4-1
(s, W pe (s,a)
Ak
[Pk (Vh+n h+1 + 1 (P/V
/ h+1 )² (s, a) +
P (ellV h+1 (++1)/22² -P (s,a) (36)
<AHPP
(V h+1 1h++1/22
Vitt1 (8,
<2HPh
(v vi+11 (),a)
and
2W p. Vr+ (s,
(s,
2 pp 1V h41 + (/2
a) +
4HP, (Tk h+1 vh+t) (s, a)
n (8,
(37)
2W p.. (V + 22+))/2(ss,a),
4HPh (V) Vht - Lhtta (s)
h
(s,
(x)
Ph (V - vh+t1 (8,a)
2W PR. IV (V + (=)
8H2
(s)
H
(s,
Plugging equation 37 back into equation 35
we have ()), + V+ + (s, 2 ()( Thus,
Qa(s,, a) = min H h + 1, Ph(ss a) + V (s. + (s, 2 (s,s)))
From the definition V (s) and T we have
(0) =(1 +
2(1
(38)
2(1 () pmin Q7 as) (s).
Similarly, we can prove that 2 a) - 0% (s,a) and v*())= s V/ (s).
()) P.V. n+ (s,a) (5) QT. (s,a)
as) V/,V h+1 (s,a) ())(s,a) Rn(s, a) Pa PrVittissal (s,
()) a)) +1) [Lo+1 - V/tt1) (s, a) + (P% Ph)Vitt - (5)
2Wpp pe [(V h+1 V (s)
PA (V Vil (s,
8H²
<(p): (s)
(s.
H
N/ (s.
2 Pe V (8,
2 pa [ h+1 V 1
ph (Vh+1 Vh++1 (s,
8
$ 50,
(s.
(s,
11
N/ a)
(39)
24

---

Published in Transactions on Machine Learning Research (08/2024)
and
(a(s) -(1))((11111)1
<(1 - O)TT (s, + miiu Q (s,
(40)
<(1 M)RT (s, (x. 2 min Q (s,a))
aEA
< p) (s)) + pmin O7 (s = Vx= (s).
C.2 Regret Analysis
C.2.1 Proof of Lemma 6.3
We consider the event g n The following analysis will be done assuming the successful event ER n
gV holds. By Lemma 6.2 the regret can be bounded by Regret(K) = EE (V - V (st)) 5
Ee (xt) - - (+t))
By the update steps in Algorithm we have
( - v1(
=(1 o (00
(1 (1- x
< <iDa; (V h+1 - V/ (+++))
+ 2D 2D:z0a 2D
[Da (V h+1 [1++))((+))++++ (V h+1 ( a + +DDz;00(ssh [P
(v (h+t))(sh af)
Day Ph (V (+1+++11-1 - V/ - (((h) - (v h+1 - V/ ( att + 2D 2D
+ 1PA (V). h+1 1/ (s a Pv
(V h+1 - V a
+ q Ph(( (V
h+1 V/ ( att 02 (V h+ - (2-1) + 02 +22 (o+1))
(41)
According to the definition of (s,saa). a),
( - (st))
= =ID (V
h+ - V 1)( - (T
h+1 - 1l at
+ [P) (V h+1 15 att ca (V 1+ h+1 (sh 14
+a Pr h+1 1 ( aft)) cD h+1 -V C2 1+1 (
2 pTptl( ((V) + 1/2 *x+)))
+ 2(1 P)N
+ +2(1-P)
(
(42)
2(1 (2AH) 7)c
+ (1 - P) P) M+1 ($
3N *h())))
2w pA I(V h+1 + /1+1))
(+))))
+ 2
+2p
(
+ p (V h+1 Vit
2 +
(st,,
We noticed that
D Daa
h+1
Vh ()( = (1 PV
h+I - + (V
h+1 Lh (sh ( (43)
25

---

Published in Transactions on Machine Learning Research (08/2024)
We can reorganize the equation 42 to
(s*))) (s))
=(1+ 1/H) 7/2 P/ ( h+1 V - -11 1/H)
(P h+1 V V a
+ (1+ + (/ h+1 V V ah) c1 PM
4+1 (
(a)
+ +cllh(VV N+1 (5h att) - c2 c2 l+1 1 +
W41 (++ta)
2 Pr [[V (WV h+1 +
+ +2(1 p 1
+2(1 --y
( क (st))
( (
(44)
(b1)
2 pa [(V
h+1 + (++ 1 (b())
2(1 - p) + 7)
2p
( (s))))
( Th (o%))
(b2)
(o (st))
2p(2411 + 7H +7
+ 2PV ( (+))
Bound of the error of the empirical probability estimator (a) Bennett's incquality, we have that w.p. 1 1 55
Here, we set c1 = 1 + 1/H. By
2P ( (8, (s,
(s Ph(d'(s,a)1s V
(45)
holds for all 8, a, h k, 8'
Thus, we have that
PPN Ph) h+1 - as,))
Σ (8'1s,)) - Ps a)) - 1 (b))
2P (V (=))(6')- Vh+1((') - SH.
(s,
Pr(
H
(Viti(6)) - vh-1(()) (s,a)
SHc
(46)
2N
HI
SH2
SHi
SP h+1
V
(s,1)
h (s,a)
(N,
SH
SP h41 (s,
(3)
where the second inequality is due to AM-GM inequality.
Bound of the error of the empirical variance estimator (b1) & (b2) Here, we bound W py ((V
h+1 +
Vk (5 af).
Recall that Ch. Cg ((s) E [E# Rww (Sw,,sw))eee H8h 8, an ~ Rx (1sw:) in Appendix B Set kt here is the optimal policy towards the adversary policy I² with n/t (s) arg max, C ((s). Similar to the proof in
26

---

Published in Transactions on Machine Learning Research (08/2024)
Appendix C.1.2 we can show that (x) 2 Ch th (6) We also have that Cj C (p)) max, C (s)) (8)2
2
Ch P (s) 2 V (s) 2 (s) For any (s,a, h k) E 8 x Ax [H] x [K], under event el NErn
Wp h+1 + + 1+++1)/2(ss.0) -A
h+1 xt (s,a)
-PAI(V h+1 V 1+1///2(()s)) - [V: h+1 + V va+1) (s2
PA h+1 (s, (PAC (s)aa)
(47)
A (V h+1)² P1 vh++) - ( + (11
-
S S (v+1)) ())
+ PPl(VV ((V)++)** )22 + - ( (s,
(P.V
1)² 11
(PAV
where the first incquality is due (s) 2 C "h 2 (s). The result of (Weissman al. 2003
combined with union bound N (8, a) E [K] implies w.p 1
28t
|| (-1s, a) - Px(-1s,a)l1 1 (s)
(48)
holds for all s, a, h k. These terms can be bounded separately by
25t
I(Ph
s H2
2St
- (s, & 2H - PAIV S 2H
(49)
(s)
x+1 = (Vt 2HP h+1 - (s+
[(PA 1) 1 S 2HP (V h+1 (s,))
where the first two inequality is due to equation 48 In addition, 3/12 have
2S.
5 1 2N
9SH'
Thus, we
V (s.a)
Way (V ht1 + (x,,)/2((s,a))
WA, Chtt
2s,,) (s,
2St
S4HP, (++1 V/ (x, +3H²
(3,
(50)
9SH
SAHP, 1+1 V/
(x, +1+
2N
27

---

Published in Transactions on Machine Learning Research (08/2024)
Then we have
W pe 1-1 + Vh 1/21) (2(7))
pa ((V 4+1 + / sr (st))e
(1 p)
( (+
Wm Cati C (xX
WR. O ( (sh,
<(1 1N
h+1
( ()))
( (+)))
PH (V h+1 - Lh (sh (h(0)))e
AHPP(V (Vh+1
+ +(1-p)
(S =
No (
+ +(1- V (A(SH + VV
N (6
(1 P) 9/H-1/2 9V9SH41/2
N ( म (ott)
N (s
Wr. C (s (s
W a
. (sh,, (st))e
h+1
5(1 NN
N (+)))
(s (sh))
(V h++1 h+1 - (ot (+t)))
2V2H2
+ (1 P)
2/2H
N (
(51)
Pa - -++
2V²H²
+0 0
2/2H
1
(1 P) C ((+
PV NE (s5t))
p)v 9/H44/2
PV9SH41/2
(o A (ott)
Pr C at ( (x
Cain at I1
W P.
=(1 P)
h+1
h+1
( (++)))
( dh I (st))
ID RA
(V
1+1 Vh (58)
2V2(1 - p)H2L ( (b{1)
2 2v20H2
+ ((()
2/2H
(1 V NK (({))) + VV
(1 - PM
9/9HH41/2
No. 1
(1 (())))
where the second inequality is due to AM-GM inequality.
28

---

Published in Transactions on Machine Learning Research (08/2024)
Recursing on h Plugging equation 46 and equation 51 02 = 11+1/HH3 we have
into equation 44 setting c + 1/H and
-=( L
1 h+1 LK -
(1 -L+ (/ - V/ -
+1/H h+1 h+1 - ( a/) (SH + SH²)
VX
( a%
ta h+1 - 1sh - c2 h+1 - 1
- + C2 [V - V (+++))+
2 (o8)))
2(1 (2411 + 7H 7)
2 PIV N (+
( (s))))
O (3
2
(52)
201
(S (s
3N (g
SW PA Cf tt " (s,) (1()))
8W Pa Cht1 xt (s (x
+ (1 1
( (+)))
D # PA h+l
Vh+ (oh)
8(1 - p)HP
8pH22
H
NA (o8g)
=
8
8
6(1 ()V-S) (((
6pv ((
+ (1 + DV
+ P
(sh (+R))
(5 (+
We set (s. a) = pr Ch4 =
32
+ SH ().a))
Since (s, S 1, by organizing the items,
(s.a)))
we have that
(*())) ($})
#y P/ (V) h+ - 11(5)) (1 (1+1/H)) (1+1 1+1 - VA (5 oN
+ (1/H + 11/H PM h+1 VL 1sh at:) + (SH + SH
(5 at))
PPP (V A+1 (sh of) (V
h+1 - - + c (3tL)
Day Pa h+1 7
+ +D (*)))
5(1 + (1HH 2 Ph: (T
h+1 1((s)) (1 + 1/ HHH (P) A+1 V 11 of)
1 + - P h+1 (+)) (v
h+1 - Vh+ (5 af))]
(53)
+ (1+
+
h+1 v (5 at: 02 (V / - v (5t
(SH + SH²)
+ + h+1 Co (
+ + +D+ ((()))
( ax)
5(1 + 1/HHH/H Pk: h+1 ((++)) (1 + (/ h41 1 (3t
(V
1
+ и
DD Pn
h+1 Vk Vh (sf)) Pv h+1 - Vh+ (sth at)1
+ cv2Ph(V h+1 v 1 af.) -2 (v* l+1 1h+
+ + h+1 - ( (SH + SH2)
D Of(
(5) at)
29

---

Published in Transactions on Machine Learning Research (08/2024)
1, "., H and V*+1 Vh+1 = 0, we have that
By induction of equation on 10.,...
K
H
Regret(K) & 21
Σ
D
Pk PR(V h+1 VA ((+1)(sA) - P (V
h+1 V 1h++i (14+))sh ah)
k= h=1
H Da Pn(V h+1 - V [ - Pa(V (41 ( at)l
(54)
+ PA(V h- -
V ab) -(V - v (
(SH + )
+ D (s / at.
Here we use (1 (1+1/H)aи < 21.
C.2.2 Proof of Lemma 6.4
Recall that M1 = -E Σ h= (D PN (T V (($) P/ (V
1 V (o at)l.
Since BaRDD 1// h+1 V (5 a
(V h+1 1itt)) have that Dag P\ (V (V++1 h+1 D&# Pr.
h+1 vh+ (s a is a martingale difference sequence. By the Azuma- Hoema-in in- Vh. ($/ P (V
equality, with probability 6, we have
D ( (++) - P/ (0 atil SHV2HK.
(55)
C.2.3 Proof of Lemma 6.5
Recall that M2 = =K E 1 Ph (($)) - PA(V Vh h+1 (s aB)]-
H
h+1
Since EAt-DAY (V
1 a
Day PA h41 (st)) we have that Day Pa (V
24
1h+z) P. h+1 1h (s a is martingale difference sequence. By the Azuma- Hoeffding in- equality, with probability - 6, we have
K ΣΣ
2* Pa (h+t)(s))) Pa(V ht1 V (s afill I HV2HHKu
(56)
C.2.4 Proof of Lemma 6.6
h+1 1htr) (Th-1 1 10 att (s = 1 and ( att = 0 for s + sf Thus, [(P) - (v V 1s af) a martingale difference sequence. By the Azuma- Haama--oeffding inequality, with probability 5, we have
Recall that M3 DK
Let the one-hot vector ( at) to satisfy that
(s
K
Σ
Σ
I(Ph - i KI 1 att I HV22HKi
(57)
R h=1
C.2.5 Proof of Lemma 6.7
(8H+SH") We bounded M4- = E m=1 at)
+ +D (s))) by separately bounding the four items.
30

---

Published in Transactions on Machine Learning Research (08/2024)
Bound Σ
1k=1
k
Ex=1
H
1SH+9H")
We regroup the summands in a different way.
H ΣΣ
K
(SH SH²)
N (s.a)
(SH + SH )
Σ A= (s,0)ESXA
Σ ==1
S (SH SH
(58)
hml
rn "f (x.a)
Recall that (s) = V
52
46v SHH1
(s.a)
(s,a)
32c Bound E Em ply
+PV (+). (+))
32c
We regroup the summands in different
way. For any policy т, we have
H
N (2.0)
32,
Σ
Σ
Σ
32t
SSHVSAK.
(59)
(
(())
k=
h= (s,))SSXA
==
46SH Bound Σ k= E [11 p)
H
+
(
46SH
We regroup the summands in different way.
For any policy we have
N (s.a)
46
46v S
Σ (x,0)ESXA
Σ
< 465
AH A
(60)
1 ((5)))
n=1
Bound
K Σ k= Σ k==
(1 (1-
pvr. Pa h-1 - (
8 Pr C
(ot at (+t))
By
Cauchy-
( (+)))
N (
Schwarz inequality,
H
W P.. C ="' ({}
N (
K
H
K H
Wr, h+1
C i (s (s)))
(61)
(($$))
K H
Wr, C x" x² (( (+)))))
S
k=1 h=1
Similarly,
te I as
WP
C
(s x (+)))
(62)
K H
SAH?2 2
Σ Σ
Wp
gh h. .x -p (s ($))))
km
By (1 (1- (I-p)a² + pb2 2 ((1 p)a + pb)2
K
Wr, C - - - (/()))
Wm. C "t " (s/))
(1 p),
(63)
H
Σ
(1 Wr xI ( + pWr, C - (st..
k=1b=1
31

---

Published in Transactions on Machine Learning Research (08/2024)
Now we bound the total variance. Let D x Pr(('(s) = (s) + ps.
(64)
and
WDD 1n) = -((1 (11-))PP((1ss
h
(65)
Σ (11- -1 () + P (+))) V/
We have that
V Vi Pal Cht1 P (
Σ [11 - PP0GG//H "(d))2
- 1 (11 p) TO
of 's')) (s)))2
(66)
21 pn C C W (
+ +
(1 (F
(('))
((5)) + (s (s')1
2(1 - p) ra Ch x" (sh x (5h))) + p ry Ch xz (sh. (s))),
where the last inequality is due to (1 - p)a² + pb? N ((1 - p)a + pb)².
With probability 28, we also have that
K
H
Pul O (s())
W VID
K
[ Pa (C fe x" ()9(())))
( (((t)) 2)
n-1
PD (p9(h))) (cnfi=" ((0ht)))))
K
11
(C " (stiti))) - Pa
1=11=1
(67)
<HHK2HK +
K
(Ca x² -
- (1D (1Dg ))
Σ
K
lo tr x (sf)))
k= h=1
k=
K
<H2 + 2H
Ch (st)
D Pr. Ph =sh))
k=1h=1
K
H
I' sp (((5)t1))== - -Dag Ph O x' ( d
SH2 2H 1=1
Σ
CT
HI
i (st)
+
Σ
h+1
h=1
<H2 2 + 22H2222H
<3H2K + +9H2 1/2,
32

---

Published in Transactions on Machine Learning Research (08/2024)
where the first incquality holds with probability 1 - 5 by Azuma-Hooffding inequality, the second inequal- ity is due to the bound of V-values, the third incquality is due to Lemma 6.2 so that C% ht I ((s)) N Day Dr
t* - (sh) 2 PapPhCCt1 - (sh), the fourth inequality holds with probability 1 - 6 by Azuma-
Hoeffding inequality, and the last inequality holds with 2ab S a² +
In summary, with probability at least - 6, we have Σ E Wr. V af & (H2 + 1²1).
In summary, Da I SVSAH2K. + 46S AH + VAAS Kt 36SAH2²
BYSSH'K + AH K
D Model-free method
In this section, we develop a model-free algorithm and analyze its theoretical guarantee. We present the proposed Action Robust Q-learning with UCB-Hoeffding (ARQ-H) algorithm show in Algorithm 2 Here, we highlight the main idca of Algorithm 2 Algorithm 2 follows the same idea of Algorithm | which trains the agent in a clean (simulation) environment and learns a policy that performs well when applied to a perturbed environment with probabilistic policy execution uncertainty. To simulate the action perturbation, Algorithm
2 chooses adversarial action with probability p. To learn the agent's optimal policy and the corresponding adversarial policy, Algorithm 2 computes optimistic estimate Q of Q* and pessimistic estimate Q of Q=", Algorithm uses the optimistic estimates to explore the possible optimal policy and uses the pessimistic estimates to explore the possible adversarial policy и. The difference is that Algorithm 2 uses model-free method to update Q and V values.
Here, we highlight the challenges of the model-free planning compared with the model-based planing, In the mosel-basod planning, we performs value iteration and the Q values, V values, agent policy मे and adversarial policy π are updated on all a). However, the model-free method, the Q values, V values are updated only on (sh, a which are the samples on the trajectories. Compared with the model-basod planning, the model-free planning is slower and less stable. We need to update the output policy carefully. In line 14-16, Algorithm does not update the output policy when the lower bound on the value function of the new policy does not improve. By this, the output policies are stably updated.
E Proof for model-free algorithm
Vh In this section, we prove Theorem 7.1 Recall that we use Th V" 2* 2 V'
and No denote the values of
V.. V, and max (N,, 1} at the beginning of the k-th episode.
Property of Learning Rate ar We refer the readers to the setting of the learning rate a := #+1 and the Lemma 4.1 in Jin et al. 2018). For notational convenience, define of = I -ox) and
H+1
aj == o; I[ oz). Here, we introduce some useful properties of af which were proved in (Jin et al.
2018):
(1) i= a and a for 2 1;
(2) Σ i= af- = 0 and a = 1 for L = 0;
(3) 1
Vi < E
a
<
2 for every 2 1;
vi
Vi
(4) E (a/)² < t
2H for every t 2 1;
(5) Ee of $ (1 + 1
for every 2 1.
Recursion on Q As shown in (Jin et al. 2018). at any a, k) E Ax H x [K]. let (s. and suppose (s, a) was previously taken by the agent at step h of episodes ky .a.....k, kt k. By the update
33

---

Published in Transactions on Machine Learning Research (08/2024)
equations in Algorithm 2 and the definition of of, we have
(x)sa)== al h + 1) Σ at (The W (s + bi):
(68)
(s,a) Σ aj (v ( -ba) bi)
Thus,
Chh - (s)(sa)) =a?(H- h +
Σ
al (Th + V ( + +b))
i=1
(of0)(s.a)
Σ
dg Ra ()) + Pa PaV P=V (8,
==1
(69)
= - h + a)) + Σ at ( Vi+t (
i=1
at (1 a)) + Vht (5 PAVi+1 (s, +b))
and similarly
2 - [s, a) = Σ
at k; + vhi ( - b.)
(r)
1=1
Q (8, a) + Σ aaj (Ra( PAVTT((0.
(70)
afan (s, Σ 0i (Pr ((s,))))
ae (1 a)) + ( PA (s. bi).
In addition, for any 1/ < k. let t' = Nok a). Thus, as was previously taken by the agent at step h of episodes ki, .2,...,kr < K.. We have
10t Q (s,a)= = aF (s, Σ a (PR.CE v Vost))(ssaa)
i=1
(71)
Σ at (1r) Rn(s, a)) + Vh: + (5 - PA ( b.).
Confidence Bounds By the Axuma-Hoeffding inequality, with probability 5, we have that for all s, a, and < K,
Σ af (r RR(s, a)) Vk: (s Pa PA ( H. Σ (af)21/25 Hi/tt.
(72)
At the same time, with probability 1 - 8, we have that for all s, h and s K,
a (rr) Ra(s, + Vřt (s ) Pa PaVi (5, S 13/.tt
(73)
34

---

Published in Transactions on Machine Learning Research (08/2024)
In addition, we have WHi/tt S Ei= ajb, S 2/
Hat/t. 22/Hat/t.
Monotonicity Now prove that (s) (s) 2 (s) 2 (i(ss) and (xss,a) 2 Qx(s,a) N Q (s, a) 2 (s, a) for all (s, h, k) E A x H [K].
At step H + 1, we have V (+) = (8) = V (8) = (s) = 0 and @n QH+1 = (H+1(0, a) = 2 (s = 0 for all (5, k) E x A x [K].
Consider any step h E [H] in any episode k E [K], and suppose that the monotonicity is satisfied for all previous episodes as well as all steps h' 2 h + 1 in the current episode, which is
v** 2 (s)
(s) 2 v
(k 1] + th (s,a) 2 Cº (s.a) A( s.) E [k 1] x H [
@H (2,) (1
(74)
(*))) 2 22 (8) > (8) wh 2 h and s SES,
)h(s,,)) Q7, O (s, 2 ( (s wh' 2 h 1 and (s,a) E A.A
We first show the monotonicity of Q values. We have
Φ - ()) 2 - - h --1--h+1--160 Q2(,
( v 2 0,
(75)
and, by to the update rule of V. values (line 13) in Algorithm
2
C - -h (s) S af (s
at (Pa(Citt - Vitt)((s, -VtiiiiiVVtille.
(76)
5 a- (s, + a (PrcC - v=ti)((,,a)) a)) s 0.
-
In addition, for any k' < k;
0 2 S (s, Σ at (PACC vitill(s.a))
(77)
S <aa (s, a) + Σ at (PP ( viti)((s.a) $o. 0.
Then, we show the monotonicity of V values. We have that
(1 - p) max Q + pi arg Q (s,
2(1 p) max (s, arg (s,a))
(78)
211 م) 1e
min Q (s,a)
2(1 pp) (s)) + min Q7 a) = (s).
By the update rule of V values (line 12) in Algorithm 2
(s()) min (v (s).
(s)) (1 p) max ( + p arg (s) 2 (s).
(79)
35

---

Published in Transactions on Machine Learning Research (08/2024)
Here, need use the update rule of policy I (line 11-16) in Algorithm 2 Define T(k; hkk,,, maxfk' (s,
V < le and (s)+ - p) (s, arg max, Q% + a)) + p 2 xx+1c a)}, which denotes the last episode (before the beginning of the episode k)), in which the n and V. was updated at (h, For notational simplicity, we use 5 to denote T(k; h, s) here. After the end of episode т and before the beginming of the episode k, the agent policy क was not updated and V was not updated at (h,,), iee. Vh(()= = Vn V (s) = m.
r+1 (s, Thus, (1 -0 (s, ( (s)) + p pmnn, h (s, a) and ()) ग (s) arg max, Qh
(s) =(1 -2 (s. T + (5)) + p min 2 (s,aa
5(1 1-0 (s (s)) min 27 e (s,a)
(80)
<(1 O)TT (s, (s,T p 1 (s, arg min Q% (s,a))
aEA
<(1 p))p (s, (s))
min QT (s.a) VÆ= (s).
aEA
By induction from h = H + 1 to 1 and k = 1 to K, we can conclude that (x())
(s) 2 Vi((s) 2 VT= (s) 2 (s)
and (s, a) 2 0% a) 2 t (s.a) 2 2¹ (s. a) for all (s, hs E S x x H] x [K].
Regret Analysis According the monotonicity, the regret can be bounded by
K
Regret(K)) = (vi (( S (is vs(())).
(81)
By the update rules in Algorithm 2 have
(5 V
<(1 k) (0%, arg max ( a)) + arg
mig min (5 a))
-11 - e) (s arg max क (s a)) + p (sh, arg arg min Q¹ (5% a))
(82)
=(1 , 1 a.) + न 1 e
= Ø (sh att + 1D Φ 1+*)) Φhh - 2 at).
Set n = (s a and where (s att) is the episode in which (s at) was taken at step h for the i-th time.
For notational simplicity, we set of = (*$ - V and ch = Day @ - 2))(( 1et - 12 af). According to the update rules,
$ = (sh)
ni.
5a 0 (H h + 1)
Σ
an
h+1 (6 (s (ill
V (0ht11
verlotion) Belliinhi) + 20x
1=1
+ [D* @h/h - (+>) - 10x - -Q/ (oh att)
(83)
n
=0% (H- h + 1)
Σ
(Ph+1
+ 2b.) ch
<a (H h + 1)
k())taaf) h+l
+ ch + 4 H3///
m/
We add (a(())) - Vi((s)) over is and regroup the summands in a different way. Note that for any episode kf takes all the prior episodes K; < h where (s)) at) was taken into account. In
k the term Enh of pb+l
ng
36

---

Published in Transactions on Machine Learning Research (08/2024)
other words, for any episode K' the term oh appears in the summands at all posterior episodes A >> k' where (sh ax ) was taken. The first time it appears we have n = ny + 1, and the second time it appears we have n = n + 2, and so on. Thus, we have
K
[V*((s)) ((())
K
K
K
ang
(H - -hh
Σ
4
Hat/nf
k=1
k=
k=1
k=1
(84)
K
K
K
K
0 a
(H - 1)+ +
ph+1
+
Sh
H3t/n
1=1
t=
+1
k=1
k=1
K
K
K
K
(I- - -
4
H31/n
h+1
Rm
k=
where the final inequality uses the properly Ei= of S (1 + #) for every i i2 1. Taking the induction from h = 1 to H, we have
(s k(()))
1=1
(85)
H K
(H - h +1 +
<
ΣΣ
12
12
H31/n
h=1
h=1k=1
where we use the fact that (1 + 1/HHH <3 and Φ = 0 for all k.
We bound the three items separately.
(1) We have E 2h=1 E n (H h 1) - 11 Ex 1m h
1) -
SAH
(2) Similar to Lemma 6.4 by the Azuma-Hoeffding inequality, with probability 1 - 8, have
ΣH Ex=1 <x < H222Hi.
(3) We have E ΣK 12 H3i/n = Ei' E(s.o) IMI VHii/n & HV2H'SAK..
In summary,
K
Regret(K) = Σ (v) - -1² (s/)) S OOVSSHHK +
k=1
and
(1((s)) V/T" (s1) SV (si) - 1 (si+
min (V1 v+(())
kE[K+1]
(86)
VSAHt SAH²
00
K
K
37


Reviews:
[{"review_id": "u1QGZnZq66", "reviewer": "Reviewer_186h", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- The paper is easy to follow, with a clear template. \n- It analyzes a setting that has essentially been addressed heuristically only (probabilistic action robust setup), to the best of my knowledge. The minimax regret and sample complexity result provide a theoretical justification for action robustness under probabilistic policy execution.\n\n**Weaknesses**\n- There is missing literature on robust MDPs. A list of references is provided in §1 of Sec. 2, but the authors claim that \"These settings are beyond the scope of this paper, though our techniques may be also related to these settings.\". This is not very convincing to me. In particular, the PR-MDP setting looks very much like (Wang et al., 2021), if not the same. As a result of this missing discussion on related work, the motivation for this study is unclear to me. On the one hand, action-robust MDPs have already been solved by Tessler et al. (2019) but on the other hand, the environments on which ARRLC are tested are not as convincing. Pertaining to my concern, related work is described without assessing what each reference misses that this paper adds. This section should emphasize more on what previous work did and what is still missing that this study fulfills. For example, a table showing complexity bounds from previous methods + ARRLC would greatly help. Comparisons with SOTA on zero-sum Markov games are only briefly mentioned at the end of Sec. 2. \n\n- Numerical experiments are not very convincing. ARRLC is tested against a non-robust method. Instead, more experiments on robust baselines would have been appreciated to assess the efficiency of ARRLC. In particular, a comparison with RARL and PR-PI on Mujoco tasks would be illuminating here, as these are the original environment benchmarks those algorithms have been tested on. Moreover, it is unclear to me why each comparison baseline appears on a different plot. It would be more intuitive to see one common plot for ORLC, robust TD, RARL, PR-PI and ARRLC for $\\rho=0.1$ and another one for $\\rho=0.2$.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies the action robust framework in which a mixture policy is prescribed in the environment between a maximizing reward agent and a minimizing adversary. Focusing on the finite horizon setting, the authors derive a Bellman recursion that solves this type of MDP and introduce ARRLC, a model-based method shown to achieve minimax optimal regret. Similar results are established on a model-free variant of ARRLC, with less sample efficient bounds compared to its model-based version.  Experiments are conducted in two environments and ARRLC is compared to (i) a non-robust algorithm called ORLC; (ii) a robust TD algorithm; (iii) RARL from Pinto et al. (2017) and (iv) PR-PI from Tessler et al (2019). The numerical results show that ARRLC improves robustness upon ORLC, converges faster than robust TD, and shows more stable performance than RARL and PR-PI.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "On the form:\n- There are several grammar mistakes: punctuation, time concordance, definite article \"the\" for indefinite nouns, etc. There are enough language tools online to avoid submitting works with this many English mistakes. \n- The $p=$ labels in the plots should be $\\rho=$, for notation consistency.\n- $\\Pi(\\rho)$ is introduced without being defined in \"Action robust MDPs\"§ (only later). \n\nOn the content:\n- As established in (Tessler et al, 2019), the action robust setup is a particular instance of robust MDP. As a result, a comparison between ARRLC and robust RL methods (theoretical, in particular) is missing. The authors consider these works as \"beyond the scope of this paper\", but in practice, they englobe this one. In addition, sample complexity bounds in robust RL should be discussed and compared to the proposed method. \n- To better assess the novelty of this work, I recommend the authors to include a table of different complexity bounds established in previous works, vs this one (see remark above). \n- An empirical comparison with RARL and PR-PI should be made on higher dimensional Mujoco environments. \n\nSome questions/unclarities:\n- The model-based complexity bounds rely on Bernstein inequalities, whereas the model-free ones rely on looser Hoeffding bounds. This results in less sample efficiency for model-free Algo. 2. Although minimax optimality is established in both cases, it is unclear to me why Bernstein does not apply to both settings. A discussion on that aspect is missing. \n\n- The bounds do not show any dependence in the mixture coefficient $\\rho$. I may be misunderstanding, in which case the authors should empirically study the impact of the mixture coefficient $\\rho$ on the sample complexity. \n\n- Unlike Tessler et al. the authors focus here on a finite horizon setting. I guess ARRLC generalizes to infinite horizon with a $1/(1-\\gamma)$ term instead of $H$. In this case, how do sample complexity bounds translate in PR-PI?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WWt3HRoGeR", "reviewer": "Reviewer_WE6L", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem tackled in the work is relevant and well-motivated. The literature is also well discussed. Most importantly, the work shows the benefits of the proposed algorithms in terms of regret and sample-efficiency, achieving optimality. The theoretical contributions of the work are therefore strong. \n\nIn my view, however, the section of numerical results could improve. In the main paper, we have results that show that ARRLC is outperforming a non-robust baseline in terms of optimality and outperforming robust baselines in terms of efficiency, spread across three different sets of results. I believe all there results can appear in the same set of plots, especially the last two sets, leaving space for important results, that I believe are currently in the appendix. I believe the experiments that are currently covered in the appendix do not cover some of the most important cases we would like to see tested. Furthermore, the model-free algorithm is not tested, as far as I understand.\n\nFinally, I also think it would be important to have a discussion on the choice for the episodic setting instead of the infinite setting, which should in theory be easier to analyze, due to existence of an optimal stationary policy (not dependent on the time-step). I think it would also be beneficial to have on the paper either a discussion on why standard reinforcement learning algorithms such as model-based or model-free TD learning algorithms were not used as baselines, or their results added.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The work focuses on the problem of action-robust reinforcement learning, where the goal of an agent is to learn a policy that can also perform in a scenario where the action fails with probability $\\rho$, either being replaced with a random action or, especially, chosen by an adversary. The work proposes a model-based (ARRLC) and a model-free (ARQ-H) algorithm to solve the problem; proves the existence of an optimal action-robust policy; derive the regrets and sample complexities of both algorithms; and proves the proposed algorithm ARRLC achieve optimal regret and sample complexity.  The work also provides numerical experiments that demonstrate that ARRLC outperforms non-robust algorithms in terms of accumulated rewards and robust algorithms in terms of efficiency.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The numerical results I miss are the following:\n- Performance of the non-robust approach (trained without action-failures) and ARRLC against the worst adversary possible. It would be important to see how much better ARRLC performs against the adversary it was trained to face.\n- Performance of the non-robust approach when trained against the adversary tested in the main paper. It would be important to see how far is the performance of ARRLC from what would be optimal, if the adversary was known. \n- Performance of the model-free ARQ-H in all settings. \n\nI think it would be also beneficial to see justification for the choice of episodic setting, and for not considering standard reinforcement learning algorithms as baselines for the experiments. \n\nI believe that the changes I recommend are important for the work to be well validated. They would also strengthen the work significantly in my view. However, I would not say they are critical.", "broader_impact_concerns": "I do not predict any particular ethical impact of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "U8kLxO98I1", "reviewer": "Reviewer_gDKT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n\nThe idea is well explained, the math looks ok and the experiments clearly show a strong improvement of the SOTA.\n\nThere is both theoretical and empirical evidence to justify the approach. \n\nI find very interesting the way ORLC was adapted to the zero-sum game framework where the adversarial policy minimizes the pessimistic value. \n\n*Weaknesses*\n\nThe model-free algorithm part seems disconnected to the rest of the paper. It is forgotten in the experimental part and the conclusion (while the conclusion mentions adaptation to continuous setting and I guess the model-free approach would be better suited for this framework).\n\nOne thing I am not sure to understand about action-robust RL, and that is not mentioned in the paper, is how extending the robustness to the worst adversarial is still robust against any adversary. We could imagine a game where two or more Nash equilibria are possible. ARRLC would fall into one of them, and if suddenly the adversary plays another equilibrium, the algorithm's answer will be not adapted at all.  For example, imagine a 3D cliff walking game, you have to walk in the x direction, and both y and z are leading to a cliff. Two equivalent worst case adversaries could be imagined, one always pushing to the y axis, the other always pushing to the z axis. ARRLC would discover one of them, and would learn to adapt to only one adversary.\n\n*Questions* \n\nIt seems that this algorithm could be adapted to solve general zero-sum games (if the $\\rho$ rule is replaced by a turn by turn setting). Did you explore or plan to explore that possibility?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an algorithm (ARRLC) that addresses the action robust RL problem, where the actions produced by the agent are sampled from its own policy with prob $1-\\rho$ and sampled from an adversarial policy with probability $\\rho$.\n\nARRLC has theoretical guarantees for sample complexity and regret, and empirically outperforms the previous few algorithms designed to solve the same problem.  \n\nAs ARRLC is a model-based approach, the authors also derive a model-free version, with weaker theoretical guarantees but that does not require model estimation phase.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "*Maths*\n\nI would suggest a simple change to simplify the maths in the introduction:\n\nInstead of having $\\pi \\in \\Delta_A$ and $\\tilde{\\pi} \\in \\Pi(\\pi)$, to use $\\pi \\in \\Delta_A$ and $\\pi' \\in \\Delta_A$ where $\\tilde{\\pi}=\\Pi(\\pi, \\pi') := \\pi'$ with $p=\\rho$, $\\pi$ otherwise.\n\nThat way, eq (1), (2) and (4) would be much more clear (minimizing over $\\pi' \\in \\Delta_A$). And it would be perfectly coherent with the notation in eq (7). \n\nIn \"Additional Notation\", in the derivation of variance of the value function (very last equation): $[P_h(V_{h+1})^2](s, a) - ...$\nThe square should go inside the parenthesis (otherwise it seems that it applies to $P_h$ while it applies to $V_{h+1}$).\n\n*Experiments*\n\nAlso compare ARQ-H to the SOTA and to ARRLC. \n\nExplain how you discretized the pendulum task (that is, it seems to me, a continuous task). \n\nIn appendix A.2, was ARRLC trained for the specified random or fixed adversary, or was it trained with the worst case adversary and then tested with the random / fixed one?\n\nI would also suggest adding the above-mentioned 3D cliff walking task and see if the learned policy is still robust against any adversary (like a deterministic one that always goes for the y axis). If this breaks the results, that would still be a very interesting phenomena and if not, it would show that this approach is particularly strong.", "broader_impact_concerns": "Does not apply.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper takes an interesting formulation of action-robust reinforcement learning and provides principled algorithms and a corresponding analysis. All the reviewers agree that this submission is valuable, and I am inclined to propose it for publication.

However, going through the paper briefly I noticed some areas of improvement in the presentation. I think the manuscript requires some polishing, a concern mostly shared by the reviewers. I provide some suggestions below while i urge the authors to go through the reviewers' comments again before submitting a final version of the paper.

----

- The result showing that action-robust RL has the same sample complexity barriers of RL is an important contribution that could be better highlighted. Reviewer 186h suggests to integrate this conclusion in the abstract as well.
- The symbol $\widetilde{\pi}$ has an ugly display when in subscript.
- I suggest to use top alignment for Algorithm 1 (to the next page) and to consistently use either ARRLC or AR-RLC acronym.
- Figure 1 could have a better display (e.g., Figure 2 in the appendix is much clearer) and the caption should be much more informative, such as to include the information on the number of runs and the meaning of the shaded areas, report what is p and the parameters used (especially $\rho$), instead of "Tessler 19", "Pinto 17" report the name of the algorithm and (optionally) a reference in the caption.
- Algorithm 2: It is odd to have both "Output" and "Return". $\pi^{out}$ does not seem to be specified.
- Finally, I suggest the authors to do a careful revision of the paper in terms of grammar and typos. E.g., uncertain -> uncertainty (above eq. 3), pi -> \pi (below eq. 7).
Decision: Accept (poster)