Reinforcement learning (RL) has demonstrated remarkable empirical success in simulated environments, with applications spanning domains such as robotics (Kober et al., 1 New York University, Stern School of Business 2 Horizon Robotics Inc., CA, USA 3 Department of Management Science and Engineering, Stanford University, CA, USA 4 Department of Electrical Engineering and Computer Sciences, UC Berkeley, CA, USA 5 Arena Technologies. Correspondence to: Zhengyuan Zhou <zzhou@stern.nyu.edu>.
Proceedings of the 39 th International Conference on Machine Learning, Baltimore, Maryland, USA, PMLR 162, 2022. Copyright 2022 by the author(s).
2013; Gu et al., 2017), computer vision (Sadeghi & Levine, 2016;Huang et al., 2017), finance (Li et al., 2009;Choi et al., 2009;Deng et al., 2017) and games (Silver et al., 2016;2018). More recently, reinforcement learning has also been applied to economic domains such as personalized promotions in revenue management, inventory control in supply chains and scheduling in queueing networks. However, carrying this success to real environments requires an attribute that is often missing in the existing literature on policy learning: robustness, because existing RL algorithms often make the implicit assumption that the environment in which the policy is trained will be the same as the environment in which the policy will be deployed. In other words, a policy is evaluated in the same environment from which the training data has been generated.
While the above assumption is arguably a good starting point 1 for developing a rigorous understanding of algorithmic performance of policy learning, it does not capture the complexity of real-world applications because the discrepancy between training and deployment environments is often common and hard to anticipate (and hence account for) in advance. Two common sources of discrepancies are:
1. Simulator model mis-specification. In many reinforcement learning (RL) applications, a policy is often first trained in a simulator before being deployed in a real environment. However, simulator models often cannot capture the full complexity of the real environment, and hence will be mis-specified. Further, it is hard to know exactly how the real environment differs from the simulator (otherwise, the simulator would have been augmented/modified to account for that). 2. Environment shifts. The underlying environment may shift due to either non-stationarity or a different deployment environment (for the same task). As an example of the latter, a personalized content recommendation 1 Much like supervised learning was first developed under the same assumption, before adversarial training was recognized as a valuable tool to make empirical predictions robust; see, for instance, (Sinha et al., 2018;Goodfellow et al., 2014;Ganin et al., 2016;Zhang et al., 2019;Tramèr et al., 2017). The topic of domain adaptation (Shimodaira, 2000;Saerens et al., 2002;Ben-David et al., 2010;Courty et al., 2016;Ganin et al., 2016;Sun et al., 2020;Arjovsky et al., 2019;Wang & Deng, 2018;Sagawa et al., 2019) is another approach to address covariate shifts in supervised learning, but the new domain is often assumed to be known. engine (learned from existing user browsing data collected in one region or market) may need to be deployed in a different region or market, with different population characteristics. Another example occurs in robotics, where a robot trained to perform certain maneuvers (such as walking (Schulman et al., 2013) or folding laundry (Maitin-Shepard et al., 2010)) in an environment can fail catastrophically (Drew, 2015) in a slightly different environment, where the terrain landscape (in walking) is slightly altered or the laundry object (in laundry folding) is positioned differently.
As a result, to learn an effective policy in practice, one must be cognizant of such discrepancies and take them into account during the training stage in order to learn a policy that is robust to the unknown environment changes that cannot be avoided and are difficult to know in advance. Whereas distributionally robust learning in the simpler supervised learning setting has been extensively studied in the past decade (see Section 1.1), an emerging literature has only recently been initiated to study this problem in the RL context (Si et al., 2020b;Zhou et al., 2021;Yang et al., 2021;Kishan & Kalathil, 2021). In particular, a common and natural formulation adopted therein is to consider distributional shifts for rewards and/or transition probabilities (defined via different divergence measures or distances between probability distributions), and to learn from data (collected from some generative model) the best policy under the worstcase distributional shift, which thus carries a certain level of robustness to the unknown environment shifts.
Currently, all the existing distributionally robust policy learning algorithms mentioned above (Si et al., 2020b;a;Zhou et al., 2021;Yang et al., 2021;Kishan & Kalathil, 2021) are model-based, which estimate the underlying MDP first before provisioning some policy from it. Although model-based methods are often more sampleefficient and easier to analyze, their drawbacks are also wellunderstood (Sutton & Barto, 2018;Franc ¸ois-Lavet et al., 2018): they are computationally intensive; they require more memory to store MDP models and often do not generalize well to non-tabular RL settings. These issues limit the practical applicability of model-based algorithms, which stand in contrast to model-free algorithms that learn to select actions without first learning an MDP model. Such methods are often more computationally efficient, have less storage overhead, and better generalize to RL with function approximation. In particular, Q-learning (Watkins & Dayan, 1992), as the prototypical model-free learning algorithm, has widely been both studied theoretically and deployed in practical applications. However, Q-learning is not robust (as demonstrated in our simulations), and the policy learned by Q-learning in one environment can perform poorly in another under a worst-case shift (with bounded magnitude). As such, we are naturally led to the following research ques-tion:
Can we design a variant of Q-Learning that is distributionally robust?
Robustness has been studied in several settings that are related to (but different from) our investigation. For instance, a rich literature has explored distributionally robust learning and optimization in supervised learning (Bertsimas & Sim, 2004;Delage & Ye, 2010;Hu & Hong, 2013;Shafieezadeh-Abadeh et al., 2015;Bayraksan & Love, 2015;Gao & Kleywegt, 2016;Namkoong & Duchi, 2016;Duchi et al., 2016;Staib & Jegelka, 2017;Shapiro, 2017;Lam & Zhou, 2017;Chen et al., 2018;Volpi et al., 2018;Lee & Raginsky, 2018;Nguyen et al., 2018;Yang, 2020;Mohajerin Esfahani & Kuhn, 2018;Zhao & Jiang, 2017;Abadeh et al., 2018;Zhao & Guan, 2018;Gao et al., 2018;Ghosh & Lam, 2019;Blanchet & Murthy, 2019;Duchi & Namkoong, 2018;Lam, 2019;Duchi et al., 2019), where the underlying testing distribution is still the same as the training distribution, and the learner merely uses the distributional uncertainty (around the empirical distribution) to guard against over-generalization due to lack of data. As such, the statistical learning results in this area focus on the setting where the distributional uncertainty decreases with the sample size (and as such, is part of the algorithm rather than the environment); further, it has been well recognized that under certain conditions, this approach is formally equivalent to regularization (Duchi & Namkoong, 2019;Duchi et al., 2016;Gao et al., 2017;Shafieezadeh-Abadeh et al., 2019), which prevents over-fitting in the small data regime.
On the other hand, learning predictive rules in testing distributions that are different from -and often perturbations oftraining distributions have also been studied in (Sinha et al., 2018;Goodfellow et al., 2014;Ganin et al., 2016;Zhang et al., 2019;Tramèr et al., 2017), where the training procedure is robustified by first perturbing the original dataset with some synthesized noise before solving a empirical risk minimization problem, which has been observed to work well in a robust manner.
Going beyond the supervised learning setting, a related area to ours is distributionally robust Markov decision processes (MDPs) (González-Trejo et al., 2002;Iyengar, 2005;Xu & Mannor, 2010;El Ghaoui & Nilim, 2005;Wiesemann et al., 2013;Wolff et al., 2012;Mannor et al., 2016;Morimoto & Doya, 2005;Yang, 2020). This line of work has studied the known environment MDP setting (hence no learning) and has mainly focused on the computational issues 2 . Closest to our work is the recent distributionally robust policy learning work already mentioned (Si et al., 2020b;Zhou et al., 2021;Yang et al., 2021;Kishan & Kalathil, 2021): (Si et al., 2020b) studies the special case of distributionally robust policy learning in contextual bandits (i.e. horizon is 1), while the other three study the infinite-horizon discounted RL setting.
We design a distributionally robust Q-learning algorithm that has two features beyond the standard Q-learning algorithm. The first feature lies in the new values that the algorithm aims to learn: instead of Q-values, the algorithm now aims to estimate the distributionally robust Q-values. We achieve this by leveraging strong duality to transform the distributionally robust Q-values (an infinite-dimensional object since the distributional uncertainty set is infinitedimensional) into a finite-dimensional quantity, also known as the distributionally robust Bellman operator. Second, we design a novel multi-level Monte-Carlo estimator to unbiasedly estimate the distributionally robust Bellman operator. Through a careful analysis of our estimator's bias and variance (see Theorem 3.7 and Theorem 3.8), we show that the distributionally robust Q-learning algorithm asymptotically converges to optimal distributionally robust policy (Theorem 3.10). As such, our results provide an initial affirmative answer to the open question raised above, and the convergence result provides a distributionally robust counterpart to the well-known asymptotic convergence of Q-learning (Jaakkola et al., 1994). Finally, we provide simulation results to demonstrate the robustness of the policy learned by the proposed distributionally-robust Q-learning algorithm.
The distributionally robust Bellman equation was obtained before in (Iyengar, 2005). However, this is merely a tool for us to solve the problem in the dual space. Our main contribution is to design a distributionally robust Q-learning algorithm based on it. (Xu & Mannor, 2010) does not propose any new algorithm for learning a distributionally robust policy but only proved some properties of distributionally robust MDP. (Yang, 2020) considers the Wasserstein distance and uses a model-based algorithm that is totally different from ours. Our algorithm is the first model-free algorithm ever developed on this problem. Prior to our work, it is not clear at all whether Q-learning can be made robust, since all the existing algorithms in this area are model-based.
computation can be done efficiently in polynomial time, although depending on how such uncertainty sets are specified, some of the proposed algorithms require oracle access to solving an infinitedimensional problem, and hence are infeasible.
with a Simulator
Let M = (S, A, P, R, γ) be a tabular RL environment, where S and A are finite state space and action space respectively, R : S × A → P(R ≥0 ) (the set of random variables that are supported on R ≥0 ) is the randomized reward function, P = {p s,a (•)} (s,a)∈S×A is the transition model, and γ ∈ (0, 1) is the discount factor. We assume that the transition is Markovian, i.e., at each state s ∈ S, if action a ∈ A is chosen, then the subsequent state is determined by the conditional distribution p s,a (•) = p(•|s, a). The decision maker will therefore receive a randomized reward r(s, a). The value function V π (s) provides the expected cumulative discounted reward under the policy π with initial state s ∈ S,
Hence, the optimal value function is:
where Π denotes the class of random policies. It is well known that the optimal value function is the solution of the following Bellman's equation:
From here we define the optimal Q-function, Q * as
Throughout this paper, we impose the following assumption on the rewards. Assumption 2.1. (Bounded rewards) For any (s, a) ∈ S × A, r(s, a) ∈ [0, R max ].
In reality, the transition model P and rewards R in M are subjected to change over time, this motivates us to learn a policy that is robust to certain perturbation in the environment. In particular, we consider the setting of distributionally robust RL, where both transition probabilities and rewards might be perturbed w.r.t. the Kullback-Leibler (KL) divergence D KL (P ∥Q) = log dP dQ dP whenever P ≪ Q (P is absolutely continuous with respect to Q). Remark 2.2. We pick KL divergence simply because it is one common divergence measure that is easy to analyze (given the already complicated nature of the problem). Our results can also be generalized to f -divergence.
In the original environment, let P 0 = {p 0 s,a } (s,a)∈S×A be the transition probabilities, ν 0 be the joint distribution of {r(s, a)} (s,a)∈S×A , where r(s, a) ∼ ν 0 s,a (marginal distribution with respect to (s, a)). To construct the distributional uncertainty setting, for each (s, a) ∈ S × A, we define robust KL balls that are centered at p 0 s,a and ν 0 s,a by
Here δ > 0 is the level of distributional robustness, and ∆ |S| stands for the |S|-1 dimensional probability simplex. Now we are able to build the uncertainty set P(δ) by the Cartesian product of P s,a (δ) for each (s, a) ∈ S × A. This type of uncertainty set is called (s, a)-rectangular set in standard literature (Wiesemann et al., 2013). Similarly we define R(δ) by the Cartesian product of R s,a (δ) for each (s, a) ∈ S × A. In the distributionally robust framework, the adversarial player is assumed to pick the worst-case transition model and rewards that minimize the expected cumulative discounted reward. To be clear, we define the distributionally robust value function as follows.
Definition 2.3. Given δ > 0 and policy π ∈ Π, the distributionally robust value function V rob,π δ is defined as:
(1)
Following the definition, V rob,π δ measures the quality of a policy π by computing its performance in the worst-case environment among the set of all possible environments that perturb the original transition P 0 and reward distribution ν 0 under a δ-KL ball. The optimal distributionally robust value function is therefore defined by
Following the well known results in (Iyengar, 2005;Xu & Mannor, 2010), we can write down the distributionally robust dynamic programing for the distributionally robust value function V rob,π δ in Equation (1) as follows:
(2)
Moreover, we can write down the distributionally robust Bellman's equation for the optimal value function as follows:
(3)
Note that both Equation (2) and Equation ( 3) are in general computationally intractable since they involve infinite dimensional optimization. To address this issue, we introduce the following strong duality lemma from distributionally robust optimization under KL-perturbation.
Lemma 2.4 ( (Hu & Hong, 2013), Theorem 1). Suppose H(X) has finite moment generating function in the neighborhood of zero. Then for any δ > 0, sup
By Lemma 2.4, we can transform the Equation (2) to the following equation.
As a direct consequence of the Equation (4) (note that the size of Π is finite in the tabular setting, see Theorem 3.2 in (Iyengar, 2005) for a standard proof), the optimal distributionally robust value function V rob, * δ in fact satisfies the following distributionally robust Bellman's equation.
-βδ .
(5)
The Q-learning algorithm determines the optimal Qfunction using point samples. Let π be some random policy such that P(π(s) = a) > 0 for all state-action pairs (s, a) ∈ S × A. Suppose at time t, we draw a sample (s t , a t , r t , s ′ t ) from the environment according to the policy π. Then, Q-learning uses the following update rules
where the step-sizes α t will be properly chosen. The key reason why Q-learning works is that both r t and
Therefore we can use the stochastic approximation theorem to show that Q t converges to Q * with careful choice of step-sizes. For more details, please read (Melo, 2001;Even-Dar et al., 2003).
From Equation (3) and Equation ( 5), we know the optimal distributionally robust Q
By analogy with the Bellman Operator, we can define the δ-distributionally robust Bellman Operator as follows:
Definition 3.1. Given δ > 0 and Q ∈ R S×A , the δdistributionally robust Bellman Operator T rob δ : R S×A → R S×A is defined as
Remark 3.2. We define the δ-distributionally robust Bellman Operator by using its dual form. However, it may be more convenient to use the primal form
Our definition implies that Q rob, * δ is a fixed point of T rob δ . Now suppose we have a simulator that allows us to sample (r, s ′ ) from (ν 0 s,a , p 0 s,a ), can we come up with a nice unbiased estimator of T rob δ (Q)(s, a)? The plug-in estimator of T rob δ (Q)(s, a) is in fact biased (because of the non-linearity). For instance, if we just take one sample, say (s, a, r, s ′ ). The corresponding plug-in estimator of
To address this issue, we propose a new estimator of T rob δ by introducing the multilevel Monte-Carlo method (Blanchet & Glynn, 2015;Blanchet et al., 2019). The formal description of our estimator is defined as follows:
Definition 3.3. Given δ > 0, ε ∈ (0, 0.5) and Q ∈ R S×A , the δ-distributionally robust estimator T rob δ,ε is defined as:
For R rob δ (s, a) and T rob δ (s, a), we firstly sample N ∈ N from the distribution P(N = n) = p n = ε(1 -ε) n , then use the simulator to draw 2 N +1 samples (r i , s ′ i ) from (ν 0 s,a , p 0 s,a ). Finally we define
where
and
Using the estimator T rob δ,ε , our Distributionally Robust Q-Learning algorithm is summarized in Algorithm 1.
Input: Uncertainty radius δ > 0, parameter ε ∈ (0, 0.5).
) through Equation (11) and Equation ( 12) respectively.
Remark 3.4. In Algorithm 1, we can choose any α t which satisfies the Robbins-Monro Condition, i.e.,
δ is an exogenous variable that quantifies the level of conservatism, which we consider as pre-determined (and not part of the algorithm). That said, it can also be from past datasets if they are collected from different environments, in which case the shift can be estimated.
First of all, we introduce Lemma 3.6 which plays a critical role in the proof of convergence of Algorithm 1.
Lemma 3.6. Given δ > 0, 0 < γ < 1, T rob δ is a γcontraction map w.r.t. the infinity norm.
By applying the primal form of T rob δ (Equation ( 7)), we have
Consider any ϵ > 0, suppose p(ϵ) ∈ P s,a (δ) makes
Combining the previous part, we have ∀ϵ > 0,
which implies
By a similar argument, we also have
Hence, there is
Note that the above result is true for any (s, a) ∈ S × A, which implies
Next, we give the key theorem of our estimator T rob δ,ε . Theorem 3.7. Given δ > 0. If Assumption 2.1 holds, then for any ε ∈ (0, 0.5), T rob δ,ε is an unbiased estimator of T rob δ , i.e., ∀Q ∈ R S×A , (s, a) ∈ S × A,
Due to the page limitation, we defer the whole proof of Theorem 3.7 into Appendix B and give a proof outline here. By the law of total probability, we first can get
One key technical point helping us to move on is to understand
s,a e -r(s,a)/α , and β * defined in a similar way. By employing different events defined in Appendix B, we finally can derive
which completes the unbiasedness of R rob δ (s, a). Similar result will give us the unbiasedness of T rob δ (Q)(s, a).
Besides, we introduce another key property of T rob δ,ε . Theorem 3.8. Given δ > 0, ε ∈ (0, 0.5). If Assumption 2.1 holds, then there exists a constant C(δ, ε, ν 0 , P 0 ) > 0 such that for any Q ∈ R S×A and (s, a) ∈ S × A,
The proof of Theorem 3.8 is also deferred to Appendix C. Remark 3.9. For Theorem 3.8, our setting is different from (Blanchet & Glynn, 2015;Blanchet et al., 2019), which requires a careful analysis and a different proof strategy.
One key difference is that expectation terms in Equation ( 6) are inside the log function. However, in (Blanchet & Glynn, 2015;Blanchet et al., 2019), expectations are always at the most outside. The non-linearity of the log function makes the analysis more difficult. Another technical point is we need to understand the optimizers of T rob δ , i.e.,
where proof techniques are different for α * , β * = 0 and α * , β * ̸ = 0.
Finally, combing previous results, we are able to establish the following convergence guarantee for Algorithm 1.
Theorem 3.10. Given δ > 0. If Assumption 2.1 holds, then for any ε ∈ (0, 0.5), Q rob δ,t in Algorithm 1 will converge to Q rob, * δ as t → ∞.
Proof. Following the proof in (Melo, 2001;Even-Dar et al., 2003), we can rewrite the update rule of Algorithm 1 as
where
. Combining Lemma 3.6, Theorem 3.7 and the fact that
Next, by Theorem 3.8, we have
Also note that α t satisfies the Robbins-Monro Condition, these intermediate results then yield the convergence of Algorithm 1 by Theorem 1 of (Jaakkola et al., 1994).
We use a supply chain model to test Algorithm 1 in our numerical experiments. In the supply chain model, the state space In our experiments, due to the limit computation resources, we fix n = 10. Besides, we take h = 1, p = 2, k = 3 and set the discount factor γ = 0.9 with starting from s 1 = 0.
By using standard Q-learning, one can find the non distributionally robust, optimal policy π * for the non perturbed problem, i.e., δ = 0, satisfying
For the distributionally robust setting, we can think the probability distribution of d t is no longer a uniform distribution anymore, which is quite reasonable in reality.
In the simulation, we set δ = 1 as the perturbation parameter. At the k-th step of Algorithm 1, we set the learning rate α k be 1 1+(1-γ)(k-1) to satisfy the Robbins-Monro Condition. We will treat Algorithm 1 as having converged when the infinity norm of the difference between the updated value and the old value is no greater than tolerance = 0.05.
For the parameter ε used in our estimator, we consider ε ∈ {0.49, 0.499.0.5, 0.6}. Note that our Theorem 3.10 only ensures the convergence for ε ∈ (0, 0.5), but we will test some values out of this range. Besides, the reason why we only choose {0.49, 0.499} rather than adding some other smaller ε ∈ (0.0.5) is that from the construction of our estimator, we can find smaller ε will lead to a huge number of samples with high probability, to avoid this problem, we only test ε close to 0.5. To reduce the effect of variance, for every ε, we will run 5 times and use the averaged value as the final output Q rob δ,ε . Finally, we use Q rob δ,ε to find the greedy policy
for every ε. The output greedy policy π rob δ,ε for every ε is listed in Table 1. We can see all policies are the same as
In Table 2, we list the averaged number of iterations and averaged number of samples used for every ε. Combing our results in Tables 1 and2, it shows that Algorithm 1 may converge with even less samples when ε / ∈ (0, 0.5) . Now we define a perturbed uniform distribution with parameter m and b as follows:
With the perturbed distribution, we test our distributionally robuast policy π rob δ and non distributionally robuast policy π * for b ∈ {1, 1.5, 2, 2.5} (Note that b can not be too large, otherwise there will exist some pair (s, a) such that D KL (p s,a ∥p 0 s,a ) > δ or D KL (ν s,a ∥ν 0 s,a ) > δ) and every m ∈ [n -1]. We report the total cost averaged over 2000 runs for different b in Figures 1 to 4.
With varying test probabilities, our distributionally robust policy performs better in worst cases when the probability distribution of demand is centered in {5, 6, 7} instead of the uniform distribution, demonstrating again the effectiveness of our proposed distributionally robust formulations.
In this paper, we proposed a novel unbiased estimator of the distributionally robust Bellman Operator. By using the Several open problems suggest itself. First, although asymptotic convergence is desirable, it would also be interesting to obtain finite-sample guarantees for distributionally robust Q-learning algorithm. We believe such a result would require a completely different line of analysis, whose scope goes significantly beyond this paper. Second, this paper focused on the infinite-horizon discounted RL setting. A much more challenging but also highly useful setting to consider is the (infinite horizon) average reward RL (Dong et al., 2021). RL in this setting is less explored, and distributionally robust policy learning in this setting poses significant technical challenges. Finally, another important direction of research is to generalize the results to high-dimensional state settings (Ren & Zhou, 2020), where the intrinsic dimension is low. Data efficiency in such settings will be of particular importance. We look forward to these problems being addressed by the emerging distributionally robust reinforcement learning community.
First of all, we introduce two ancillary concentration inequalities. Lemma A.1 ( (Fournier & Guillin, 2015), Concentration inequality for Wasserstein distance ). For µ ∈ P(R), we consider an i.i.d. sequence (X k ) k≥1 of µ-distributed random variables and, for all n ≥ 1, the empirical measure
Assume that there exists γ > 0 such that E 2,γ (µ) := R exp(γ|x| 2 )µ(dx) < ∞. Then for all n ≥ 1, all x > 0,
where the Wasserstein distance W(µ n , µ) is defined by
|x -y|π(dx, dy) , and the positive constant C and c depends only on γ and E 2,γ (µ). Lemma A.2 (Hoeffding's inequality).
Then for every t > 0,
B. Missing Proof of Theorem 3.7
Proof. Fix a pair (s, a) ∈ S × A, we first prove R rob δ (s, a) defined in Equation ( 9) is an unbiased estimator of sup α≥0 -α log E ν 0 s,a e -r(s,a)/α -αδ which forms the first part of our δ-distributionally robust Bellman Operator (see Equation ( 6)). Let g(α) = -α log E ν 0 s,a e -r(s,a)/α -αδ.
) is defined by using the subset of 2 N samples in which the index of every element is odd (resp. even). We use g 2 N to represent the function defined by replacing ν 0 s,a by ν 2 N in g and α * 2 N = argmax α≥0 g 2 N (α). Similarly, we also have
We only need to show
Based on our Assumption 2.1, we can give an upper bound of α * by observing
By a similar argument, α * 2 n ≤ R max /δ also holds. Besides, from above derivation, we can find
holds by a similar argument. Starting from here, we split the proof into two cases: α * = 0 and α * > 0.
• α * = 0. By proposition 2 in (Hu & Hong, 2013), α * = 0 implies λ := ν 0 s,a (r(s, a) = ess inf r(s, a)) > 0. We first introduce the following two events:
Note that we have the following result for G 2 n :
By Lemma 4 in (Zhou et al., 2021), ∀ϵ > 0, there exists a constant N (ϵ, δ), such that ∀n ≥ N (ϵ, δ),
where the first inequality is by Equation ( 14) and Equation ( 15). Hence we know
Using above result, Equation ( 13) holds immediately in this case.
• α * > 0. We define the following event in this case,
By Lemma 4 in (Zhou et al., 2021), ∀ϵ > 0, there exists a constant N ′ (ϵ), such that once n ≥ N ′ (ϵ), we have
Observe that E ν 0 s,a e -r(s,a)/α ≥ e -Rmax/α and E ν 2 n e -r(s,a)/α ≥ e -Rmax/α hold, combining the Lipschitz property of log x when x is bounded below, we know
Then we have
For any α ∈ α * 2 , Rmax δ , the function e -x/α is a Lipschitz function on [0, ∞), and the Lipschitz constant is bounded by 2/α * . Hence, by the dual representation of Wasserstein distance, we have
where the Wasserstein distance W(ν 0 s,a , ν 2 n ) is defined by
|x -y|dπ(x, y) .
By Lemma A.1 (note that we assume r is bounded, so the condition for Lemma A.1 is satisfied automatically), there exists c, C > 0 such that
Note that we choose ϵ > 0 arbitrarily, so there is
Hence we know Equation ( 13) holds in this case.
Now we can conclude that R rob δ (s, a) is an unbiased estimator of sup α≥0 -α log E ν 0 s,a e -r(s,a)/α -αδ .
From here we give the proof that T rob δ (Q)(s, a) defined in Equation ( 10) is an unbiased estimator of sup β≥0 -β log E p 0 s,a e -max b∈A Q(s ′ ,b)/β -βδ which constructs the remaining part of our δ-distributionally robust Bellman Operator. Given Q ∈ R S×A and (s, a) ∈ S × A. We define V (s ′ ) = max b∈A Q(s ′ , b) for any s ′ ∈ S and
) is defined by using the subset of 2 N samples in which the index of every element is odd (resp. even). We use f 2 N to represent the function defined by replacing p 0 s,a by p 2 N in f and β * 2 N = argmax β≥0 f 2 N (β). Similarly, we also have
. Following the similar proof for g used in the previous part, we will have
Hence we only need to show
We can observe that both β * and β * 2 n are no bigger than 2∥Q∥ ∞ /δ. For β * , this is because
If we apply the similar argument to β * 2 n , we can get the same result. Besides, from the above derivation, we can see
also holds with a similar reason. Now we define the following two key events,
Note the facts P [E n 2 ] = 1 and
where the last inequality is right because of Lemma A.2. With the above proposition, we can start to show that Equation ( 17) is true, we consider the following decomposition
, where the last inequality holds due to Equation (18) and Equation ( 19). Now denote min s ′ ∈S,p 0 s,a (s ′ )>0 V (s ′ ) as v. Note that we have shown 0 ≤ β * , β * 2 n ≤ 2∥Q∥ ∞ /δ. Observe that under T 2 n and E 2 n , ∀β ∈ [0, 2∥Q∥ ∞ /δ], there are
and
Then under T 2 n and E 2 n , we know
The third inequality is right is by the Lipschitz property for log x when x is bounded from below. Finally we have
where the second inequality is by Lemma A.2. Hence we have
This is enough to conclude
Note that Equation (21) implies that Equation ( 17) is true. Now we complete our partial proof, i.e., T rob δ (Q)(s, a) is an unbiased estimator of sup β≥0 -β log E p 0 s,a e -max b∈A Q(s ′ ,b)/β -βδ .
Finally we complete the proof that
Proof. Following the same notations defined in the proof of Theorem 3.7 (cf. Appendix B), we have already known for any ε ∈ (0, 0.5), Q ∈ R S×A and (s, a) ∈ S × A,
By the definition of variance we have
We first analysis the term Var[ R rob δ (s, a)] by noticing
Like the proof of Theorem 3.7, we also consider following two cases
• α * = 0. By Proposition 2 in (Hu & Hong, 2013), α * = 0 if and only if λ := ν 0 s,a (r(s, a) = ess inf r(s, a)) > 0 and λ ≥ e -δ . Since δ is chosen by us, we can ignore the edge case λ = e -δ by introducing randomness on δ. Now we define the following three events: (Hu & Hong, 2013) implies that we have α * , a). The same argument can be applied to the subscript 2 n E and 2 n . Besides, note that
Note the following two bounds
The first bound is due to Lemma A.2 again. Finally we have
Then if we choose p n = ε(1 -ε) n , we know
Note that λ depends on (s, a). However, the number of pair (s, a) is finite, hence we can find a uniform constant bound K 1 (δ, ε, ν 0 ) ≥ K ′ 1 (λ, δ, ε, ν 0 ) for any (s, a) ∈ S × A which makes α * = 0.
• α * > 0. In this case, we follow the way proposed by (Zhou et al., 2021). Define
where α = α * /2 and α = R max /δ. Besides, we introduce the following event
Note that by Lemma 4 in (Zhou et al., 2021), under where the last inequality holds by a similar argument for Equation ( 16). Using a similar calculation used in the proof of Theorem 3.7, we can find
Besides, by Lemma 4 in (Zhou et al., 2021), we know P[F c 2 n ] = O(e -2 n ), Besides, note p n = ε(1-ε) n for ε ∈ (0, 0.5). Since we are in the tabular setting ,we can find a constant K 2 (δ, ε, ν 0 ) > K ′ 2 (α * , δ, ε, ν 0 ) for any (s, a) which makes α * > 0.
By the previous two cases, we know E[( R rob δ (s, a) -g(α * )) 2 ] ≤ max(K 1 (δ, ε, ν 0 ), K 2 (δ, ε, ν 0 )). Now we start to analysis Var[ T rob δ (Q)(s, a)] = E[( T rob δ (Q)(s, a) -f (β * )) 2 ]. By the similar approach, we can find
Use the same notations we defined in proof of Theorem 3.7, we can find 2 n ] = 0 from the proof of Theorem 3.7. Note that p n = ε(1 -ε) n for ε ∈ (0, 0.5), we have
Now we can find a uniform bound K 3 (δ, ε, P 0 ) > 0 such that
Var[ T rob δ,ε (Q)(s, a)] ≤ 2 max(K 1 (δ, ε, ν 0 ), K 2 (δ, ε, ν 0 )) + 2γ 2 K 3 (δ, ε, P 0 )(1 + ∥Q∥ 2 ∞ ) ≤ C(δ, ε, ν 0 , P 0 )(1 + ∥Q∥ 2 ∞ ), where C(δ, ε, ν 0 , P 0 ) > 0 is some uniform constant. Hence we complete the proof.
For instance, they have characterized various types of uncertainty sets, and have shown that for almost all of them, the optimal distributionally robust policy is NP-hard to compute. For rectangular uncertainty sets (to which our formulation belongs), such