Online Robust Reinforcement Learning with Model Uncertainty

Abstract:
Robust reinforcement learning (RL) is to find a policy that optimizes the worstcase 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 a single sample trajectory sequentially, 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 Qlearning 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.

heading: 1 Introduction
text: 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 a learned policy will be deployed is the same one that was used to generate the policy, which is 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 of 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, Iyengar, 2005], where the transition kernel of the MDP is not fixed and lies in an uncertainty set, and the goal is to learn a policy that performs well under the worst-case MDP in the uncertainty set. In [Bagnell et al., 2001, Nilim and El Ghaoui, 2004, Iyengar, 2005], it was assumed that the uncertainty set is known beforehand, i.e., model-based approach, and dynamic programming can be used to find the optimal robust policy.
The model-based approach, however, requires a model of the uncertainty set known beforehand, and needs a large memory to store the model when the state and action spaces are large, which make it less applicable for many practical scenarios. This motivates the study in this paper, model-free robust RL with model uncertainty, which is to learn a robust policy using a single sample trajectory from a misspecified MDP, e.g., a simulator and a similar environment in which samples are easier to collect 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
35th Conference on Neural Information Processing Systems (NeurIPS 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-policy learning, which we refer to as the "off-transition-kernel" setting. Therefore, the learning may be unstable and could diverge especially when function approximation is used [Baird, 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 [Huang et al., 2017, Kos and Song, 2017, Lin et al., 2017, Pattanaik et al., 2018, Mandlekar et al., 2017] and theR-contamination model in robust detection (called -contamination model in [Huber, 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., 2017], where the uncertainty set is relaxed to one not depending on the misspecified MDP that generates samples so 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 in [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 a discount factor close to 1 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 a given policy under the worstcase MDP in the uncertainty set. As mentioned before, the robust RL problem is essentially "off-transition-kernel", and therefore non-robust methods with function approximation may diverge [Baird, 1995] (also see our experiments). We develop a novel extension of the gradient TD (GTD) method [Maei 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 a 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 our experiments, our robust Q-learning algorithm achieves a much higher reward than the vanilla Q-learning algorithm 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.

heading: 1.1 Related Work
text: Model-Based Robust MDP. The framework of robust MDP was investigated in [Iyengar, 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-based, which assume beforehand 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 is equivalent to a 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 in [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 a 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., [Huang et al., 2017, Kos and Song, 2017, Lin et al., 2017, Pattanaik et al., 2018, Mandlekar et al., 2017]. Despite the empirical success of 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 in 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 1 in practice. Moreover, only asymptotic convergence was established in [Roy et al., 2017]. In this paper, we do not relax the uncertainty set, and instead propose an online approach to estimate it. Our algorithms converge without the need of the condition on 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., 2021]. 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 al., 2019, Sun et al., 2020]. Q-learning and SARSA with linear function approximation were investigated in [Zou et al., 2019, Chen et al., 2019]. The finite-time error bounds for the gradient TD algorithms [Maei et al., 2010, Sutton et al., 2009, Maei et al., 2010] were further developed recently in [Dalal et al., 2018, Liu et al., 2015, Gupta et al., 2019, Xu et al., 2019, Dalal et al., 2020, Kaledin et al., 2020, Ma et al., 2020, Wang and Zou, 2020, Ma et al., 2021, Doan, 2021]. There are also finite-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., 2020, Cen et al., 2020, Bhandari and Russo, 2019, Agarwal et al., 2021, 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.

heading: 2 Preliminaries
text: Markov Decision Process. An MDP can be characterized by a tuple (S,A,P, c, γ), where S and A are the state and action spaces, P = { pas ∈ ∆|S|, a ∈ A, s ∈ S } is the transition kernel1, c is the cost function, and γ ∈ [0, 1) is the discount factor. Specifically, pas denotes the distribution of the next state if taking action a at state s. Let pas = {pas,s′}s′∈S, where pas,s′ denotes the probability that the environment transits to state s′ if taking action a at state s. The cost of taking action a at state s is given by c(s, a). A stationary policy π is a mapping from S to a distribution over A. At each time t, an agent takes an action At ∈ A at state St ∈ S. The environment then transits to the next state St+1 with probability pAtSt,St+1 , and the agent receives cost given by c(St, At). The value function of a policy π starting from any initial state s ∈ S is defined as the expected accumulated discounted cost by following π: E [ ∑∞ t=0 γ
tc(St, At)|S0 = s, π], and the goal is to find the policy π that minimizes the above value function for any initial state s ∈ S. 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 κ = (P0,P1, ...), where Pt ∈ P,∀t ≥ 0, and P is the uncertainty set of the transition kernel. The sequence κ can be viewed as the policy of the nature, and is adversarially chosen by the nature [Bagnell et al., 2001, Nilim and
1∆n denotes the (n− 1)-dimensional probability simplex: {(p1, ..., pn)|0 ≤ pi ≤ 1, ∑n i=1 pi = 1}.
El Ghaoui, 2004, Iyengar, 2005]. Define the robust value function of a policy π as the worst-case expected accumulated discounted cost following a fixed policy π over all transition kernels in the uncertainty set:
V π(s) = max κ Eκ [ ∞∑ t=0 γtc(St, At)|S0 = s, π ] , (1)
where Eκ denotes the expectation when the state transits according to κ. Similarly, define the robust action-value function for a policy π: Qπ(s, a) = maxκ Eκ [ ∑∞ t=0 γ
tc(St, At)|S0 = s,A0 = a, π] . The goal of robust RL is to find the optimal robust policy π∗ that minimizes the worst-case accumulated discounted cost:
π∗ = argmin π V π(s),∀s ∈ S. (2)
We also denote V π ∗ and Qπ ∗ by V ∗ and Q∗, respectively, and V ∗(s) = mina∈AQ∗(s, a).
Note that a transition kernel is a collection of conditional distributions. Therefore, the uncertainty set P of the transition kernel can be equivalently written as a collection of Pas for all s ∈ S, a ∈ A, where Pas is a set of conditional distributions p a s over the state space S. Denote by σP(v) , maxp∈P(p
>v) the support function of vector v 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, 2004] The following perfect duality condition holds for all s ∈ S:
min π max κ
Eκ [ ∞∑ t=0 γtc(St, At) ∣∣π, S0 = s] = max κ min π Eκ [ ∞∑ t=0 γtc(St, At) ∣∣π, S0 = s] . (3)
The optimal robust value function V ∗ satisfies V ∗(s) = mina∈A(c(s, a) + γσPas (V ∗)), and the optimal robust action-value function Q∗ satisfies Q∗(s, a) = c(s, a) + γσPas (V ∗).
Define the robust Bellman operator T by TQ(s, a) = c(s, a) + γσPas (mina∈AQ(s, a)). It was shown in [Nilim and El Ghaoui, 2004, Iyengar, 2005] that T is a contraction and its fixed point is the optimal robust Q∗. When the uncertainty set is known, so that σPas can be computed exactly, V
∗ and Q∗ can be solved by dynamic programming [Iyengar, 2005, Nilim and El Ghaoui, 2004].

heading: 3 R-Contamination Model For Uncertainty Set Construction
text: In this section, we construct the uncertainty set using the R-contamination model.
Let P = {pas , s ∈ S, a ∈ 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 1, from which we can take samples to learn a policy that will be deployed in a similar environment 2. The goal is to learn a policy using samples from P that performs well when applied to 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 et 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:
Pas = { (1−R)pas +Rq|q ∈ ∆|S| } , s ∈ S, a ∈ A, for some 0 ≤ R ≤ 1. (4)
Here, pas is the centroid of the uncertainty set P a s at (s, a), which is unknown, and R is the design parameter of the uncertainty set, which measures the size of the uncertainty set, and is assumed to be known in the algorithm. We then let P = ⊗ s∈S,a∈A P a s .
Remark 1. R-contamination model is closely related to other uncertainty set models like total variation and KL-divergence. It can be shown that R-contamination set certered at p is a subset of total variation ball : { (1−R)p+Rq|q ∈ ∆|S| } ⊂ { q ∈ ∆|S||dTV(p, q) ≤ R } . Hence the total variation uncertainty set is less conservative than our R-contamination uncertainty set. KL-divergence
moreover can be related to total variation using Pinsker’s inequality, i.e., dTV(p, q) ≤ √ 1 2dKL(p, q).

heading: 4 Tabular Case: Robust Q-Learning
text: In this section, we focus on the tabular case with finite state and action spaces. We focus on the asynchronous setting where a 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 σPas (·), and then design our robust Q-learning algorithm. We propose an efficient and data-driven approach to estimate the unknown pas and thus the unknown uncertainty set Pas for any s ∈ S and a ∈ A. Specifically, denote the sample at t-th time step by Ot = (st, at, st+1). We then use Ot to obtain the maximum likelihood estimate (MLE) p̂t , 1st+1 of the transition kernel patst , where 1st+1 is a probability distribution taking probability 1 at st+1 and 0 at other states. This is an unbiased estimate of the transition kernel patst conditioning on St = st and At = at. We then design a sample-based estimate P̂t , { (1−R)p̂t +Rq|q ∈ ∆|S|
} of the uncertainty set Patst . Using the sample-based uncertainty set P̂t, we construct the following robust Q-learning algorithm in Algorithm 1. For any t, σ
P̂t (Vt) can be easily computed: σP̂t(Vt) =
Algorithm 1 Robust Q-Learning Initialization: T , Q0(s, a) for all (s, a) ∈ S×A, behavior policy πb, s0, step size αt
1: for t = 0, 1, 2, ..., T − 1 do 2: Choose at according to πb(·|st) 3: Observe st+1 and ct 4: Vt(s)← mina∈AQt(s, a), ∀s ∈ S 5: Qt+1(st, at)← (1− αt)Qt(st, at) + αt(ct + γσP̂t(Vt)) 6: Qt+1(s, a)← Qt(s, a) for (s, a) 6= (st, at) 7: end for
Output: QT
Rmaxs∈S Vt(s) + (1−R)Vt(st+1). Hence the update in Algorithm 1 (line 5) can be written as
Qt+1(st, at)← (1− αt)Qt(st, at) + αt(ct + γRmax s∈S Vt(s) + γ(1−R)Vt(st+1)). (5)
Compared to the model-based approach, our approach is model-free. It does not require the prior knowledge of the uncertainty set, i.e., the knowledge of pas ,∀s ∈ S, a ∈ A. Furthermore, the memory requirement of our algorithm is |S| × |A| (used to store the Q-table), and unlike the modelbased approach it does not need a table of size |S|2|A| to store pas ,∀s ∈ S, a ∈ A, which could be problematic if the state space is large. Moreover, our algorithm does not involve a relaxation of the uncertainty set like the one in [Roy et al., 2017], which will incur a stringent condition on the discount factor to guarantee the convergence. As will be shown below, the convergence of our Algorithm 1 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 2. (Asymptotic Convergence) If step sizes αt satisfy that ∑∞ t=0 αt =∞ and ∑∞ t=0 α 2 t <∞, then Qt → Q∗ as t→∞ 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 πb and the transition kernel pas ,∀s ∈ S, a ∈ A is uniformly ergodic.
Let µπb denote the stationary distribution over S × A induced by πb and pas ,∀s ∈ S, a ∈ A. We then further define µmin = min(s,a)∈S×A µπb(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: tmix = min { t : maxs∈S dTV(µπ, P (st = ·|s0 = s)) ≤ 14 } , where dTV is the total variation distance.
The following theorem establishes the finite-time error bound of our robust Q-learning algorithm.
Theorem 3. (Finite-Time Error Bound) There exist some positive constants c0 and c1 such that for any δ < 1, any < 11−γ , any T satisfying
T ≥ c0 (
1
µmin(1− γ)5 2 + tmix µmin(1− γ)
) log ( T |S||A|
δ
) log ( 1
(1− γ)2
) , (6)
and step size αt = c1 log(T |S||A|δ )
min (
1 tmix , 2(1−γ)4 γ2
) ,∀t ≥ 0 we have with probability at least 1−6δ,
‖QT −Q∗‖∞ ≤ 3 .
From the theorem, we can see that to guarantee an -accurate estimate, a sample size Õ( 1µmin(1−γ)5 2 + tmix µmin(1−γ) ) (up to some logarithmic terms) is needed. This complexity matches with the one for the vanilla Q-learning in [Li et al., 2020] (within a constant factor), while our algorithm also guarantees robustness to MDP model uncertainty. Our algorithm design and analysis can be readily extended to robustify TD and SARSA. The variance-reduction technique [Wainwright, 2019] can also be combined with our robust Q-learning algorithm to further improve the dependency on (1− γ).

heading: 5 Function Approximation: Robust TDC
text: 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, e.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 (1) for a given policy π under the worst-case MDP transition kernel in the uncertainty set. Note that for robust RL with model uncertainty, any policy evaluation problem can be viewed as "off-transition-kernel", as it is to evaluate the value function under the worst-case MDP using samples from a different MDP. Since the TD algorithm with function approximation may diverge under off-policy training [Baird, 1995] and importance sampling cannot be applied here due to unknown transition kernel, in this paper we generalize the GTD method [Maei et al., 2010, Maei, 2011] to the robust setting.
Let { φ(i) : S→ R, i = 1, . . . , N } be a set of N fixed base functions, where N |S||A|. In particular, we approximate the robust value function using a linear combination of φ(i)’s: Vθ(s) =∑N i=1 θ iφ (i) s = φ>s θ, where θ ∈ RN is the weight vector.
Define the following robust Bellman operator for a given policy π:
TπV (s) , EA∼π(·|s)[c(s,A) + γσPAs (V )]
= EA∼π(·|s)
[ c(s,A) + γ(1−R)
∑ s′∈S pAs,s′V (s ′) + γRmax s′∈S V (s′)
] . (7)
We then define the mean squared projected robust Bellman error (MSPRBE) as
MSPRBE(θ) = ‖ΠTπVθ − Vθ‖2µπ , (8)
where ‖v‖2µπ = ∫ v2(s)µπ(ds), µπ is the stationary distribution induced by π, and Π is a projection onto the linear function space w.r.t. ‖ ·‖µπ . We will develop a two time-scale gradient-based approach to minimize the MSPRBE. However, it can be seen that maxs Vθ(s) in (7) is not smooth in θ, which is 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 a LSE(LogSumExp):
T̂πV (s) = EA∼π(·|s)
[ c(s,A) + γ(1−R)
∑ s′∈S pAs,s′V (s ′) + γR · LSE(V )
] , (9)
where LSE(V ) = log(
∑ s e %V (s))
% is the LogSumExp w.r.t. V with a parameter % > 0. Note that when
%→∞, the smoothed robust Bellman operator T̂π → Tπ. 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 T̂π exists for any %, and the fixed points converge to the one of Tπ for large %.
Theorem 4. (1). For any %, T̂π has a fixed point.
(2). Let V1 and V2 be the fixed points of T̂π and Tπ , respectively. Then
‖V1 − V2‖∞ ≤ γR 1− γ log |S| % → 0, as %→∞. (10)
We then denote by J(θ) the smoothed MSPRBE with the LSE operator, and the goal is:
min θ J(θ) = min θ ∥∥∥ΠT̂πVθ − Vθ∥∥∥2 µπ . (11)

heading: 5.1 Algorithm Development
text: In the following, we develop the robust TDC algorithm to solve the problem in (11). We will first derive the gradient of the smoothed MSPRBE, J(θ), and then design a two time-scale update rule using the weight doubling trick in [Sutton et al., 2009] to solve the double sampling problem. Define δs,a,s′(θ) , c(s, a) + γ(1 − R)Vθ(s′) + γRLSE(Vθ) − Vθ(s), where LSE(Vθ) is the LogSumExp function w.r.t. Vθ = θ>φ. Denote by C , Eµπ [ φ>S φS ] . Then,
Eµ[δS,A,S′(θ)φS ] = Φ>D ( T̂πVθ − Vθ ) , where D = diag(µπ(s1), µπ(s2), ..., µπ(s|S|)) and
Φ = (φs1 , φs2 , ..., φs|S|) > ∈ R|S|×N . We know that Π>DΠ = D>Φ(Φ>DΦ)−1Φ>D from [Maei, 2011]. Hence we have
J(θ) = ∥∥∥ΠT̂πVθ − Vθ∥∥∥2
µπ = Eµπ [δS,A,S′(θ)φS ]>C−1Eµπ [δS,A,S′(θ)φS ]. (12)
Then, its gradient can be written as:
− 1 2 ∇J(θ) = −Eµπ [(∇δS,A,S′(θ))φS ]>C−1Eµπ [δS,A,S′(θ)φS ]
= Eµπ [δS,A,S′(θ)φS ]− γEµπ [( (1−R)φS′ +R · ∇LSE(Vθ) ) φ>S ] ω(θ),
where ω(θ) = C−1Eµπ [δS,A,S′(θ)φS ]. It can be seen that to obtain an unbiased estimate of∇J(θ), two independent samples are needed as there exists a 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 ω(θ), and a slow time scale to estimate∇J(θ). Denote the projection by ΠK(x) , argmin‖y‖≤K ‖y − x‖ for any x ∈ RN . Our robust TDC algorithm in Algorithm 2 can be implemented in an online and incremental fashion. If the uncertainty set becomes a singleton, i.e., R = 0, then Algorithm 2 reduces to the vanilla TDC algorithm.

heading: 5.2 Finite-Time Error Bound of Robust TDC
text: Unlike the vanilla TDC algorithm, J(θ) here is non-convex. Therefore, we are interested in the convergence to stationary points, i.e., the rate of ‖∇J(θ)‖ → 0. We first make some standard assumptions which are commonly used in RL algorithm analysis, e.g., [Wang and Zou, 2020, Kaledin et al., 2020, Xu et al., 2019, Srikant and Ying, 2019, Bhandari et al., 2018]. Assumption 2 (Bounded feature). ‖φs‖2 ≤ 1,∀s ∈ S. Assumption 3 (Bounded cost function). |c(s, a)| ≤ cmax,∀s ∈ S and a ∈ A. Assumption 4 (Problem solvability). The matrix C = Eµπ [φSφ>S ] is non-singular with λ > 0 being its smallest eigenvalue.
Algorithm 2 Robust TDC with Linear Function Approximation Input: T ,α, β, %, φi for i = 1, ..., N , projection radius K Initialization: θ0,w0, s0
1: Choose W ∼ Uniform(0, 1, ..., T − 1) 2: for t = 0, 1, 2, ...,W − 1 do 3: Take action according to π(·|st) and observe st+1 and ct 4: φt ← φst 5: δt(θt)← ct + γ(1−R)Vθt(st+1) + γR log( ∑ s e %θ>φs ) % − Vθt(st)
6: θt+1 ← ΠK ( θt + α ( δt(θt)φt − γ ( (1−R)φt+1 +R ∑ s∈S ( e%Vθ(s)φs∑ j∈S e %Vθ(j) )) φ>t ωt )) 7: ωt+1 ← ΠK(ωt + β(δt(θt)− φ>t ωt)φt) 8: end for
Output: θW
Assumption 5 (Geometric uniform ergodicity). There exist some constants m > 0 and ρ ∈ (0, 1) such that for any t > 0, maxs∈S dTV(P(st|s0 = s), µπ) ≤ mρt.
In the following theorem, we characterize the finite-time error 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: β = O ( 1 T b ) , and α = O ( 1 Ta ) , where 12 < a ≤ 1 and 0 < b ≤ a. Then we have that
E[‖∇J(θW )‖2] = O ( 1
Tα + α log(1/α) +
1
Tβ + β log(1/β)
) , (13)
If we further let a = b = 0.5, then E[‖∇J(θW )‖2] = O (
log T√ T
) .
The robust TDC has a matching complexity with the vanilla TDC with non-linear function approximation [Wang et al., 2021], 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 a condition on the discount factor.

heading: 6 Experiments

heading: 6.1 Robust Q-Learning
text: In this section, we compare our robust Q-learning with the vanilla non-robust Q-learning. We use OpenAI 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 learned in a 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 S, and with probability 1− p the state transition is according to the true unperturbed transition kernel. The behavior policy for all the experiments below is set to be a uniform distribution over the action space given any state, i.e., πb(a|s) = 1|A| for any s ∈ S and a ∈ 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.e., πt(s) = argmaxaQt(s, a). A Monte-Carlo method with horizon 100 is used to evaluate the accumulated discounted reward of the learned policy on the unperturbed MDP. We take the average over 30 trajectories. More details are provided in the appendix.
In Figure 1 and Figure 2, we plot the accumulated discounted reward of both algorithms under different p and R 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, as p and R getting
larger, i.e., as the MDP that we learn the policy deviates from the MDP we test the policy, the advantage of our robust Q-learning algorithm is getting more significant compared to the vanilla Q-learning algorithm.

heading: 6.2 Robust TDC with Linear Function Approximation
text: In this section we compare our robust TDC with the vanilla non-robust TDC with linear function approximation on the 4 × 4 Frozen Lake problem. The problem setting is the same as the one in Section 6.1. More details about the experiment setup are provided in the appendix.
We implement the two algorithms using samples from the perturbed MDP both for 30 times, and obtain 30 sequences of {θit}∞t=1, i = 1, 2, ..., 30. We then compute the squared gradient norm ‖∇J(θ)‖2 on the true unperturbed MDP, and see whether {θit}∞t=1 converges to some stationary points on the true unperturbed MDP. In Fig. 3, we plot the average squared gradient norm ‖∇J(θ)‖2 for different p 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. 3(c)), while our robust TDC still converges to some stationary point. Also, the robust TDC has a much smaller variance, which indicates a much stable behavior under model uncertainty.

heading: 6.3 Comparison with The Adversarial Training Approach
text: 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 to minimize the reward that the agent receives. The action space Aad of the nature is set to be the state space Aad , S. Then the perturbed training environment can be viewed as an adversarial model: both the agent and the adversary take actions aa, aad, then the environment will transit to state aad with probability R and transit following the unperturbed MDP paas 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 Qt. Then we fix the agent’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 an action, the environment transits to the state which has the minimal value function (argmins∈S Vt(s)) with probability p. We plot the accumulated discounted rewards of both algorithms against number of training iterations under different parameters. We set α = 0.2 and γ = 0.9. It can be seen from Fig. 4 that our robust Q-learning achieves a higher accumulative reward, and thus is more robust that the RARL algorithm in [Pinto et al., 2017]. Also our robust Q-learning is more stable during training, i.e., the variance is smaller.

heading: 7 Conclusion
text: In this paper, we develop a 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: It is 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.

heading: 8 Acknowledgment
text: The work of Y. Wang and S. Zou was supported by the National Science Foundation under Grants CCF-2106560 and CCF- 2007783.

Review summaries:
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.  =====  The paper presents robust versions of the Q-learning and TDC algorithms and analyzes their rate of convergence in tabular and linear-approximation representations.

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.

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.

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.