Online Robust Reinforcement Learning with Model Uncertainty
Authors: Yue Wang
Shaofeng Zou
Venue: NeurIPS 2021 Poster (2021)
Keywords: robust reinforcement learning
model mismatch
data-driven
model-free
online

Abstract: Robust reinforcement learning (RL) is to find a policy that optimizes the worst-case performance over an uncertainty set of MDPs. In this paper, we focus on model-free robust RL, where the uncertainty set is defined to be centering at a misspecified MDP that generates samples, and is assumed to be unknown. We develop a sample-based approach to estimate the unknown uncertainty set, and design robust Q-learning algorithm (tabular case) and robust TDC algorithm (function approximation setting), which can be implemented in an online and incremental fashion.  For the robust Q-learning algorithm, we prove that it converges to the optimal robust Q function, and for the robust TDC algorithm, we prove that it converges asymptotically to some stationary points. Unlike the results in [Roy et al., 2017], our algorithms do not need any additional conditions on the discount factor to guarantee the convergence. We further characterize the finite-time error bounds of the two algorithms, and show that both the robust Q-learning and robust TDC algorithms converge as fast as their vanilla counterparts (within a constant factor). Our numerical experiments further demonstrate the robustness of our algorithms. Our approach can be readily extended to robustify many other algorithms, e.g., TD, SARSA, and other GTD algorithms. 

Online Robust Reinforcement Learning with Model Uncertainty
Yue Wang University at Buffalo Buffalo, NY 14228
Shaofeng Zou University at Buffalo Buffalo, NY 14228 szou3@buffalo edu
ywang2940buffalo. edu
Abstract
Robust reinforcement learning (RL) is to find a policy that optimizes the worst- case performance over an uncertainty set of MDPs. this paper, we focus on model-free robust RL, where the uncertainty set is defined to be centering at misspecified MDP that generates a single sample trajectory sequentially, and is assumed be unknown. We develop sample-based approach estimate the unknown uncertainty set, and design robust Q-learning algorithm (tabular case) and robust TDC algorithm (function approximation setting), which can be implemented in an online and incremental fashion. For the robust Q-learning algorithm, we prove that converges the optimal robust Q function, and for the robust TDC algorithm, we prove that it converges asymptotically to some stationary points. Unlike the results in Roy et al. 2017]. our algorithms do not need any additional conditions on the discount factor to guarantee the convergence. We further characterize the fnite-time error bounds of the two algorithms, and show that both the robust Q- learning and robust TDC algorithms converge as fast as their vanilla counterparts (within a constant factor). Our numerical experiments further demonstrate the robustness of our algorithms. Our approach can be readily extended to robustify many other algorithms, e.g., TD, SARSA, and other GTD) algorithms.
Introduction
Existing studies on Markov decision process (MDP) and reinforcement learning (RL) [Sutton and Barto 2018) mostly rely on the crucial assumption that the environment on which learned policy will be deployed the same one that was used to generate the policy, which often violated in practice e.g., the simulator may be different from the true environment, and the MDP may evolve over time. Due to such model deviation, the actual performance the learned policy can significantly degrade. To address this problem, the framework of robust MDP was formulated in [Bagnell et al.) 2001 Nilim and El Ghaoui| 2004 [yengar 20055.. where the transition kernel of the MDP is not fixed and lies in uncertainty set, and the goal is to learn policy that performs well under the worst-case MDP in the uncertainty set. In [Bagnell et al. 2001 Nilim and El Ghaoui 2004 [yengar 20055, assumed that the uncertainty set is known beforehand, i.e., model-base approach, and dynamic programming can be used to find the optimal robust policy.
The model-based approach, however, requires model of the uncertainty set known beforehand, and needs large memory to store the model when the state and action spaces are large, which make less applicable for many practical scenarios. This motivates the study in this paper, model-free robust RI. with model uncertainty, which learn robust policy using a single sample trajectory from misspecified MDP, c.g., simulator and similar environment in which samples than in the target environment where the policy is going to be deployed. The major challenge lies in that the transition kernel of the misspecified MDP is not given beforehand, and thus, the uncertainty
easier to collect
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

set and the optimal robust policy need to be learned simultaneously using sequentially observed data from the misspecified MDP. Moreover, robust RL learns the value function of the worst-case MDP in the uncertainty set which is different from the misspecified MDP that generates samples. This is similar to the off- off-policy learning, which we refer to as the "off-rransition-erne" setting. Therefore, the learning may be unstable and could diverge especially when function approximation is used [aird 1995].
In this paper, we develop a model-free approach for robust RL with model uncertainty. Our major contributions in this paper are summarized as follows.
Motivated by empirical studies of adversarial training in RL [uung et al. 2017 Kos and Song 2017 [iin et al. [217]] Pattanaik et al. (0118] Mandlekar et al. 2017 and the R-coontmmiattion model in robust detection (called e-contamination model in [Hbeer 1965 we design the uncertainty set using the R-contamination model (see 4 for the details). We then develop an approach to estimate the unknown uncertainty set using only the current sample, which does not incur any additional memory cost. Unlike the approach in [Roy et al. (017], where the uncertainty set is relaxed to one not depending on the misspecified MDP that generates samples that an online algorithm can be constructed, our approach does not need to relax the uncertainty set.
We develop a robust Q-learning algorithm for the tabular case, which can be implemented in an online and incremental fashion, and has the same memory cost as the vanilla Q-learning algorithm. We show that our robust Q-learning algorithm converges asymptotically, and further characterize its finite-time error bound, Unlike the results [Roy et al. 2017] where a stringent condition on the discount factor (which is due to the relaxation of the uncertainty set, and prevents the use of discount factor close to in practice) is needed to guarantee the convergence, our algorithm converges without the need of such condition. Furthermore, our robust Q-learning algorithm converges as fast as the vanilla Q-learning algorithm (Li et al. 2020 (within a constant factor), while being robust to model uncertainty.
We generalize our approach to the case with function approximation (for large state/action space). We investigate the robust policy evaluation problem, i.e., evaluate given policy under the worst- case MDP in the uncertainty set. As mentioned before, the robust RL problem is essentially "off-transittonn-kerel" and therefore non-robust methods with function approximation may diverge [Baird 1995] (also see our experiments). We develop novel extension of the gradient TD (GTD) method [aci et al. 2010 Maei 2011 Sutton et al., (2008) to robust RL. Our approach introduces a novel smoothed robust Bellman operator to construct the smoothed mean-squared projected robust Bellman error (MSPRBE). Using our uncertainty set design and online sample-based estimation, we develop two time-scale robust TDC algorithm. We further characterize its convergence and finite-time error bound.
We conduct numerical experiments to validate the robustness of our approach. In experiments, our robust Q-learning algorithm achieves a much higher reward than the vanilla Q-learning algo- rithm when being trained on a misspecified MDP; and our robust TDC algorithm converges much faster than the vanilla TDC algorithm, and the vanilla TDC algorithm may even diverge.
1.1 Related Work
Model-Based Robust MDP. The framework of robust MDP was investigated in [lyengar 2005
Nilim and El Ghaoui 2004 Bagnell et al.] 2001 Satia and Lave Jr 1973 Wiesemann et al. 2013]. where the transition kernel is assumed to be in some uncertainty set, and the problem can be solved by dynamic programming. This approach was further extended to the case with function approximation in [Tamar et al.] 2014]. However, these studies are model- which assume beforchand knowledge of the uncertainty set. In this paper, we investigate the model-free setting, where the uncertainty set is a set of MDPs centered around some unknown Markov transition kernel from which a single sample trajectory can be sequentially observed.
Adversarial Robust RL. It was shown in [Iyengar 2005) that the robust MDP problem equivalent to zero-sum game between the agent and the nature. Motivated by this fact, the adversarial training approach, where an adversary perturbs the state transition, was studied /Vinitsky et al.) 2020 Pinto
et al. 2017 Abdullah et al. 2019 Hou et al. 2020 Rajeswaran et al. 2017 Atkeson and Morimoto, 2003 Morimoto and Doya. 2005 This method relies on simulator, where the state transition can
be modified in an arbitrary way. Another approach is to modify the current state through adversarial

---

samples, which is more heuristic, e.g.. [Hunn et al. 2017, Kos and Song 2017 Lin et al. 2017 Pattanaik et al., 2018 Mandlekar et al. 2017 Despite the empirical success these approaches, theoretical performance guarantees, e.g., convergence to the optimal robust policy and convergence rate, are yet to be established. The main difference lies in that during the training, our approach does not need to manipulate the state transition of the MDP. More importantly, we develop the asymptotic convergence to the optimal robust policy and further characterize the finite-time error bound. In (Lim) (et al., 2013). the scenario where some unknown parts of the state space can have arbitrary transitions while other parts are purely stochastic was studied. Adaptive algorithm to adversarial behavior was designed, and its regret bound is shown to be similar to the purely stochastic case. In (Zhang et al.) 2020a the robust adversarial RL problem for the special linear quadratic case was investigated.
Model-free Robust RL. In [Roy et al. 2017 Badrinath and Kalathil 2021] model-free RL with model uncertainty was studied, where order to construct an algorithm that can be implemented in an online and incremental fashion, the uncertainty set was firstly relaxed by dropping the dependency on the misspecified MDP that generates the samples (centroid of the uncertainty set). Such a relaxation is pessimistic since the relaxed uncertainty set is not centered at the misspecified MDP anymore (which is usually similar to the target MDP), making the robustness to the relaxed uncertainty set not well-justified. Such a relaxation will further incur a stringent condition on the discounted factor to guarantee the convergence, which prevents the use of a discount factor close to in practice. Moreover, only asymptotic convergence was established in [Roy al., 2017]. In this paper, do not relax the uncertainty set, and instead propose an online approach to estimate it. Our algorithms converge without the need of the condition the discount factor. We also provides finite-time error bounds for our algorithms. The multi-agent RL robust to reward uncertainty was investigated in (Zhang et al. 2020b), where the reward uncertainty set is known, but the transition kernel is fixed.
Finite-time Error Bound for RL Algorithms. For the tubular case, Q-learning has been studied
intensively, e.g., in [Even-Dar et al., 2003 Beck and Srikant 2012, Qu and Wierman 2020 Li et al.
2020 Wainwright 2019]]Li et al.) 2021T. TD with function approximation were studied in Dalal
Gal and Szörényi, Balázs and Thoppe, Gugan and Mannor, Shie 2018 Bhandari et al.
2018 Srikant
and Ying, 2019; Cai et |ll,22019 (Snn et al.| 2020]. Q-learning and SARSA with linear function
approximation were investigated in [Zou et al. [019 [Chen et al. 2019]. - The finite-time error bounds
for the gradient TD algorithms [Maci et al. [2100] [Sutton et al. 22099] Maei et al. [0100] were further
developed recently in (Dalal al. 2018 Liu et al. 2015 Gupta al. [2099] Xu al.
2019 Dalal
let al.] 20200 Kaledin et al.) 2020] Ma et al. [2020] Wang and Zou| 2020 Ma et al. [202] Doan 2021]
There are also unite-time error bounds on the policy gradient methods and actor critic methods, e.g..
[Wang et al. 2020 Yang et al. 2019 Kumar et al. 2019 Qiu et al., 2019 Wu et al. [0220] Cen al. 2020 Bhandari and Russo 2019 Agarwal et al. 202 Mei et al. 2020). We note that these
studies are for the non-robust RL. algorithms, and in this paper, we design robust RL algorithms, and characterize their finite-time error bounds.
2 Preliminaries
Markoy Decision Process. An MDP can be characterized by a tuple (8,A,,,,,, 7),,) where S and A are the state and action spaces, P = [pp E 4|8), a E A, s E 8} is the transition kerne] cs the cost function, and y E [o, 1) is the discount factor. Specifically, Pt denotes the distribution of the next state if taking action environment transits to state s' if taking action a at state s. The cost of taking action at state is given by c(s, a). A stationary policy π is a mapping from S to a distribution over A. At each time an agent takes an action A, E A at state S. E S. The environment then transits to the next state S441 with probability PsS,s, and the agent receives cost given by c(S,, A,). The value function of policy ı starting from any initial state s is defined the expected accumulated discounted cost by following т: E 1E0 7c(SS, At = 8, T.. and the goal is to find the policy π that minimizes the above value function for any initial state S.
state Let pº = {p Je' where pg..- denotes the probability that the
Robust Markov Decision Process. In the robust case, the transition kernel is not fixed and lies in some uncertainty set. Denote the transition kernel at time t by Pt, and let (Po, Pi,...), where Pe E P. Vt 2 O, and P is the uncertainty set of the transition kernel. The sequence R can be viewed as the policy of the nature, and is adversarially chosen by the nature (Bagnell et al. 2001 Nilim and
An denotes the (n- 1) J-dimensional probability simplex: ((p..... Pn) 0 S ps 20 P

---

Define the robust value function of policy π as the worst expected accumulated discounted cost following a fixed policy æ over all transition kernels in the uncertainty set:
EI Ghaoui 2004, Lyengar 2005|.
V (s) max EN
Σ y c(S 8, t=
(1)
where E, denotes the expectation when the state transits according to Similarly, define the robust action-value function for policy 9: Q" (=( a) max, Ex [Et= 7'c(S,, At]|So = Ao = a, π|
The goal of robust RI. is to find the optimal robust policy x² that minimizes the worst-case accumu- lated discounted cost:
π argmin V (s..
We also denote V= and Q by V and Q", respectively, and (*) minag (*(ssa)
Note that a transition kernel a collection of conditional distributions. Therefore, the uncertainty set P of the transition kernel can be equivalently written as collection of P. for all E 8, a E A, where Pe is set of conditional distributions P over the state space 8. Denote by (v) max v) the support function of vector u over a set of probability distributions P. For robust MDP, the following robust analogue of the Bellman recursion was provided in [Nilim and El Ghaoui 2004
Iyengar 2005].
Theorem 1.
Nilim and El Ghaoui 2004y The following perfect duality condition holds for all E
oc: E'd(S Ar) =
min max EN
tets Ar) n So = = max min E.
(3)
N
The optimal robust value function V satisfies (8) = min minaen (c(s, + (V*))(")), and the
optimal robust action-value function Q* satisfies Q" (s, a) = c(8, a) + yop;
Define the robust Bellman operator T by TQ(s, a) c(s, a) + po (minge. Q(s, a)). was shown in Nilim and El Ghaoui 2004 Iyengar 2005 that T is contraction and its fixed point is the optimal robust Q" When the uncertainty set is known, so that O.pe can be computed exactly, V and Nilim and El Ghaoui 2004).
Q" can be solved by dynamic programming [Iyengar 2005
3 R-Contamination Model For Uncertainty Set Construction
In this section, we construct the uncertainty set using the R-contamination model.
Let P (E% s E 8, E A} be the centroid of the uncertainty set, i.e., the transition kernel that generates the sample trajectory, and P is unknown. For example, P can be the simulator at hand, which may not be exactly accurate; and P can be the transition kernel of environment from which we can take samples to learn a policy that will be deployed in a similar environment 2. The goal is to learn policy using samples from P that performs well when applied a perturbed MDP from P.
Motivated by empirical studies of adversarial training in RL Huang et al. 2017 Kos and Song 2017 Lin et al. 2017| Pattanaik al.) 2018 Mandlekar et al. 2017] and the R-contamination model in robust detection
Huber 1965], we use the R-contamination model to define the uncertainty set:
Po = (1 R)p + Rqlg E A E S, E A, for some 0 < R < 1.
(4)
Here, P is the centroid of the uncertainty set Pa at (s, a). which is unknown, and A is the design parameter of the uncertainty set, which measures the size of the uncertainty set, and assumed be known in the algorithm. We then let P = O &.E8, Po.
Remark 1. R-contamination model is closely related to other uncertainty set models like total varia- tion and KL-divergence. It can be shown that R-contamination set certered at p is subset of total variation ball: {(1 (1R + Rglg A {g E Aig]ldry(p, q) S R). Hence the total varia- tion uncertainty set is less conservative than our R-contamination uncertainty set. Kl--iivegencc
moreover can be related to total variation using Pinsker's 's inequality, i.e., drv(p. 9) S / Vddxe (p. q).

---

Tabular Case: Robust Q-Learning
In this section, we focus on the tabular case with finite state and action spaces. We focus on the asynchronous setting where single sample trajectory is available with Markovian noise. We will develop an efficient approach to estimate the unknown uncertainty set P, and further the support function awe (-), and then design our robust Q-learning algorithm.
We propose an efficient and data-driven approach to estimate the unknown 1e and thus the unknown uncertainty set Pe for any 8 and a E A. Specifically, denote the sample at t-th time step by O₂ (st, (,, St+1)) We then O₂ to obtain the maximum likelihood estimate (MLE) Pt & 1 #14 of the transition kernel p.y. where 11 24 is a probability distribution taking probability at $t+1 and 0 at other states. This is unbiased estimate of the transition kernel pt; conditioning
S, = s and A, = dz- We then design sample-base -aaed estimate Pr. - {(1 R)p, + Rqlq E 4
of the uncertainty set p.. Using the sample-based uncertainty set P., we construct the following robust Q-learning algorithm in Algorithm For any 0g (Vi) can be easily computed: 0g, (V.)
Algorithm 1 Robust Q-Learning
Initialization: T, Qo a) for all (s,a) E A, behavior policy Th, so, step size at.
1: for I. 0, 1,2, ...,
do
2: Choose ar according to (b(((s²)
3: Observe 81+1 and 6:
4: Vi(s) min Qr a), Vs E
5: Q++1 4x) t (1 Qr)s((s,, ar) + asle + 10 (Vi)
6: Q++1(s,a) t Qe(s, for (s (s),
7: end for
Output: Qr
R max.es Vi(s) + (1 ())) Hence the update in Algorithm (line 5) can be written as
Q4+1(5e, ar) + (1 ar (c + ac + tR max Vi(s) + 7(1 V)
max
(5)
sE8
Compared to the moodel-based approach, our approach is model-free. It does not require the prior knowledge of the uncertainty set, i.e., the knowledge of ph. Vs E 8, E A. Furthermore, the memory requirement of our algorithm is []] x |A| (used to store the Q-table), and unlike the model- based approach does not need a table of size | |.|| to store pt, Vs E 8, a E A, which could be problematic if the state space is large. Moreover, our algorithm does not involve relaxation of the uncertainty set like the one in [Roy et al. 2017), which will incur stringent condition on the discount factor to guarantee the convergence. As will be shown below, the convergence of our Algorithm] does not require any condition on the discount factor.
We show in the following theorem that the robust Q-learning algorithm converges asymptotically to the optimal robust action-value function Q
Theorem (Asymptotic Convergence) step sizes at satisfy that E a; oo and Eie af < co. then Qt - Q" as + co with probability 1.
To further establish the finite-time error bound for our robust Q-learning algorithm in Algorithm 1 we make the following assumption that is commonly used in the analysis of vanilla Q-learning.
Assumption 1. The Markov chain induced by the behavior policy Th and the transition kernel ph Vs E S, a E A is uniformly ergodic.
Let HT,, denote the stationary distribution over 8 x A induced by ne and ph. Vs E 8, A. We then further define Mmin min (s.)e. x.A Mr, (s, a). This quantity characterizes how many samples are needed to visit every state-action pair sufficiently often. Define the following mixing time of the induced Markov chain: lmix min {1= max,es drv ( P(st = -|s0 = s)) s }) where drv is the total variation distance.
The following theorem establishes the finite-time error bound of our robust Q-learning algorithm.
5

---

Theorem 3. (Finite-Tiie Time Error Bound) There exist some positive constants and C1 such that for any ò 1, any E < T-q. any T satisfying
bmix
[T8
T Co
log
log
(6)
Mmmin (1 - 7)
Mmiol
c 7)
2 (1--2) VE 2 0 we have with probability least 1 68,
and step size at
min
log(
7
||Qr - 100 - 3e.
From the theorem, can see that guarantee an e-accurate estimate, sample size O
Pain P (-
(eie(1-9) (up to some logarithmic terms) is needed. This complexity matches with the one for the
Laix
vanilla Q-learning in [Li et al. 2020) (within constant factor), while algorithm also guarantees robustness to MDP model uncertainty. Our algorithm design and analysis can be readily extended
to robustify TD and SARSA. The variance- rrduuccereduutton technique (Wainwright, 2019 can also be combined with our robust Q-learning algorithm to further improve the dependency on (1 -7).
5 Function Approximation: Robust TDC
In this section, we investigate the case where the state and action spaces can be large or even continuous. A popular approach is to approximate the value function using a parameterized function, e.g., linear function and neural network. In this section, we focus on the case with linear function approximation to illustrate the main idea of designing robust RL algorithms. Our approach can be extended to non-linear (smooth) function approximation using techniques in, c.g., (Cai et al. 2019
Bhatnagar et al. 2009 Wai et al. 2019. Wang et al. 2021].
We focus on the problem of robust policy evaluation, i.e., estimate the robust value function V defined in (T) for given policy и under the worst-case MDP transition kernel the uncertainty set. Note that for robust RL with model uncertainty, any policy evaluation problem can be viewed as -ettrrnnitton-keneel as is to evaluate the value function under the worst-case MDP using samples from different MDP. Since the TD algorithm with function approximation may diverge under off- off-policy training [Baird] 1995) and importance sampling cannot be applied here due to unknown transition kernel, in this paper generalize the GTD method [Maei et al., 2010 Maci 2011 to the robust setting.
Let {Φ(); 8 R. i= N} be set of N fixed base functions, where N < |8||A]] In particular, we approximate the robust value function using a linear combination of (())s: Vo(s) EN (')( 00 where 0 E TRN is the weight vector.
Define the following robust Bellman operator for a given policy m:
T (ss) E 1 A) (V))
A) + 7(1 R.)
R V(S') s'E8
(7)
S'E8
We then define the mean squared projected robust Bellman error (MSPRBE) as
MSPRBE(() = | , Vo Vol
where || (2 (ds), Ar is the stationary distribution induced by म, and II is a projection onto the linear function space w.r.t. || -ly.. We will develop a two time-scale gradient-based based approach to minimize the MSPRBE. However, it can be seen that max, Vs(s) in 7 is not smooth in 0 which troublesome in both algorithm design and analysis. To solve this issue, we introduce the following smoothed robust Bellman operator T,, by smoothing the max with LSE(LogSumExp):
T V(s) = E A- c(s, 7 R) Σ P V(s') + + -SE(V))
(9)
EE

---

where LSE = log (E,(E, coV(
is the LogSumExp w.r.t. V with parameter 0. Note that when + 00, the smoothed robust Bellman operator T, + Tg. The LSE operator can also be replaced by some other operator that approximates the max operator and is smooth, e.g., mellow-max [Asadi and Littman 2017]. In the following, we first show that the fixed point of Tx exists for any @. and the fixed points converge to the one of T for large
Theorem 4. (1). For any o. TT has a fixed point.
(2). Let V12 and V2 be the fixed points of TT and T,, respectively. Then
12 S R log SI I
0, as co.
(10)
We then denote by (() the smoothed MSPRBE with the LSE operator, and the goal is:
min ((0) min ITT Vo voll
(11)
#
5.1 Algorithm Development
In the following, we develop the robust TDC algorithm to solve the problem in ITp. We will first derive the gradient of the smoothed MSPRBE, J(0), and then design two time-scale update rule using the weight doubling trick in (Sutton et al. 2009] to solve the double sam- pling problem. Define 85,a,x(0) A c(s.a) a) + 71 R)Vo(s') + (RLSB((V)) Vs(s), where LSE(V)) is the LogSumExp function w.r.t. Vo = TT.. Denote by C - Ep. [s]os] Then,
(, (0)os) Φ D T. VVo), where D diag(ux(s1). Ar (82), Mx (3|s)) and
④ (0 Φoz: .... )ejan)
E R 1IxN, We know that II DII D D D from Maei
2011 Hence we have
((0) ITT, V/ Vol 15..s C- 1ōS.A, (0)ps)
(12)
Then, its gradient can written as:
[ -E (VV.,, (0))). ( (.s.A,s (0)os)
2
(55.4,s-- By (1- + R VLSE(V)) of (():
where (0) C- ASS. (0) (s)ss)- can be seen that to obtain an unbiased estimate of V J(O). two independent samples needed as there exists multiplication of two expectations, which is not applicable when there is only one sample trajectory. We then utilize the weight doubling trick in [Sutton et al. 2009]. and design the robust TDC algorithm in Algorithm 2 Specifically, we introduce a fast time scale to estimate wf)), and a slow time scale to estimate VJ Denote the projection by T (xr - arg min < |ly - x|| for any x E RRN. Our robust TDC algorithm in Algorithm 2 can be implemented in online and incremental fashion. If the uncertainty set becomes singleton, i.e., R = 0, then Algorithm reduces to the vanilla TDC algorithm.
5.2 Finite-Time Error Bound of Robust TDC
Unlike the vanilla TDC algorithm, ((O) here is non-convex. Therefore, are interested in the convergence to stationary points, i.e., the rate of [[V]())) + 0. We first make some standard assumptions which are commonly used in RL algorithm analysis, e.g., [Wang and You 2020 Kaledin
et al. 2020 Xu et al. 2019 (Srikant and Ying. 2019 Bhandari et 2018).
Assumption (Bounded feature). || 112 S 1, Vs 8.
Assumption (Bounded cost function). |c(s, a)) S Cmax, Vs 8 and E A.
Assumption (Problem solvability). The matrix C E,,, [ds0]] non-singular with X > being its smallest eigenvalue.
7

---

Algorithm/ 2 Robust TDC with Linear Function Approximation
Input: T. T,a, 9, 2, 6; for i 1, ..... N, projection radius K Initialization: Wg $0
1: Choose W ~ Uniform (0, -
2: for = 2.... ... W do
3: Take action according to rT-1s;) and observe 8141 and Ct
4: Φt t Dn.
6c.),) + at + 7(1 Ro)o, + 7R loRiR cvo on)
5:
(8)
6: 01+1 f IIx 0c (0.(0.) - -7(11- 1))++1
(1-1)rrt + +BE
eoVole) de
)) )OTTw (oTrr) we
Eser novotos
SE8
7: Wh+1 f [ur + B(6,(0.) w)(r)
8: end for
Output: Ow
Assumption 5 (Geometric uniform ergodicity). There exist some constants m > 0 and E (0, 1) such that for any > max.es dyv(P((s)*s) 1>) ) S mp'.
In the following theorem, we characterize the finite-time enror bound for the convergence of our robust TDC algorithm. Here we only provide the order of the bounds in terms of T. The explicit bounds can be found in (129) in Appendix D.3
Theorem 5. Consider the following step-sizes: 3 = O (7x). and a = 2 (7+), where 1 < a S and 0 < b a. Then we have that
B(I ) =
Ta + +olog(1/))+ + TB
1
+ blog(118))
(13)
If we further let a b 0.5, then |||| VJ
log vT
The robust TDC has a matching complexity with the vanilla TDC with non-linear function approxi- mation [Wang et al. (02T], but provides the additional robustness to model uncertainty. It does not need to relax the uncertainty set like in [Roy et al. 2017). and our convergence results do not need condition on the discount factor.
Experiments
6.1 Robust Q-Learning
In this section, we compare our robust Q-learning with the vanilla non-robust Q-learning. We use OpenAl gym framework [Brockman et al. 2016 and consider two different problems: Frozen lake and Cart-Pole. One more example of the taxi problem is given in the appendix. To demonstrate the robustness, the policy is leamed in perturbed MDP, and is then tested on the true unperturbed MDP. Specifically, during the training, we set a probability p such that after the agent takes an action, with probability p. the state transition is uniformly over 8, and with probability is according to the true unperturbed transition kernel. The behavior policy for all the experiments below is set be a uniform distribution over the action space given any state, i.e., [a(a) ss) 지 for
p the state transition
any s E and a E A. We then evaluate the performance of the obtained policy in the unperturbed environment. At each time t, the policy we evaluate is the greedy-policy w.r.t. the current estimate of the Q-function, i.c., (s) = arg max, Qe a). A Monte-Carlo method with horizon 100 used to evaluate the accumulated discounted reward of the learned policy the unperturbed MDP. We take the average over 30 trajectories. More details are provided in the appendix.
In Figure D and Figure 2 we plot the accumulated discounted reward of both algorithms under different p and It for both problems. The upper and lower envelopes of the curves correspond to the 95 and 5 percentiles of the 30 trajectories, respectively. It can be seen that overall our robust Q-learning algorithm achieves a much higher reward than the vanilla Q-learning. This demonstrates the robustness of our robust Q-learning algorithm to model uncertainty. Moreover, p and R getting

---

5000 #200ATOI
accurs
300
TOOUSE DuNarring TRSTeccunt WARTIN
O notvisbuu Cleamirg
IStust (3NUTTA convesbunt Q1numm1
number
(a) p=0.1, R=0.1
(b) p=0.05, R=0.2
(c) p=0.1, R=0.2
Figure I: Frozenl Lakev--. robust Q-learning v.s. non-robust Q-learning.
aicrestted rewwrdd
sccur Auccsa dooourto noourooo roward
RabUst O Criaming Mar IEBMAR C Meaanrng
Rubust O leminng Nenvebbrr Qreaminng
Retust O learring Nom-noount 5) M-aaming
samples
(a) p=0.1, R=0.1
(b) p-055, R=0.2
(c) p=0.1, R=0.2
Figure 2: CartPole-vO: robust Q-learning v.s. non-robust Q-learning.
larger, i.e., the MDP that learn the policy deviates from the MDP test the policy, the advantage of our robust Q-learning algorithm is getting more significant compared to the vanilla Q-learning algorithm.
6.2 Robust TDC with Linear Function Approximation
In this section we compare our robust TDC with the vanilla non-robust TDC with linear function approximation the x 4 Frozen Lake problem. The problem setting is the same the in Section 6.1 More details about the experiment setup are provided the appendix.
We implement the two algorithms using samples from the perturbed MDP both for 30 times, and 1, 2......0., 30. We then compute the squared gradient norm
obtain sequences of (0:)2=,, [0)]2 on the true unperturbed MDP, and whether {0 converges some stationary points on the true unperturbed MDP. In Fig. 3 we plot the average squared gradient norm [[)]( for different and R. The upper and lower envelops are the 95 and 5 percentiles of the 30 curves. It can be seen that our robust TDC converges much faster than vanilla TDC, and as the model mismatch between the training and test MDPs enlarges, the vanilla TDC may diverge (Fig. Bee). while robust TDC still converges to some stationary point. Also, the robust TDC has a much smaller variance, which indicates much stable behavior under model uncertainty.
Rozust
Robust TDC
Sabur
Non-eebunt
40
(a) 0.0.1, R=0.1
(b) 0=055, R=0.2
(c) 0.1. R=0.2
Figure 3: FrozenLake-ve | of robust TDC and non-robust TDC.

---

6.3 Comparison with The Adversarial Training Approach
We also compare our robust Q-learning with Robust Adversarial Reinforcement Learning (RARL) in [Pinto et al. 2017]. To apply their algorithm to our problem setting, we model the nature as an adversarial player, and its goal is minimize the reward that the agent receives. The action space And of the nature is to be the state space Aed - S. Then the perturbed training environment can be viewed as an adversarial model: both the agent and the adversary take actions au God. then the environment will transit state oad with probability R and transit following the unperturbed MDP ph- with probability 1 - R. The goal of the maximize its accumulated reward, while the goal of the natural is to minimize it.
Following the RARL algorithm (Pinto et al. 2017 in each iteration of the training, we first fix the adversarial policy and use Q-learning to optimize the agent's policy and obtain the Q-table Q₁- Then we fix the agent's 's policy and optimize the adversarial policy.
After each training iteration, we test the performance of the greedy policies w.r.t. Q-tables obtained from robust Q-learning and RARL. The testing environment is set to be the worst-case, i.e., after the agent takes action, the environment transits the state which has the minimal value function (arg minges (s))) with probability p. We plot the accumulated discounted rewards of both algo- rithms against number of training iterations under different parameters. We set 0.2 and y 0.9. It can be seen from Fig. that our robust Q-learning achieves a higher accumulative reward, and thus is more robust that the RARL algorithm in [Pinto al. 2017 Also our robust Q-learning is more
stable during training, i.e., the variance is smaller.
0000 40000
Robust G kemiing FAIL
Fobust leemiig PARL
Ropust St mn RARL
sumber spocts
number of spochs
number of apochs
p=0.1, R=0.1
(b) p=0.55, R=0.2
(c) p=0.1, R=0.2
Figure 4: Taxi-v3: robust Q-learning v.s. RARL.
Conclusion
In this paper, we develop novel approach for solving model-free robust RL problems with model uncertainty. Our algorithms can be implemented in an online and incremental fashion, do not require additional memory than their non-robust counterparts. We theoretically proved the convergence of our algorithms under no additional assumption on the discount factor, and further characterized their finite-time error bounds, which match with their non-robust counterparts (within a constant factor). Our approach can be readily extended to robustify TD, SARSA and other GTD algorithms. Limitations: also of future interest to investigate robustness to reward uncertainty, and other types of uncertainty sets, e.g., ones defined by KL divergence, Wasserstein distance and total variation. Negative societal impact: To the best of the authors' knowledge, this study does not have any potential negative impact on the society.
8 Acknowledgment
The work of Y. Wang and S. Zou was supported by the National Science Foundation under Grants CCF-2106560 and CCF- 2007783.
10

---

References
Mohammed Amin Abdullah, Hang Ren, Haitham Bou Ammar, Vladimir Milenkovic, Rui Luo, Mingtian Zhang, and Jun Wang. Wasserstein robust reinforcement learning. arXiv preprint arX.v: 13/9/, 2019.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
Kavosh Asadi and Michael Littman. An alternative softmax operator reinforcement learning. In Proc. International Conference on Machine Learning (ICML), volume 70, pages 243-252. JMLR, 2017.
Christopher G Atkeson and Jun Morimoto. Nonparametric representation of policies and value functions: A trajectory-base approach. In Proc. Advances in Neural Information Processing Systems (NIPS) pages 1643-1650, 2003.
Kishan Panaganti Badrinath and Dileep Kalathil. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In Proc. International Conference on Machine Learning (ICML), pages 511-520. PMLR, 2021.
J Andrew Bagnell, Andrew Ng, and Jeff G Schneider. Solving uncertain markov decision. 2001.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings, pages 30-37. Elsevier, 1995.
Carolyn L Beck and Rayadurgam Srikant. Error bounds for constant step-size Q-learning. Systems & control letters, 61 (12): 100--1208, 2012.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods, arXiv preprint arXiv:I906.01700 2019.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Proc. Annual Conference Learning Theory (CoLT), pages 1691-1692. PMLR, 2018.
Shalabh Bhatnagar, Doina Precup, David Silver, Richard S Sutton, Hamid Maci, and Csaba Szepesvári. Convergent temporal-diffeee differennc learning with arbitrary smooth function approximation, In Proc. Advances in Neural Information Processing Systems (NIPS), volume 22, pages 1204-1212, 2009.
Vivek S Borkar and Sean P Meyn. The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447-469, 2000.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. OpenAl Gym. arXiv preprint 16Xiv: 2016.
Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural temporal-different learning con- verges to global optima. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 11312-11322 2019.
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. arXiv preprint arXiv:2007.06558. 2020.
Zaiwei Chen, Sheng Zhang, Thinh T Doan, Siva Theja Maguluri, and John-Paul Clarke. Performance of Q-learning with linear function approuimation: Stability and finite-time analysis. arXiv preprint 1rXiv:990.111422 2019.
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning. Proceedings of Machine Learning Research, 75:1-35, 2018.

---

Gal Dalal, Balázs Szörényi, and Gugan Thoppe. A tale of two-timee -ro-timeselle reinforcement learning with the tightest finite-time bound. In Proc. Conference on Artificial Intelligence (AAAI), pages 3701-3708, 2020.
Dalal, Gal and Szörényi, Balázs and Thoppe, Gugan and Mannor, Shie. Finite sample analyses for TD(O) with function approximation. In Proc. AAAI Conference on Artificial Intelligence (AAAI), pages
2018.
Thinh Doan. Finite-time analysis and restarting scheme for linear two-time-scale stochastic approximation. SIAM Journal on Control and Optimization, 59(4):2798-2819, 2021.
Eyal Even-Dar, Yishay Mansour, and Peter Bartlett. Learning rates for Q-learning, Journal of machine learning Research, 5(1), 2003.
Harsh Gupta, R Srikant, and Lei Ying. Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 4706-4715, 2019.
Linfang Hou, Liang Pang. Xin Hong, Yanyan Lan, Zhiming Ma, and Dawei Yin. Robust reinforcement learning with Wasserstein constraint. arXiv preprint (xXxx:0006000945 2020.
Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. In Proc. International Conference on Learning Representations (ICLR), 2017.
Peter Huber. A robust version of the probability ratio test. The Annals of Mathematical Statistics, pages 1753-1758, 1965.
Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280. 2005.
Maxim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, and Hoi-To Wai. Finite time analysis of linear two-timescale stochastic approximation with Markovian noise. In Proc. Annual Conference on Learning Theory (CoLT), pages 2144-2203, PMLR, 2020.
Jernej Kos and Dawn Song. Delving into adversarial attacks on deep policies. In Proc. International Conference on Learning Representations (ICLR), 2017.
Harshat Kumar, Alec Koppel, and Alejandro Ribeiro. On the sample complexity of actor-critic method for reinforcement learning with function approximation. arXiv preprint arXiv: 2019.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Gen Li, Changxiao Cai, Yuxin Chen, Yuantao Gu, Yuting Wei, and Yuejie Chi. Is Q-learnin minimax optimal? A tight sample complexity analysis. arXiv preprint 1XXi:22022.0548, 2021.
Shiau Hong Lim, Huan Xu, and Shie Mannor. Reinforcement learning in robust Markov decision processes. In Proc. Advances in Neural Information Processing Systems (NIPS), pages 701-709, 2013.
Yen-Chen Lin, Zhang- Wei Hong, Yuan-Hong Liao, Meng-Li Shih, Ming- Yu Liu, and Min Sun. Tactics of adversarial attack deep reinforcement learning agents. In Proc. International Joint Conferences on Artificial Intelligence (IJCAI), pages 3756-3762, 2017.
Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Finite Finite-sample analysis of proximal gradient TD algorithms. In Proc. International Conference on Uncertainty in Artificial Intelligence (UAI), pages 504-513. Citeseer, 2015.
Shaocong Ma, Yi Zhou, and Shaofeng Zou. Variance-reduced off-policy TDC learning: Non- asymptotic convergence analysis. In Proc. Advances Neural Information Processing Systems (NeurIPS), volume 33, pages 14796-14806, 2020.
12

---

Shaocong Ma, Yi Zhou, and Shaofeng Zou. Greedy-GO with variance reduction: Finite-time analysis and improved complexity. In Proc. International Conference on Learning Representations (ICLR), 2021.
Hamid Reza Maei. Gradient temporal-difference learning algorithms. Thesis, University of Alberta, 2011.
Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, and Richard $ Sutton. Toward off-policy learning control with function approximation. In Proc. International Conference on Machine Learning (ICML), pages 719-726, 2010.
Ajay Mandlekar, Yuke Zhu, Animesh Garg, Li Fei-Fei, and Silvio Savarese. Adversarially robust policy learning: Active construction of physically-plausee perturbations. In 2017 IEEE/RSJ International Conference Intelligent Robots and Systems (IROS), pages 3932-3939. IEEE, 2017.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In Proc. International Conference on Machine Learning (ICML), pages 6820-682 6829. PMLR, 2020.
Jun Morimoto and Kenji Doya. Robust reinforcement learning. Neural computation, 17(2):335-35, 2005.
Arnab Nilim and Laurent El Ghaoui. Robustness in Markov decision problems with uncertain transition matrices. In Proc. Advances in Neural Information Processing Systems (NIPS), pages 839-80 846, 2004.
Anay Pattanaik, Zhenyi Tang, Shuijing Liu, Gautham Bommannan, and Girish Chowdhary. Robust deep reinforcement learning with adversarial attacks. In Proc. International Conference on Autonomous Agents and MultiAgent Systems, pages 2040-2042, 2018
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. In Proc. International Conference on Machine Learning (ICML), pages 2817-2826.
PMLR, 2017.
Shuang Qiu, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. On the finite-time convergence of actor-critic algorithm. In Proc. Optimization Foundations for Reinforcement Learning Workshop at Advances Neural Information Processing Systems (NeurIPS). 2019.
Guannan Qu and Adam Wierman. Finite-time analysis of asynchronous stochastic approximation and Q-learnin. In Proc. Annual Conference on Learning Theory (CoLT), pages 3185-3205. PMLR, 2020.
Aravind Rajeswaran, Sarvjeet Ghotra, Balaraman Ravindran, and Sergey Levine. Epopt: Learning robust neural network policies using model ensembles. In Proc. International Conference on Learning Representations (ICLR), 2017.
Aurko Roy, Huan Xu, and Sebastian Pokutta. Reinforcement learning under model mismatch. In Proc. Advances Neural Information Processing Systems (NIPS), pages 3046-3055, 2017.
Jay K Satia and Roy E Lave Jr. Markovian decision processes with uncertain transition probabilities. Operations Research, 21(3):728-740, 1973.
R. Srikant and Lei Ying. Finite-time enror bounds for linear stochastic approximation and TD learning.
In Proc. Annual Conference on Learning Theory (Col.T), pages 2803-2830, 2019.
Jun Sun, Gang Wang, Georgios B Giannakis, Qinmin Yang, and Zaiyue Yang. Finite-sample analysis of decentralized temporal-difference learning with linear function approximation. In Proc. International Conference Artifical Intelligence and Statistics (AISTATS), 2020.
Richard Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction, Second Edition.
The MIT Press, Cambridge, Massachusetts, 2018.
13

---

Richard S Sutton, Csaba Szepesvári, and Hamid Reza Maei. A convergent O()) algorithm for off policy temporal-ditee differrnccee learning with linear function approximation. In Proc. Advances in Neural Information Processing Systems (NIPS), volume 21, pages 1609-1616. MIT Press, 2008.
Richard S Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for temporal-differen learn- ing with linear function approximation. In Proc. International Conference on Machine Learning (ICML), pages 993-1000, 2009.
Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust MDPs using function approximation. In Proc. International Conference on Machine Learning (ICML), pages 181-189. PMLR, 2014.
Eugene Vinitsky, Yuqing Du, Kanaad Parvate, Kathy Jang. Pieter Abbeel, and Alexandre Bayen. Robust reinforcement learning using adversarial populations. arXiv preprint arXiv:2008.01825, 2020.
Hoi-To Wai, Mingyi Hong. Zhuoran Yang, Zhaoran Wang. and Kexin Tang. Variance reduced
policy evaluation with smooth function approximation. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 32. pages 5784-5795, 2019.
Martin J Wainwright. Variance-reduced Q-learning is minimax optimal. arXiv preprint
19Xiv:1906.04000 2019.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. Proc. International Conference on Learning Representations (ICLR), 2020.
Yue Wang and Shaofeng Zou. Finite-sample analysis of Greedy-GQ with linear function approxi- mation under Markovian noise. In Proc. International Conference on Uncertainty in Artificial Intelligence (UAI). pages 11 11-20. PMLR, 2020.
Yue Wang, Shaofeng Zou, and Yi Zhou. Non-asymptotic analysis for two time-scale TDC with general smooth function approximation. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021.
Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust Markov decision processes. Mathe- matics of Operations Research, 38(1):153-183, 2013.
Yue Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A finite time analysis of two time-scale actor critic methods. arXiv preprint vrXiv:2005.0/3355 2020.
Tengyu Xu and Yingbin Liang. Sample complexity bounds for two timescale value-based reinforce- ment learning algorithms. In Proc. International Conference Artifical Intelligence and Statistics (AISTATS), pages 811-819. PMLR, 2021.
Tengyu Xu, Shaofeng Zou, and Yingbin Liang. Two time-scale off-policy TD learning: Non- asymptotic analysis over Markovian samples. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 10633-10644 2019.
Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 8353-8365, 2019.
Kaiqing Zhang, Bin Hu, and Tamer Basar. On the stability and convergence of robust adversarial reinforcement learning: A case study on linear quadratic systems. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020a.
Kaiqing Zhang. Tao Sun, Yunzhe Tao, Sahika Genc, Sunil Mallya, and Tamer Basar. Robust multi- agent reinforcement learning with model uncertainty. In Proc. Advances in Neural Information Processing Systems (NeuriPS), volume 33, 2020b.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for SARSA with linear function approximation. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 8665-8675, 2019.
14


Reviews:
[{"review_id": "_xAex1jw7kS", "reviewer": "Reviewer_VZkh", "summary": "This paper focuses on model free robust Q-learning that can be implemented online. The authors estimate the unknown uncertainty set (R-contamination model) with current samples. Under the perfect duality condition they obtain the bellman operator which optimize their robust objectives. They propose two different algorithms: one for tabular case and another one with function approximation for problems with large state and action spaces. The robust algorithms presented in the paper converges as fast as their non-robust counterparts. They also provide empirical analysis to show the usefulness of their proposed methods.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The paper is well written and different ideas flow smoothly. The authors were able to make the content comprehensible.\n(a)\tTheir model-free approach requires less space complexity compared to model based method while being robust to uncertainty.\n(b)\tThey were able to prove that their Q-learning algorithm converges asymptotically to the optimal value function.\n(c)\tThey prove that their algorithm converges as quickly as the vanilla Q-learning while being robust to uncertainty.\n(d)\tThey provide a linear function approximation of their algorithm (Robust TDC) which can be used in domains with large state and action spaces.\n\nThe paper does clearly explain how they are different from the previous works which mostly address Non-robust model based RL algorithms. Their algorithm is robust to model uncertainty, model free and can be used online while maintaining the advantages of less space complexity and same convergence complexity as standard non-robust Q learning.\n\nThe authors only compare their robust Q-learning method against the standard Q-learning. It can be interesting to see how their algorithm perform when compared against other methods, for example different variants of policy gradient, and actor critic methods.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "YTfUT8WY-9", "reviewer": "Reviewer_Qzzj", "summary": "The authors consider the robust reinforcement learning with uncertainty in the transition. A robust Q-learning algorithm is proposed for tabular MDPs and a robust TDC algorithm is proposed for compatibility of (linear) function approximation. Convergence rates are proved for both of the proposed algorithms. Empirical studies show that the two algorithms work for perturbed MDPs.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The presentation (writing quality and clarity) is good until the section of robust TDC. The algorithm design is a solid contribution. Below are some major concerns.\n\n1. The projection $\\Pi$ should be presented with more clarity: Line 228--should include an explicit expression, which I believe would not take too much space. Line 248--since there is no explicit expression of $\\Pi$, it is not completely clear from the context why the equation after \"we know that\" holds.\n\n2. Two-timescale: While the convergence guarantee involving two stepsizes, the final simplified rate is obtained via setting the two timescales the same $O(1/T^{0.5})$. This makes me wonder: is two-timescale design/analysis really necessary?\n\n3. Experiment and limitation: The setting for the experiments is $p\\cdot \\mathrm{uniform} + (1 - p)\\cdot p_s^a$, which completely falls into the $R$-contamination uncertainty set. The results do show that the proposed algorithms work better than their vanilla counterparts. There are some cited works on robust RL. I think it would be better if the authors add comparisons with the methods proposed in the previous works in the experiment section. Moreover, even compared to the vanilla algorithms, do the robust versions always work better? What if (i) the MDP is not perturbed? (ii) the MDP is perturbed in a way that the $R$-contamination fails to cover? It would be nice if the authors can add discussion to such limitations and also add experiments to show what happens in those \"unfavorable\" cases.\n\nBelow are some minor comments:\n\n4. The role of $K$: I feel that the radius $K$ plays an important role in robust TDC. From the view of reproducing kernel Hilber space, if $K$ is large enough, then with suitable feature, the model misspecification errors caused by the function approximation can be very small. I think the authors need to discuss this constant more. In addition, the choice of $K$ should also be mentioned in the experiment section. (This issue is less robustness related though) \n\n5. Typo: Line 103 -- \"provides\", Line 246 -- definition of $C$ should be outer product. Clarity: Line 255 & 266/ Eq(17, 18) -- what kind of norm is used? Assumption 5 -- is it for all $\\pi$?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "OkRrrG135x2", "reviewer": "Reviewer_c2hD", "summary": "I thank the authors for their responses. They main point of remaining concern seems to be the necessity of analysis/evaluation under model misspecification. I feel like this concern is quite significant, but would defer to better experts in the field.\n\n=====\n\nThe paper presents robust versions of the Q-learning and TDC algorithms and analyzes their rate of convergence in tabular and linear-approximation representations.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "There's one central point of high significance and (to my knowledge) originality in this paper, which is the idea of thinking of each individual data point as a degenerate model, and showing that being robust w.r.t. each point averages out to being robust to the average. The analysis itself is incremental (i.e. doesn't introduce new tools) but strengthens the result with guarantees — it's also interesting that they nearly match guarantees without robustness. The paper is also written very clearly.\n\nAs a non-expert in robust RL, I was missing some justification of the setting. An adversary that can perturb each step independently and with knowledge of past agent actions seems very strong, and robustness to it may give an overly cautious agent. It's also unclear to me why a uncertainty set of the form (4) is reasonable (e.g. where would it be applicable? how does it compare with KL level sets?), and in what sense the true dynamics is its “centroid”.\n\nIt makes sense to leave proofs for an appendix, but this should be indicated clearly. The authors should also consider providing some intuitive overview of the proofs, particularly involving the novel aspects. For example, a discussion of how (6) averages out to provide convergence can be insightful.\n\nThe experiments are very limited, including only two very simple domains, with 6.2 even excluding one of them (why?). How was R selected in each experiment?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately address the limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "-yPx6j5SaMb", "reviewer": "Reviewer_G5cv", "summary": "This paper considers the model-free robust reinforcement learning, where the uncertainty set is assumed to be unknown. The authors propose a robust Q-learning algorithm for tabular settings and a robust TDC algorithm for function approximation settings. The authors theoretically analyze the converge properties for these two algorithms. Numerical experiments demonstrate the robustness of the proposed methods.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "This paper is theoretically sound. The authors present the analyses in detail, and the convergence guarantee is very nice. The algorithm and assumptions are natural in many applications. The paper is well-written. Moreover, the authors provide numerical experiments to show the effectiveness of the proposed methods. When considering the function approximation setting, the authors propose the TDC algorithm, which corresponds to the policy evaluation phase. It will be better if the authors could provide a brief discussion about the robust policy improvement.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Based on the reviews and the discussion afterwards, my recommendation weighs towards acceptance. While the reviewers reached a consensus that the algorithms make novel and solid contributions, there remain some criticisms. First, the experiments can be made much more solid and comprehensive by adding previous robust RL methods as baselines, showing the tradeoff between robustness and pure performance, and presenting the performance evaluation in the face of misspecified uncertainty set. Second, I encourage the authors to also add discussion (and possibly theories) to address the limitation of the R-contamination model. I hope that the above concerns, along with other clarity issues raised by the reviewers, are addressed in the camera-ready version.
Decision: Accept (Poster)