---
abstract: 'Optimal control of a stochastic dynamical system usually requires a good dynamical model with probability distributions, which is difficult to obtain due to limited measurements and/or complicated dynamics. To solve it, this work proposes a data-driven distributionally robust control framework with the Wasserstein metric via a constrained two-player zero-sum Markov game, where the adversarial player selects the probability distribution from a Wasserstein ball centered at an empirical distribution. Then, the game is approached by its penalized version, an optimal stabilizing solution of which is derived explicitly in a linear structure under the Riccati-type iterations. Moreover, we design a model-free Q-learning algorithm with global convergence to learn the optimal controller. Finally, we verify the effectiveness of the proposed learning algorithm and demonstrate its robustness to the probability distribution errors via numerical examples.'
address: 'Department of Automation and BNRist, Tsinghua University, Beijing, 100084, China.'
author:
- Feiran Zhao
- Keyou You
bibliography:
- 'mybibfile.bib'
title: 'Data-driven Distributionally Robust Optimal Stochastic Control Using the Wasserstein Metric'
---

,

Stochastic control; Distributionally robust control; Wasserstein metric; Zero-sum Markov game; Reinforcement learning.

Introduction
============

Stochastic control is a well-studied framework for the dynamical systems with inherent stochastic uncertainties [@aastrom2012introduction]. The probability distributions of uncertain variables in the system are usually assumed to be fully known, which in practice is difficult to obtain as it possibly involves numerous expensive experiments. Using the approximated distribution is not always reliable, especially for those safety-critical systems, where a poor approximation may lead to catastrophic system behaviors [@nilim2005robust]. Besides, an exact dynamical model can be also difficult to obtain due to e.g., limited measurements and/or complicated dynamical couplings. In either case, a model-based controller might not always work well. Thus, it is necessary to design a model-free controller that is robust against the distribution errors.

To tackle the distribution uncertainties in the system, an approach is to use the distributionally robust (DR) control [@delage2010distributionally]. Recent years have witnessed significant research efforts on the DR optimization [@wiesemann2014distributionally; @gao2016distributionally; @esfahani2018data] which has also been applied to machine learning [@chen2018robust], Markov decision process (MDP) [@xu2010distributionally; @yang2017convex; @yu2015distributionally] and control [@van2015distributionally; @zymler2013distributionally; @yang2018wasserstein]. It assumes that the groundtruth distribution is contained in a given set of probability distributions, also known as the ambiguity set, and then optimize a reasonable performance index over this set. The design of the ambiguity set is critical and usually requires to merge the available prior statistical knowledge with data to reduce the conservativeness of the DR controller [@gao2016distributionally; @yang2018wasserstein; @schuurmans2019safe]. However, most of the existing methods are model-based [@delage2010distributionally; @ben2013robust; @yang2018wasserstein; @schuurmans2019safe], i.e., they require an exact dynamical model of the system.

Reinforcement learning (RL)[@sutton1998introduction], as a sample-based method, has achieved tremendous progresses recently in various control problems [@mnih2013playing; @mnih2015human-level; @levine2013guided; @lillicrap2015continuous; @schulman2017proximal]. It is model-free in the sense that the controller is not built directly on the dynamical model. Under the dynamic programming framework, the RL aims to approximately solve MDP problems by solely using training samples of the decision process. Since collecting training samples in the physical world could be possibly expensive and time-intensive, the RL algorithms are usually trained over a simulator. As expected, the resulting policies may fail to generalize to practical scenarios due to the model discrepancy between the simulated environment and the physical system. Robust RL algorithms aim to enhance the robustness of the policy [@tessler2019action; @peng2018sim; @morimoto2005robust; @pinto2017robust]. Inspired by the concept in DR control, some robust RL algorithms with respect to distribution errors have been developed [@abdullah2019wasserstein; @smirnova2019distributionally]. In @abdullah2019wasserstein, the over-fitting to training environments is tackled by minimizing a long-term cost function under the worst-case distribution over a Wasserstein ambiguity set. In @smirnova2019distributionally, a safety learning method is proposed under a DR policy iteration scheme.

However, the aforementioned DR RL frameworks are designed for solving general sequential decision-making problems without using exploring system information e.g., linearity of the optimal policy for a linear stochastic system. Thus, they suffer from the lack of global convergence guarantees and require a large number of training samples. As a consequence, the resulting controller cannot guarantee to stabilize the system. Note that the stability is not explicitly concerned in the classical RL setting, though it is among the most important requirements in control theory. These issues have drawn increasing attention in the RL community [@fazel2018global; @yang2019global; @zhang2019policy; @zhang2020policy], yet to the best of our knowledge, there are little convergence guarantees in the DR RL setting.

In this paper, we focus on the stochastic control problem in the presence of distribution uncertainties, without an exact model of the system dynamics. In particular, we consider the sample-based control problem for linear stochastic systems. To this end, we formulate it as a DR optimal control problem with disturbance distribution errors measured by a Wasserstein ball which accounts for the uncertainties of the disturbance distribution. For tractability, we reformulate it as a two-player zero-sum game with Wasserstein penalties to design an optimal controller under the worst-case disturbance distribution. Then, we propose a DR Q-learning algorithm to learn a robust controller by using training data from a simulator.

Our main contributions are summarized below:

1.  **An explicit min-max solution with stability guarantees.** We derive an explicit solution to the zero-sum game with Wasserstein penalties under Riccati-type iterations. In particular, the optimal controller is affine with respect to the state feedback. Moreover, we show that under mild assumptions, the optimal controller is always able to stabilize the system.

2.  **Relations to <span>$H_{\infty}$</span> optimal control.** Through the insights from the Q-function of the zero-sum game, we show the equivalence between the DR problem and its deterministic counterpart, and reveal that the classical $H_{\infty}$ optimal control is a special case of our DR optimal control formulation.

3.  **Model-free algorithm with global convergence.** Leveraging the affine structure of the optimal controller, we propose a DR Q-learning algorithm to learn an optimal controller by solely using data from simulated system trajectories, and show its global convergence by building connections between Q-function iterations and value iterations. This is fundamentally different from the general DR RL in @abdullah2019wasserstein [@smirnova2019distributionally].

The remainder of the paper is organized as follows. In Section \[sec:background\], we describe the stochastic control problem with distribution uncertainties and formulate the DR optimal control problem. In Section \[sec:drc\], we derive its closed-form solution, and show the stability of the closed-loop system. In Section \[sec:q learning\], we derive the Q-function and discuss its relations to the classical $H_{\infty}$ optimal control. In Section \[sec:algorithm\], we propose a DR Q-learning algorithm and show its global convergence. In Section \[sec:experiment\], we demonstrate the convergence and effectiveness of the proposed algorithm via simulations.

Problem Formulation {#sec:background}
===================

In this section, we first describe the stochastic control problem for linear systems with distribution uncertainties. To derive a DR controller, we formulate it as a two-player zero-sum dynamic game with the Wasserstein metric.

Optimal Control for Linear Stochastic Systems
---------------------------------------------

We consider a time-invariant linear stochastic system with full state feedback $$\label{equ:sys}
x_{k+1} = Ax_k + Bu_k + Ew_k,$$ where the next state $x_{k+1}$ is a linear combination of the current state $x_k \in \mathbb{R}^n$, the control $u_k \in \mathbb{R}^{m}$ and the random disturbance $w_k \in \mathbb{R}^{d}$. The disturbance $w_k$ is a stationary process with probability distribution $\nu$. The state feedback policy $\pi$ is written in the form that $u_k = \pi(x_1,x_2,\dots,x_k)$. The goal of stochastic optimal control is to find an optimal control policy $\pi^*$ that minimizes the long-term cost $J_x(\pi)$ in the presence of the random disturbance $w_k$, i.e., $$\label{equ:cost}
J_x(\pi)=\mathbb{E}_{w_{k} \sim \nu}^{\pi}\left[\sum_{k=0}^{\infty} \alpha^{k} c(x_k,u_k) | x_{0}={x}\right],$$ where $\alpha \in (0,1)$ is a discount factor, and $c(x_k,u_k)$ is a user-chosen stage cost in a quadratic form $$c(x_k,u_k)=x_k^{\top}Qx_k + u_k^{\top}Ru_k.$$ The main difficulties for the stochastic control at least include: (a) the groundtruth distribution $\nu$ is generally unknown. A common approach is to simply set it as a Gaussian distribution, which is not suitable for the safety-critical systems as the distribution errors may result in significant degradation of the control performance. (b) The exact dynamical model $(A,B,E)$ can be difficult to obtain as we can only collect a finite number of noisy system input/output.

![The simulator serves as a black-box where the inputs consist of the control $u_k$ and disturbance $w_k$, and the output is a quaternion $\{x_k, u_k, w_k, x_{k+1}\}$.<span data-label="pic:simu"></span>](simu_tu){width="70mm"}

In practice, we may have access to a finite number of samples $\left\{\hat{w}^{(1)}, \ldots, \hat{w}^{(N)}\right\}$ of the disturbance from the environment. For instance, experiments can be conducted to collect the disturbance samples with a simple controller. Then, a straightforward way to approximate the groundtruth distribution $\nu$ is to use an empirical distribution $$\label{equ:emp}
\nu_{N}:=\frac{1}{N}\sum_{j=1}^{N}\delta_{\hat{w}^{(j)}},$$ where the Dirac delta measure $\delta_{\hat{w}^{(j)}}$ is concentrated at $\hat{w}^{(j)}$. As the number of samples tends to infinity, the empirical distribution $\nu_N$ weakly converges to the static groundtruth distribution $\nu$. However, it may be costly to collect such a large number of samples, which motivates us to design a controller with robustness to the distribution error in $\nu_N$.

Moreover, we assume to have access a simulator to generate system trajectories, i.e., $\{x_k, u_k, w_k, x_{k+1}\}_{k=0}^M$, as illustrated in Fig. \[pic:simu\]. The purpose of this work is to design a model-free reinforcement learning (RL) algorithm for the linear stochastic system (\[equ:sys\]) to learn a controller with robustness to distribution errors in $\nu_N$ by using a simulator.

The Wasserstein DR Control
--------------------------

To measure the distance between two probability distributions, we adopt the Wasserstein metric which is widely studied recently in the control and machine learning communities [@abadeh2018wasserstein; @esfahani2018data; @lee2015performance]. For two d-dimension distributions $\mu_i: \mathbb{R}^d \rightarrow [0, 1], \forall i\in\{1,2\}$, the Wasserstein metric of order $p \in [1,\infty)$ is defined as $$W_{p}(\mu_1, \mu_2) = \inf _{\kappa}\left(\int_{\mathbb{R}^d\times \mathbb{R}^d}      \left\|w_{1}-w_{2}\right\|^{p} \kappa \left(\mathrm{d} w_{1}, \mathrm{d} w_{2}\right)\right)^{\frac{1}{p}},$$ where $\kappa \in \Gamma (\mu_1, \mu_2)$ and $\Gamma (\mu_1, \mu_2)$ denotes the set of the joint distributions with marginal distributions $\mu_1$ and $\mu_2$. It can be thought as the minimal energy consumption to transport the mass from a distribution $\mu_1$ to the other $\mu_2$, and $\kappa$ is interpreted as the transport plan, see e.g. @abadeh2018wasserstein [@esfahani2018data] for details.

In this work, the groundtruth probability distribution $\nu$ is assumed to be within an *ambiguity set* $\mathbb{T}$ centred at the empirical distribution $\nu_N$. With the 2-order Wasserstein metric, the ambiguity set $\mathbb{T}$ is defined as $$\notag
    \mathbb{T} := \left\{\omega | W_{2}\left(\omega, \nu_N \right) \leq \rho  \right\}.$$ Clearly, the radius $\rho$ of the Wasserstein ball reflects our confidence level of $\nu_N$ and it reduces as the number of samples increases.

Then we aim to find a DR optimal controller $\pi$ by solving a min-max optimization problem $$\label{equ:constraint}
\begin{aligned}
&\inf_{\pi} \sup_{\mu_k} \mathbb{E}_{w_{k} \sim \mu_k}^{\pi}\left[\sum_{k=0}^{\infty} \alpha^{k} c(x_k,u_k) | x_{0}={x}\right]\\
&\text{subject~to} ~~~~W_{2}(\mu_k, \nu_N) \leq \rho, ~~\forall k \in \mathbb{N},
\end{aligned}$$ where $0<\alpha<1$ is the discount factor. It is well-known that the infinite number of hard constraints in (\[equ:constraint\]) are difficult to tackle. To alleviate it, we consider its penalized version [@yang2018wasserstein] of the form $$\label{equ:wasprob}
\inf_{\pi} \sup_{\mu_k} \mathbb{E}_{w_{k} \sim \mu_k}^{\pi}\left[\sum_{k=0}^{\infty} \alpha^{k} c(x_k, u_k, \mu_k) | x_{0}={x}\right],$$ where $c(x_k, u_k, \mu_k) = x_k^{\top}Qx_k + u_k^{\top}Ru_k - \lambda \cdot W_{2}^2\left(\mu_k, \nu_N \right).$ That is, we use a tunable hyperparameter $\lambda$ to penalize the deviation of a probability distribution $\mu_k$ from the empirical distribution $\nu_N$. For such a penalized problem, the optimal parameter $\lambda$ is expected to decrease as the radius $\rho$ of the ambiguity set increases. In this work, we avoid the use of the radius $\rho$ and manually tune the hyperparameter $\lambda$ to yield sub-optimal performance.

To solve the min-max optimization problem (\[equ:wasprob\]), we formulate it as a two-player zero-sum Markov game with full observations [@gonzalez2002minimax; @yang2018wasserstein; @bacsar2008h]. Player (controller) selects a control policy to minimize the cost in (\[equ:wasprob\]) while Player (adversary) seeks to thwart its goal by exerting disturbance probability distributions.

Before proceeding, we mention that our motivation to use Wasserstein metric is manifold. It is symmetric and can measure the difference of any pair of discrete and continuous probability distributions, whereas other distances e.g., the Kullback-Leibler divergence [@esfahani2018data; @van2014renyi], can not. This implies that their support sets are allowed to be different. More importantly, it genuinely reflects the modeling errors of the empirical distribution. It is reasonable that the shape of the two distributions could be different, and accordingly, the probability that large bias occur should naturally be small. The Wasserstein metric formalizes this intuition.

Landscape of This Work
----------------------

For ease of exposition, we summarize the main ideas that eventually yield a model-free DR optimal controller to solve (\[equ:wasprob\]) in Fig. \[pic:land\].

![Landscape of this work.<span data-label="pic:land"></span>](landscape){width="80mm"}

With the disturbance samples $\{\hat{w}^{(i)}\}_{i=1}^N$ and assuming that the system model $(A,B,E)$ is known, we first derive an explicit solution to the zero-sum game (\[equ:wasprob\]) via dynamic programming, whose optimal value function $V^*(x_k)$ has a quadratic form and the optimal control policy $u^*_k$ is affine with respect to the state. Then we develop a quadratic Q-function $\widetilde{Q}(x_k,u_k,\mu_k)$ with the triple $\{x_k,u_k,\mu_k\}$ as inputs. We further show the equivalence between the zero-sum game (\[equ:wasprob\]) and a deterministic version, in the sense of having the same optimal controller.

The remaining step is to design a model-free Q-learning algorithm for the equivalent deterministic game to learn a simpler Q-function $Q_c(x_k,u_k,w_k)$, the parameterization of which can leverage the structure of $V^*(x_k)$ and disturbance samples $\{\hat{w}^{(i)}\}_{i=1}^N$. This learning process is achieved by using the simulator in Fig. \[pic:simu\]. The DR model-free controller is obtained once the Q-function is learned. Kindly note that the global convergence to the DR optimal controller of (\[equ:wasprob\]) is also shown in this work.

Distributionally Robust Control for Linear Stochastic Systems {#sec:drc}
=============================================================

In this section, we derive an explicit solution to the penalized problem (\[equ:wasprob\]) via dynamic programming if the system model $(A,B,E)$ are known. The optimal value function has a quadratic form and the policy is affine in the state. We further show that the resulting closed-loop system is always stable under mild assumptions.

An Explicit Solution to the Zero-sum Game
-----------------------------------------

We solve the zero-sum game (\[equ:wasprob\]) by a backward dynamic programming paradigm. Particularly, the optimal value function at state $x_k$ is given recursively through the well-known Bellman equation as $$\label{equ:optvalue}
V^*(x_k) = \min_{u_k} \max_{\mu_k}  \mathbb{E} \bigl[ c_k(x_k, u_k, \mu_k)  + \alpha V^*(x_{k+1})  \bigr].$$ The Wasserstein metric $W_{2}(\mu_k, \nu_N )$ in $c_k(x_k, u_k, \mu_k)$ is seemingly difficult to tackle. By leveraging recent techniques in the DR optimization problem [@gao2016distributionally; @yang2018wasserstein], we convert it to a tractable formulation.

\[Proposition 6,@yang2018wasserstein\] \[lem:bellman\] The Bellman equation (\[equ:optvalue\]) can be equivalently expressed as $$V^*(x_k) = \min_{u_k}\left\{ x_k^{\top}Qx_k + u_k^{\top}Ru_k \\
    +  \frac{1}{N} \sum_{j=1}^{N} \max_{w_k^j \in \mathbb{R}^d} \Phi(u_k, w_k^j) \right\},$$ where $\Phi(u_k, w_k^j) = \alpha V^*(x_{k+1}) - \lambda  \|w_k^j-\hat{w}^{(j)}\|^{2}$.

Lemma  \[lem:bellman\] implies that the effect of an arbitrary distribution $\mu_k$ on the optimal value function can be fully captured by a uniform discrete distribution which can be parameterized by $N$ vectors $w_k^j, j \in \{1,2,\dots,N\}$. This enables us to derive an explicit solution to the zero-sum game (\[equ:wasprob\]) under the following standard assumptions.

\[assumption\] $Q$ is positive semi-definite and $R$ is positive definite. The pair $(A,B)$ is stabilizable and $(A,Q^{{1}/{2}})$ is observable.

We define the following statistics over the set of samples $\{\hat{w}^{(i)}\}_{i=1}^N$ as follows.

\[def\] The sample mean and covariance of $\{\hat{w}^{(i)}\}_{i=1}^N$ are defined as $$\notag
    \begin{aligned}
    \text{Sample mean:}~~~~\bar{w} &:= \frac{1}{N} \sum_{j=1}^{N} \hat{w}^{(j)}, \\
    \text{Sample covariance:}~~~~\Sigma &:= \frac{1}{N} \sum_{j=1}^{N} (\hat{w}^{(j)} - \bar{w}) (\hat{w}^{(j)} - \bar{w})^{\top}.
    \end{aligned}$$

We show that the optimal value function $V^*(x_k)$ in (\[equ:optvalue\]) is quadratic with respect to the state $x_k$, and the optimal controller has an affine state feedback form with a constant offset.

For the ease of notation, let $ H_{xx}^i = Q+\alpha A^{\top}P_iA,  H_{xu}^i = \alpha A^{\top}P_iB, H_{xw}^i = \alpha A^{\top}P_iE, H_{uu}^i= R+\alpha B^{\top}P_iB, H_{uw}^i= \alpha B^{\top}P_iE, H_{ww}^i = \alpha E^{\top}P_iE-\lambda I$ and $G_x^i = \alpha A^{\top}g_i, G_u^i = \alpha B^{\top}g_i, G_{w}^i = \alpha E^{\top}g_i+2\lambda \bar{w}$, $G_{w^j}^i = \alpha E^{\top}g_i+2\lambda \hat{w}^{(j)}$, then we have the following results.

\[theorem:solution\] Suppose that for $P_0 = 0$, the Riccati-type iteration $$\label{def:P}
    \hspace{-0.085cm} P_{i+1}= H_{xx}^i-
    \begin{bmatrix}
    H_{xu}^i&H_{xw}^i
    \end{bmatrix}
    \begin{bmatrix}
    H_{uu}^i & H_{uw}^i \\
    * & H_{ww}^i
    \end{bmatrix}^{-1}  
    \begin{bmatrix}
    H_{xu}^{i^{\top}} \\
    H_{xw}^{i^{\top}}
    \end{bmatrix}$$ converges to a positive semi-definite matrix $P$ and $\lambda I -\alpha E^{\top} P E > 0 $. Then, we have the following results.

1.  The optimal value function $V^*(x)$ in (\[equ:optvalue\]) has a quadratic form, i.e., $$V^{*}(x) =x^{\top} P x+ g^{\top}x +  z,$$ where $g = \lim\limits_{i \rightarrow \infty} g_i$, $z=\lim\limits_{i \rightarrow \infty} z_i$ and $$\label{def:g}
            \begin{aligned}
            &g_{i+1}= G_x^i-
            \begin{bmatrix}
            H_{xu}^i&H_{xw}^i
            \end{bmatrix}
            \begin{bmatrix}
            H_{uu}^i & H_{uw}^i \\
            * & H_{ww}^i
            \end{bmatrix}^{-1}
            \begin{bmatrix}
            G_u^i \\
            G_w^i
            \end{bmatrix},\\
            &z_{i+1} =  \alpha z_i - \lambda \|\bar{w}\|^2 - \text{tr}\{H_{ww}^{i^{-1}} (\lambda^2\Sigma + \frac{1}{4}G_w^iG_w^{i^{\top}}) \}\\
            &-\frac{1}{4} (G_u^{i^{\top}}-G_w^{i^{\top}}H_{ww}^{i^{-1}} H_{uw}^{i^{\top}})(H_{u u}^i-H_{u w}^iH_{w w}^{i^{-1}} H_{uw}^{i^{\top}})^{-1}\\
            & \times ( G_u^{i}- H_{uw}^{i} H_{ww}^{i^{-1}}  G_w^{i}).
            \end{aligned}$$

2.  The optimal control policy to solve (\[equ:wasprob\]) has an affine state feedback form, i.e., $$\label{equ:opt_u}
            u^* = Kx + r$$ where $$\begin{aligned}
            &K = (H_{u u}-H_{u w} H_{w w}^{-1} H_{uw}^{\top})^{-1}(H_{u w} {H_{w w}^{-1}} H_{xw}^{\top}-H_{u x}^{\top}), \\
            &r = -\frac{1}{2}(H_{u u}-H_{u w} H_{w w}^{-1} H_{uw}^{\top})^{-1}(G_u - H_{uw} H_{w w}^{-1} G_w ).
            \end{aligned}
            \notag$$

3.  One of the worst-case disturbance distributions $\mu^*$ to solve (\[equ:wasprob\]) is stationary and discrete, whose support set has exactly N points ${w^j}^*, j\in \{1,2,\cdots, N\}$. Specifically, let ${w^j}^* = Lx + l_j$, where $$\notag
            \begin{aligned}
            &L = (H_{w w}-H_{uw}^{\top} H_{uu}^{-1} H_{u w})^{-1}(H_{uw}^{\top} H_{uu}^{-1} H_{xu}^{\top}-H_{xw}^{\top}),\\
            &l_j = -\frac{1}{2N}(H_{w w}-H_{uw}^{\top} H_{uu}^{-1} H_{u w})^{-1}(G_{w^j}-  H_{uw}^{\top} H_{uu}^{-1} G_u ),
            \end{aligned}$$ then $\mu^*=\frac{1}{N} \sum_{j=1}^{N} \delta_{{w^j}^*}$.

\[proof:solution\] We apply the backward dynamic programming for the finite horizon case, and the proof is completed by letting the horizon goes to infinity.

The finite-horizon zero-sum game aims to solve the following problem $$\label{equ:fini_prob}
    \inf_{\pi} \sup_{\mu_k} \mathbb{E}_{w_{k} \sim \mu_k}^{\pi}\left[\sum_{k=0}^{h-1} \alpha^{k} c(x_k, u_k, \mu_k) | x_{0}={x}\right],$$ where $h$ denotes the time horizon. Let $V_k^h(x)$ be the corresponding optimal value function at time step $k$.

We use mathematical induction to show that $V_k^h(x)$ has the following quadratic form, $$\label{equ:finite}
    V_{k}^{h}(x)  =x^{\top} P_k x+ g_{k}^{\top}x +  z_{k},$$ where $P_{k}$ is a symmetric positive semi-definite matrix to be determined, $g_{k}$ is a column vector and $z_{k}$ is a scalar.

Clearly, (\[equ:finite\]) holds for $k = h$ with $P_h = 0$, $g_h = 0$ and $z_h = 0$. Suppose it also holds for $k+1 \in \{1,2,\dots,h\}$, it follows from Lemma \[lem:bellman\] that at time step $k$, we obtain $$\label{equ:finite_bellman}
    V_k^h(x_k) = \min_{u_k} \bigl\{ x_k^{\top}Qx_k + u_k^{\top}Ru_k 
    +  \frac{1}{N} \sum_{j=1}^{N} \max_{w_k^j} \Phi(u_k, w_k^j) \bigr\},$$ where $$\notag
    \begin{aligned}
    &\Phi(u_k, w_k^j) = \\
    &\alpha(Ax_k+Bu_k+Ew_k^j)^{\top}P_{k+1}(Ax_k+Bu_k+Ew_k^j)\\
    &+ \alpha g_{k+1}^{\top}(Ax_k+Bu_k+Ew_k^j) + \alpha z_{k+1} -\lambda  \|w_k^j-\hat{w}^{(j)}\|^{2}
    \end{aligned}$$ is quadratic in $w_k^j$ and is concave if $\lambda I -\alpha E^{\top} P_{k+1} E > 0 $. Then, $\Phi(u_k, w_k^j)$ attains its maximum value at a unique point $$\label{equ:w}
    \begin{aligned}
    w_k^{j*} =& \left(\lambda I-\alpha E^{\top} P_{k+1} E\right)^{-1}\big(\alpha E^{\top} P(A x_k+B u_k)\\
    &+\lambda \hat{w}^{(j)} + \frac{1}{2}\alpha E^{\top}g_{k+1}  \big),
    \end{aligned}$$ and $$\label{equ:phi}
    \begin{aligned}
    &\Phi(u_k, w_k^{j*}) = \alpha(Ax_k+Bu_k)^{\top}P_{k+1}(Ax_k+Bu_k)\\
    &+\alpha g_{k+1}^{\top}(Ax_k+Bu_k)+\alpha z_{k+1} - \lambda \|\bar{w}\|^2\\
    & - \big(\alpha E^{\top}P_{k+1}(Ax_k+Bu_k)+\frac{1}{2}\alpha E^{\top}g_{k+1}+ \lambda \hat{w}^{(j)}
    \big)^{\top} \\
    &\times (\alpha E^{\top}P_{k+1}E-\lambda I)^{-1}\\
    &\times\big(\alpha E^{\top}P_{k+1}(Ax_k+Bu_k)+\frac{1}{2}\alpha E^{\top}g_{k+1}+ \lambda \hat{w}^{(j)}
    \big).
    \end{aligned}$$

Inserting $\Phi(u_k, w_k^{j*})$ in (\[equ:phi\]) into (\[equ:finite\_bellman\]), we have that $$\label{equ:v}
    \begin{aligned}
    &V_k^h(x_k) =  \min_{u_k} \big\{
    u_k^{\top}(H_{uu}^k- H_{uw}^kH_{w w}^{k^{-1}} H_{uw}^{k^{\top}})u_k + u_k^{\top} \\
    &\times (G_u^k - H_{uw}^k H_{w w}^{k^{-1}} G_w^k - 2(H_{u w}^k {H_{w w}^{k^{-1}}} H_{xw}^{k^{\top}}-H_{u x}^{k^{\top}})x_k)\big\}\\
    &+  \alpha z_k - \lambda \|\bar{w}\|^2 - \text{tr}\{H_{w w}^{k^{-1}} (\lambda^2\Sigma + \frac{1}{4}G_w^kG_w^{k^{\top}}) \}\\
    &+ x_k^{\top}(H_{xx}^k - H_{xw}^k H_{w w}^{k^{-1}} H_{xw}^{k^{\top}})x_k \\
    &+ (G_x^k - H_{xw} H_{w w}^{k^{-1}} G_w^k)^{\top}x_k 
    \end{aligned}$$

Solving the above quadratic optimization problem yields that $u_k^* = K_kx_k + r_k$, where $$\begin{aligned}
    &K_k=(H_{u u}^k-H_{u w}^k H_{ww}^{k^{-1}} H_{uw}^{k^{\top}})^{-1}
    (H_{u w}^k H_{ww}^{k^{-1}} H_{xw}^{k^{\top}}-H_{u x}^{k^{\top}}),\\
    &r_k = -\frac{1}{2}(H_{u u}^k-H_{u w}^k H_{ww}^{k^{-1}} H_{uw}^{k^{\top}})^{-1}(G_u^k - H_{uw}^k H_{ww}^{k^{-1}} G_w^k).
    \end{aligned}
    \notag$$ Replacing $u_k$ with $u_k^*$ in (\[equ:w\]) and (\[equ:v\]), we finish the induction. Note that the assumption $\lambda I -\alpha E^{\top} P_{k+1} E > 0 $ in the derivation is automatically satisfied since $\lambda I -\alpha E^{\top} P E > 0 $ and $P \geq P_k$ [@bacsar2008h].

Since the Riccati-type iterations (\[def:P\]) converge, (\[equ:fini\_prob\]) converges as $h$ goes to infinity. Note that the convergence of $g_i$ and $z_i$ in (\[def:g\]) is trivial.

A similar result has been developed in @yang2018wasserstein [Theorem 4] for the case $ \bar{w} = 0$. If the sample mean $\bar{w}$ is not zero, the zero-sum game (\[equ:wasprob\]) is solved by augmenting the system state as $\widetilde{x} = \begin{bmatrix}
    (x - \bar{x})^{\top} & 1
    \end{bmatrix}$ with $\bar{x}= (I-A)^{-1}E\bar{w}$. Clearly, this method implicitly requires the existence of $(I-A)^{-1}$, excluding an important class of open-loop unstable systems. Moreover, the augmented system is not controllable due to the constant in the last element of the augmented state $\widetilde{x}$, and cannot be applied to the RL setting as $(I-A)^{-1}E\bar{w}$ is not computable without the model information $(A,E)$.

Stability of the Closed-loop System
-----------------------------------

By the linear quadratic (LQ) dynamic game theory [@bacsar2008h], we first show that the conditions in Theorem \[theorem:solution\] hold, which implies that the Riccati-type iteration (\[def:P\]) converges. Then for an appropriate $\alpha$, the affine optimal controller (\[equ:opt\_u\]) is able to stabilize the system.

\[coro\] Let Assumption \[assumption\] hold, then the Riccati-type iteration (\[def:P\]) converges to a symmetric positive semi-definite matrix $P$. Moreover, if the discount factor $\alpha$ is sufficiently close to $1$, then $\rho(A+BK+EL)<1$ and $\rho(A+BK)<1$ where $(K,L)$ is given in (\[equ:opt\_u\]).

Let $
A_{\alpha} := \sqrt{\alpha} A, ~~B_{\alpha} := \sqrt{\alpha} B, \text { and } E_{\alpha} := \sqrt{\alpha} E,
$ the convergence of (\[def:P\]) follows from the standard LQ game theory [@bacsar2008h].

Since the feedback gains $K$ and $L$ in Theorem \[theorem:solution\] are functions of $\alpha$, we rewrite them as $K(\alpha)$ and $L(\alpha)$, respectively. We consider the spectral radius $\rho(A+BK(\alpha)+EL(\alpha))$ which is a continuous function with respect to $\alpha$. It follows from @bacsar2008h that $A+ BK(1) + EL(1)$ is stabilizing, namely $\rho(A+BK(1)+EL(1))<1$. Thus, we have $\rho(A+BK(\alpha)+EL(\alpha))<1$ as long as $\alpha$ is sufficiently close to 1. Similarly, we can show that $\rho(A+BK(\alpha))<1$.

The computation of the feedback gain pair $(K,l)$ in (\[equ:opt\_u\]) requires the information of the system model $(A,B,E)$. Next, we further design a RL algorithm to learn an optimal control policy via training data in a trial-and-error way. Since it can be both time-consuming and expensive to collect data from the physical world, one can use a computer simulator to generate data at a relatively low cost, see Fig. \[pic:simu\]. In the sequel, we shall only use such a simulator to find the optimal controller in Theorem \[theorem:solution\].

Distributionally Robust Q-learning {#sec:q learning}
==================================

\[sec:q\_setup\]

In this section, we first find an equivalent DR Q-learning setup and derive the Q-function of the zero-sum game in (\[equ:wasprob\]). By exploiting the structure of the Q-function, we then convert the stochastic zero-sum game (\[equ:wasprob\]) to a deterministic version. Moreover, we discuss its relation to the classical $H_{\infty}$ optimal control.

Distributionally Robust Q-learning {#distributionally-robust-q-learning}
----------------------------------

In order to solve the zero-sum Markov game (\[equ:wasprob\]) via a model-free approach, we adopt the approximate dynamic programming framework [@bertsekas1995dynamic; @powell2007approximate; @bertsekas2019reinforcement]. Particularly, the Q-function $Q(x_k,u_k,\mu_k)$ in (\[equ:wasprob\]) is given as $$\notag
\begin{aligned}
Q(x_k,u_k,\mu_k) = & x_k^{\top}Qx_k + u_k^{\top}Ru_k - \lambda W_{2}^2(\mu_k, \nu_N ) \\
&+ \alpha \mathbb{E}_{w_{k} \sim \mu_k}
V^*(x_{k+1}),
\end{aligned}$$ where $u_k$ and $\mu_k$ are actions taken by the controller and adversary, respectively. Once the Q-function is determined, the optimal $u_k^*$ can be obtained by simply setting the derivative to zero.

The difficulty in determining a closed-form of the Q-function lies in the Wasserstein distance $W_{2}(\mu_k, \nu_N)$. By Theorem \[theorem:solution\], the worst-case distribution $\mu^*$ is discrete with the same number of supports as the empirical distribution $\nu_N$. Thus, there is no loss of generality to restrict $\mu_k$ to a set of discrete distributions $\mathbb{D}_N$ and parameterize it with $N$ vectors $\{w_k^j\}_{j=1}^N$. The following lemma formally confirms this observation.

\[lemma:equvalence\] Define an alternative Q-function $$\label{equ:appro_q}
    \begin{aligned}
    \widetilde{Q}(x_k,u_k,\mu_k)
    = & x_k^{\top}Qx_k + u_k^{\top}Ru_k -  \frac{\lambda}{N} \sum_{i=1}^{N} \|{w_k^j}-\hat{w}^{(j)}\|^{2}\\
    & + \alpha \mathbb{E}_{w_{k} \sim \mu_k} V^*(x_{k+1}).
    \end{aligned}$$ It follows that $$\min_{u_k} \max_{\mu_k} Q(x_k,u_k,\mu_k) = \min_{u_k} \max_{\mu_k \in \mathbb{D}_N} \widetilde{Q} (x_k,u_k,\mu_k)$$ and optimal values of both sides are achieved at the same pair $(u_k^*, \mu_k^*)$.

By Lemma \[lem:bellman\], it follows that $$\notag
    \begin{aligned}
        &\hspace{-0.8cm}\min_{u_k} \max_{\mu_k} Q(x_k,u_k,\mu_k)=\min_{u_k} \bigl\{ x_k^{\top}Qx_k + u_k^{\top}Ru_k \\
        &~~~+  \frac{1}{N} \sum_{j=1}^{N} \max_{w \in \mathbb{R}^d} \bigl\{ \alpha V^*(x_{k+1}) - \lambda  \|w-\hat{w}^{(j)}\|^{2} \bigr\}  \bigr\} \\
        & = \min_{u_k} \max_{\mu_k \in \mathbb{D}_N} \widetilde{Q}(x_k,u_k,\mu_k). 
        ~~~~~~~~~~~~~~~~~~~~~~~~~\qed
    \end{aligned}$$

Thus, we only need to focus on $\widetilde{Q}(x_k,u_k,\mu_k)$ over $ \mathbb{D}_N$. Since $V^*(x_{k+1})$ is quadratic, $\widetilde{Q}(x_k,u_k,\mu_k)$ also has a quadratic form.

\[prop:q\] The Q-function in is explicitly given as $$\notag
     \widetilde{Q}(x_k,u_k,\mu_k) =
    \begin{bmatrix}
        x_{k} \\
    u_{k} \\
    w_k^1 \\
    \vdots \\
    w_k^N
    \end{bmatrix}^{\top}
    \widetilde H
    \begin{bmatrix}
    x_{k} \\
    u_{k} \\
    w_k^1 \\
    \vdots \\
    w_k^N
    \end{bmatrix} +
    \widetilde G^\top
        \begin{bmatrix}
    x_{k} \\
    u_{k} \\
    w_k^1 \\
    \vdots \\
    w_k^N
    \end{bmatrix} + \widetilde s,$$ where $\widetilde G^{\top} =
    \bigl[ G_x^{\top}~  G_u^{\top} ~ G_{w^1}^{\top}~\cdots~  G_{w^N}^{\top} \bigr], 
     \widetilde s = \alpha z - \frac{\lambda}{N} \sum_{i=1}^{N} \|\hat{w}^{(j)}\|^2$ and $$\notag
    \widetilde H =  \begin{bmatrix}
     H_{xx} & H_{xu} & H_{xw} &\cdots &  H_{xw} \\
     & H_{uu} & H_{uw} &\cdots &  H_{uw} \\
     &  & H_{ww} &\cdots &   0  \\
     & * &  & \ddots & 0 \\
     &  & & &  H_{ww}  \\
    \end{bmatrix},$$

We note that $$\notag
        \begin{aligned}
    & \widetilde{Q}(x_k,u_k,\mu_k) \\
    &= x_k^{\top}Qx_k + u_k^{\top}Ru_k -  \frac{\lambda}{N} \sum_{i=1}^{N} \|{w_k^j}-\hat{w}^{(j)}\|^{2}
    + \alpha \mathbb{E}_{w_{k}} V^*(x_{k+1})    \\
    & =  x_k^{\top}Qx_k + u_k^{\top}Ru_k -  \frac{\lambda}{N} \sum_{i=1}^{N} \|{w_k^j}-\hat{w}^{(j)}\|^{2} \\
    &+  \frac{\alpha}{N} \sum_{i=1}^{N} \bigl((Ax_k+Bu_k + Ew_k^j)^{\top} P (Ax_k+Bu_k + Ew_k^j) \\
    &+ g^{\top}(Ax_k+Bu_k + Ew_k^j) + z\bigr)\\
    & = x_k^{\top}Qx_k + u_k^{\top}Ru_k \\
    &-  \frac{\lambda}{N} \sum_{i=1}^{N} (\|w_k^j\|^2 - 2 \langle \hat{w}^{(j)},w_k^j \rangle + \| \hat{w}^{(j)} \|^2 ) + \alpha z \\
    &+  \frac{\alpha}{N} \sum_{i=1}^{N} \bigl((Ax_k+Bu_k)^{\top}P(Ax_k+Bu_k) + \langle w_k^j, E^{\top}PEw_k^j \rangle \\
     &+ 2\langle w_k^j,E^{\top}P(Ax_k+Bu_k) \rangle+ g^{\top}(Ax_k+Bu_k + Ew_k^j)  \bigr). \\
    \end{aligned}$$ By reorganizing the above terms with tedious algebraic manipulations, the proof is completed.

Since $$\notag
\begin{aligned}
&\frac{\partial \widetilde{Q}}{\partial u_k} =  \frac{2}{N} \sum_{i=1}^{N}
\left(H_{xu}^{\top}x_k + H_{uu}u_k + H_{uw} w_k^j  \right) + G_u ~\text{and}~ \\
&\frac{\partial \widetilde{Q}}{\partial w_k^j} =  \frac{2}{N}\left(H_{ww} w_k^j + H_{xw}^{\top} x_k + H_{uw}^{\top} u_k \right) + G_{w^j},
\end{aligned}$$ the solution to the zero-sum game (\[equ:wasprob\]) depends only on the parameter of $\widetilde{Q}(x_k,u_k,\mu_k)$. Notice that $\widetilde H$ is sparse with only 6 undetermined blocks. Similar observation can also be found in $\widetilde G$, implying a practical way to learn $\widetilde H$ and $\widetilde G$ by only using data.

Equivalence of the Zero-sum Game
--------------------------------

In the Q-learning framework, both $\widetilde H$ and $\widetilde G$ are learned on-line. However, this is a challenging task under our DR setting as the computation of $\widetilde{Q}(x_k,u_k,\mu_k)$ in (\[equ:appro\_q\]) involves an expectation operator $\mathbb{E}_{w_{k} \sim \mu_k} V^*(x_{k+1})$, which is not convenient to evaluate on-line since only one sample $\{x_k, u_k, w_k, x_{k+1}\}$ is available at each time instant. To remedy it, we further show that the DR problem can be converted to a deterministic version.

By Proposition \[prop:q\], we only have the two parameter matrices to be learned, i.e., $$\begin{aligned}
H_c &=\begin{bmatrix}
H_{xx} & H_{xu} & H_{xw} \\
& H_{uu} & H_{uw} \\
*&  & H_{ww}
\end{bmatrix}
\\
&=\begin{bmatrix}
\alpha A^{\top} P A+ Q & \alpha A^{\top} P B & \alpha A^{\top} P E \\
& \alpha B^{\top} P B+ R & \alpha B^{\top} P E \\
*&  & \alpha E^{\top} P E-\lambda I
\end{bmatrix}\end{aligned}$$ and $ G_c^{\top} =
 \begin{bmatrix}
 G_x^{\top} &G_u^{\top} & G_w^{\top}
 \end{bmatrix}=\begin{bmatrix}
 \alpha g^{\top}A &\alpha g^{\top}B &\alpha g^{\top}E+2\lambda \bar{w}^{\top} 
 \end{bmatrix} $ and find that the pair of $(H_c,G_c)$ corresponds to the Q-function of another zero-sum game. Specifically, consider the following deterministic zero-sum game $$\label{equ:newgame}
\min_{\pi} \max_{w} \sum_{k=0}^{\infty} \alpha^{k} (x_k^{\top}Qx_k + u_k^{\top}Ru_k
- \lambda \|w_k - \bar{w}  \|^2 ),$$ where $w$ denotes the policy of the adversary in the form that $w_k = w(x_k)$.

\[theorem:certainty\] Under the same conditions in Theorem \[theorem:solution\], we have the following results.

1.  The optimal value function of the deterministic zero-sum game (\[equ:newgame\]) has a quadratic form $$\notag
            \begin{array}{lll}
            V_c^{*}(x) & =x^{\top} P x+ g^{\top}x +  z ,& \\
            \end{array}$$ where $P$, $g$ and $z$ are obtained through iterations in (\[def:P\]) and (\[def:g\]).

2.  The Q-function of the zero-sum game in (\[equ:newgame\]) is given by $$\label{def:Q_c}
            \begin{aligned}
            Q_c(x_k,u_k,w_k) =&
            \begin{bmatrix}
            x_{k} \\
            u_{k} \\
            w_k
            \end{bmatrix}^{\top}
            H_c
            \begin{bmatrix}
            x_{k} \\
            u_{k} \\
            w_k
            \end{bmatrix} +
            G_c^{\top}
            \begin{bmatrix}
            x_{k} \\
            u_{k} \\
            w_k
            \end{bmatrix}\\
            & + s_c,
            \end{aligned}$$ where $s_c$ is a scalar.

3.  The optimal controller of the game in (\[equ:newgame\]) is identical to that of the game in (\[equ:wasprob\]), i.e., $u^* = Kx + r,$ where $$\begin{aligned}
            &K = (H_{u u}-H_{u w} H_{w w}^{-1} H_{uw}^{\top})^{-1}(H_{u w} {H_{w w}^{-1}} H_{xw}^{\top} -H_{xu}^{\top})\\
            &r = -\frac{1}{2}(H_{u u}-H_{u w} H_{w w}^{-1} H_{uw}^{\top})^{-1}(G_u - H_{uw} H_{w w}^{-1} G_w ).
            \end{aligned}$$

4.  The optimal adversarial policy is given by $w^*= Lx+l,$ where $$\notag
            \begin{aligned}
            &L = (H_{w w}-H_{uw}^{\top} H_{uu}^{-1} H_{u w})^{-1}(H_{uw}^{\top} H_{uu}^{-1} H_{xu}^{\top}-H_{xw}^{\top})\\
            &l = -\frac{1}{2}(H_{w w}-H_{uw}^{\top} H_{uu}^{-1} H_{u w})^{-1}(G_w-  H_{uw}^{\top} H_{uu}^{-1} G_u ).
            \end{aligned}$$

By following the same procedures (backward induction) as in the proof of Theorem \[theorem:solution\], it can be shown that the iterations in (\[def:P\]) and (\[def:g\]) are preserved. To save space, the details are omitted.

\[sebsec:H\_inf\] In comparison with (\[equ:newgame\]), the well-known $H_\infty$ optimal control [@bacsar2008h] solves the following zero-sum game $$\min_{\pi} \max_{w} \sum_{k=0}^{\infty} (x_k^{\top}Qx_k + u_k^{\top}Ru_k - \lambda \|w_k\|^2).\notag$$ Clearly, the deterministic game (\[equ:newgame\]) covers this case by letting $\bar{w}=0$.

Theorem \[theorem:certainty\] implies that the game with Wasserstein penalties is equivalent to the deterministic version in in the sense that the resulting optimal controllers are identical. Thus, it suffices to design a model-free algorithm to solve the deterministic game (\[equ:newgame\]).

Model-free Q-learning with Convergence Guarantees {#sec:algorithm}
=================================================

In this section, we develop a Q-learning algorithm with the simulator in Fig. \[pic:simu\] to solve the deterministic game (\[equ:newgame\]) and show its global convergence to the DR optimal controller in Theorem \[theorem:solution\].

An Online Q-learning Algorithm
------------------------------

Motivated by @al2007model, we propose a Q-learning algorithm to learn $Q_c(x,u,w)$ in (\[def:Q\_c\]) by solely using data from a simulator. We refer to it as the DR Q-learning algorithm since it yields the same optimal controller as the zero-sum game in (\[equ:wasprob\]).

By Theorem \[theorem:certainty\], $Q_c(x,u,w)$ can be parameterized with a symmetric matrix $H$, a vector $G$ and a scalar $s$. By using the Kronecker operator, we can reformulate it as a linear function with a parameter vector $\theta$.

Let $e = [x^{\top}~u^{\top} ~w^{\top}]^{\top} \in \mathbb{R}^q$ with $q = n+m+d$, $\bar{e} = [e_1^2, \cdots, e_1e_q, e_2^2, e_2e_3, \cdots, e_{q-1}e_q,e_q^2]^{\top}$ be the Kronecker product quadratic polynomial basis vector, $h$ be the vector formed by stacking the columns of the matrix $H$ and then removing the redundant terms introduced by the symmetry of $H$. Then the Q-function can be written as $$\label{equ:para_q}
\begin{aligned}
Q_c(x,u,w |\theta) &=
\begin{bmatrix}
x\\
u \\
w \\
\end{bmatrix}^{\top}
H
\begin{bmatrix}
x \\
u \\
w
\\
\end{bmatrix} +
G^{\top}
\begin{bmatrix}
x \\
u \\
w
\end{bmatrix} +s\\
&=
[h^{\top}~G^{\top}~s]
\begin{bmatrix}
\bar{e} \\
e \\
1 \\
\end{bmatrix} = \theta^{\top} \tilde{e}
\end{aligned}$$ with $\theta = [h^{\top}~G^{\top}~s]^{\top}$ and $$\label{def:e}
\tilde{e} = [\bar{e}^{\top}~e^{\top}~1]^{\top}.$$ A pair of optimal solutions to the zero-sum game (\[equ:newgame\]) under the parameter vector $\theta$ is given as $u^*(x) = K x + r$ and $w^*(x) = Lx+l$. Since $$V_c(x_k) = \min_{u_k}\max_{w_k} Q_c(x_k, u_k, w_k),$$ it follows from the Bellman equation that $$\label{equ:iter}
Q_c(x_k,u^*(x_k),w^*(x_k)|\theta) = d(x_k,\theta)$$ where $$\label{def:d}
\begin{aligned}
d(x_k,\theta) &= x_k^{\top}Qx_k + u^*(x_k)^{\top}Ru^*(x_k)- \lambda \|w^*(x_k) - \bar{w}\|^2\\
&~~ + \alpha Q(x_{k+1},u^*(x_{k+1}),w^*(x_{k+1})|\theta).
\end{aligned}$$ Clearly, $d(x_k,\theta)$ can be computed by using the sample $\{x_k, u^*(x_k),w^*(x_k), x_{k+1}\}$ from the simulator.

Now, we find $\theta$ by designing an iterative learning algorithm. Suppose that at the i-th iteration, the parameter vector is denoted as $\theta_{i}$ and the resulting pair of optimal policies are $u_i^*(x)=K_ix+r_i, w_i^*(x)= L_ix+l_i$. We sample a system trajectory $\{x_k^p, u_i^*(x_k^p), w_i^*(x_k^p), x_{k+1}^p\}_{p=1}^M$ of the length $M$ from the simulator, then $\theta_{i+1}$ is obtained by solving a least-squares problem $$\label{equ:theta_update}
\begin{aligned}
    {\theta}_{i+1}
    &=\arg \min_\theta \{ \sum_{p = 1}^{M} |    Q_c(x_k^p,u_i^*(x_k^p),w_i^*(x_k^p)|\theta) - d(x_k^p, \theta_i)  |^2  \}\\
     &=\arg \min_\theta \{ \sum_{p = 1}^{M} |   {\theta}^{\top} \tilde{e}(x_k^p) - d(x_k^p, \theta_i)  |^2  \},
\end{aligned}$$ where $\tilde{e}(x_k^p)$ and $d(x_k^p, \theta_i)$ are given by (\[def:e\]) and (\[def:d\]), respectively.

Since $u_i^*(x_k)$ and $w_i^*(x_k)$ are linearly dependent on $[x_k^{\top} ~~1]^{\top}$, solving (\[equ:ls\]) yields an infinite number of solutions. To this end, we manually add exploration noises to the control and disturbance inputs, i.e., $$\label{equ:explor}
    {u}_i^*(x_k) = K_i x_k + r_i + o_k^1,~~~~{w}_i^*(x_k) = L_i x_k + l_i + o_k^2,$$ where $o_k^1 \sim \mathcal{N}(0, \Sigma_1)$ and $o_k^2 \sim \mathcal{N}(0, \Sigma_2)$ with covariance matrices $\Sigma_1$ and $\Sigma_2$. This ensures that if $M > \frac{1}{2}(q+1)(q+2)$, there is a unique solution to (\[equ:theta\_update\]), i.e., $$\label{equ:ls}
{\theta}_{i+1} = \left(\sum_{p = 1}^{M}\tilde{e}(x_k^p)\tilde{e}(x_k^p)^{\top}  \right)^{-1}
\sum_{p = 1}^{M} \tilde{e}(x_k^p) d(x_k^p,\theta_i).$$ It is shown in @al2007model that the exploration noises do not result in any bias to $\theta$.

\[t\]

\[1\] Penalty parameter $\lambda$, discount factor $\alpha$, disturbance samples $\left\{\hat{w}^{(1)}, \ldots, \hat{w}^{(N)}\right\}$ from the physical world, length of a trajectory $M$, termination condition $\epsilon$. An optimal controller $u^*(x)= Kx+r$. Initialize ${\theta}_0 = 0$, and the optimal feedback policies $K_0 = 0$, $r_0 = 0$, $L_0 = 0$ and $l_0 = 0$. **Step 1: Q-function Evaluation** Collect $\{x_k^p, {u}_i^*(x_k^p), {w}_i^*(x_k^p), x_{k+1}^p\}_{p=1}^M$ from the simulator, where ${u}_i^*(x_k^p)$ and ${w}_i^*(x_k^p)$ are noisy inputs given by (\[equ:explor\]). Determine the target value $\{d(x_k^p, \theta_i)\}_{p=1}^M$ by using the trajectory. Update $\theta_{i+1}$ by $$\notag
        {\theta}_{i+1} = \arg \min_{\theta} \left\{ \sum_{p = 1}^{M} |  {\theta}^{\top} \tilde{e}(x_k^p) - d(x_k^p, \theta_i)  |^2  \right\}.$$ Terminate the loop and output $K_i,r_i$. **Step 2: Policy Improvement** Update the optimal policy pair $(K_{i+1}, r_{i+1})$ and $(L_{i+1}, l_{i+1})$ by $\theta_{i+1}$.

We present our DR Q-learning algorithm in Algorithm \[alg:q\_learning\] which terminates when the increment of ${\theta}_{i}$ is smaller than a user-defined constant $\epsilon$.

Convergence of the Q-learning Algorithm
---------------------------------------

We show that $\theta = [h^{\top}~G^{\top}~s]^{\top}$ in (\[equ:para\_q\]) can be solved by the value iteration in (\[def:P\]) and (\[def:g\]), whose convergence has already been shown in Theorem \[coro\].

Let $W=\text{diag}(Q, R, -\lambda I)$. Then we have the following results.

\[lemma3\] The update of $\theta_i = [h_i^{\top}~G_i^{\top}~s_i]^{\top}$ in (\[equ:ls\]) can be written as $$\label{equ:para_iter1}
        H_{i+1}=
        W+\alpha \begin{bmatrix}
        A & B & E \\
        K_{i} A & K_{i} B & K_{i} E \\
        L_{i} A & L_{i} B & L_{i} E
        \end{bmatrix}^{\top}
        H_{i}\begin{bmatrix}
        A & B & E \\
        K_{i} A & K_{i} B & K_{i} E \\
        L_{i} A & L_{i} B & L_{i} E
        \end{bmatrix},$$ $$\label{equ:para_iter2}
    \begin{aligned}
    &G_{i+1}^{\top}=
    \alpha (G_i^{\top} + 2 \begin{bmatrix}
    0  \\
    r_i \\
    l_i
    \end{bmatrix}^{\top} H_i) \begin{bmatrix}
    I  \\
    K_i \\
    L_i
    \end{bmatrix}\bigl[A~B~E\bigr] + \begin{bmatrix}
    0  \\
    0 \\
    2\lambda \bar{w}
    \end{bmatrix}^{\top},\\
    & \text{and} ~s_{i+1} =
     \alpha \bigl(s_i + G_i^{\top} \begin{bmatrix}
    0  \\
    r_i \\
    l_i
    \end{bmatrix} + \begin{bmatrix}
    0  \\
    r_i \\
    l_i
    \end{bmatrix}^{\top} H_i \begin{bmatrix}
    0  \\
    r_i \\
    l_i
    \end{bmatrix}
    \bigr) - \lambda \|\bar{w}\|^2.
    \end{aligned}$$

Define $$\notag
    \begin{aligned}
    &V = [\tilde{e}(x_k^1), \tilde{e}(x_k^2), \cdots, \tilde{e}(x_k^M)], \\
    &Y = [d(x_k^1, \theta_i), d(x_k^2, \theta_i), \cdots, d(x_k^M, \theta_i)]^{\top}.
    \end{aligned}$$ It follows from (\[equ:ls\]) that ${\theta}_{i+1} = (VV^{\top})^{-1}VY$. In the sequel, we show that $d(x_k, \theta_i)$ is linear with respect to $\tilde{e}(x_k)$, i.e., $Y = Vy(\theta_i)$, where $y(\theta_i)$ is a function of $\theta_{i}$.

We derive $d(x_k, \theta_i)$ as a function of $e(x_k)$. Since $$\notag
    \begin{aligned}
    &Q_c(x_{k+1},{u}_i^*(x_{k+1}),{w}_i^*(x_{k+1})|\theta_{i}) \\
    &~~~~~~~~~~~~~~~~~=e(x_{k+1})^{\top}H_i e(x_{k+1}) + G_i^{\top} e(x_{k+1}) +s_i,
    \end{aligned}$$ it follows from (\[equ:iter\]) that $$\label{equ:dd}
    \begin{aligned}
    d(x_k, \theta_i) & = e(x_k)^{\top}We(x_k) + \begin{bmatrix}
    0  \\
    0 \\
    2\lambda \bar{w}
    \end{bmatrix}^{\top}e(x_k)  - \lambda \|\bar{w}\|^2 \\
    &+ \alpha \big[e(x_{k+1})^{\top}H_i e(x_{k+1}) + G_i^{\top} e(x_{k+1}) +s_i\big].
    \end{aligned}$$

Moreover, the term $e(x_{k+1})$ in (\[equ:dd\]) can be written as $$\label{equ:e_e}
    \begin{aligned}
    &e(x_{k+1})=e\left([A~~B~~E]e(x_k)\right)\\
    &=e\big([A~~B~~E]\big(
    \begin{bmatrix}
    I  \\
    K_i \\
    L_i
    \end{bmatrix} x_k +
    \begin{bmatrix}
    0  \\
    r_i \\
    l_i
    \end{bmatrix}
    \big)\big) \\
    &=\begin{bmatrix}
    I  \\
    K_i \\
    L_i
    \end{bmatrix}
    [A~~B~~E]\big(
    \begin{bmatrix}
    I  \\
    K_i \\
    L_i
    \end{bmatrix} x_k +
    \begin{bmatrix}
    0  \\
    r_i \\
    l_i
    \end{bmatrix}
    \big) +
    \begin{bmatrix}
    0  \\
    r_i \\
    l_i
    \end{bmatrix} 
    \end{aligned}$$ $$\begin{aligned}
    &=\begin{bmatrix}
    I  \\
    K_i \\
    L_i
    \end{bmatrix}
    [A~~B~~E]e(x_k) +
    \begin{bmatrix}
    0  \\
    r_i \\
    l_i
    \end{bmatrix}. \\
    \end{aligned}$$ Inserting (\[equ:e\_e\]) into (\[equ:dd\]), $d(x_k, \theta_i)$ is written as a function with respect to $e(x_k)$. By using the Kronecker product as in (\[equ:para\_q\]), it follows that $d(x_k, \theta_i) = \tilde{e}(x_k)^{\top}y(\theta_i)$. Combining ${\theta}_{i+1} = (VV^{\top})^{-1}VY$, the proof is completed.

\[lemma:2\] The update of $H_i$, $G_i$, $s_i$ in (\[equ:para\_iter1\]) and (\[equ:para\_iter2\]) can be written as $$\label{equ:hp}
    \begin{aligned}
    H_{i+1} &= \begin{bmatrix}
    \alpha A^{\top} P_i A+ Q & \alpha A^{\top} P_i B & \alpha A^{\top} P_i E \\
     &\alpha B^{\top} P_i B+ R & \alpha B^{\top} P_i E \\
     *&  & \alpha E^{\top} P_i E-\lambda I
    \end{bmatrix},\\
    G_{i+1}^{\top} &= \left[\alpha g_i^{\top}A ~~~ \alpha g_i^{\top}B ~~~ \alpha g_i^{\top}E+2\lambda \bar{w}^{\top}  \right],\\
    s_{i+1} &= \alpha z_i - \lambda \|\bar{w}\|^2,
    \end{aligned}$$ where $P_{i}=\left[\begin{array}{lll}
        I & L_{i}^{\top} & K_{i}^{\top} \end{array} \right] H_{i} \left[\begin{array}{lll}
        I & L_{i}^{\top} & K_{i}^{\top} \end{array} \right]^{\top}$, and $$\label{def:pgz}
        \begin{aligned}
        &g_i^{\top} = (G_i^{\top} + 2 \begin{bmatrix}
        0  \\
        r_i \\
        l_i
        \end{bmatrix}^{\top} H_i) \begin{bmatrix}
        I  \\
        K_i \\
        L_i
        \end{bmatrix},\\
        &z_i = s_i + G_i^{\top} \begin{bmatrix}
        0  \\
        r_i \\
        l_i
        \end{bmatrix} + \begin{bmatrix}
        0  \\
        r_i \\
        l_i
        \end{bmatrix}^{\top} H_i \begin{bmatrix}
        0  \\
        r_i \\
        l_i
        \end{bmatrix}.  
        \end{aligned}$$

The iteration on $H_i$ in (\[equ:para\_iter1\]) can be written as $$\notag
        H_{i+1}=W+[A~~B~~E]^{\top}[I~~L_i^{\top}~~K_i^{\top}]H_i[I~~L_i^{\top}~~K_i^{\top}]^{\top}[A~~B~~E].$$

By the definition of $P_i$ in (\[def:pgz\]), we yield that $$\notag
    \begin{aligned}
    H_{i+1}&=W+[A~~B~~E]^{\top}P_i[A~~B~~E]\\
    &\hspace{-.8cm}=\begin{bmatrix}
    \alpha A^{\top} P_i A+ Q & \alpha A^{\top} P_i B & \alpha A^{\top} P_i E \\
     &\alpha B^{\top} P_i B+ R & \alpha B^{\top} P_i E \\
     *&  & \alpha E^{\top} P_i E-\lambda I
    \end{bmatrix}.
    \end{aligned}$$ Similarly, both $G_{i+1}$ and $s_{i+1}$ can be expressed in terms of $g_i$ and $z_i$.

\[lemma:3\] Iterations (\[equ:para\_iter1\]) and (\[equ:para\_iter2\]) can be written as the value iteration in (\[def:P\]) and (\[def:g\]), respectively.

It follows from (\[def:pgz\]) that $$\label{hhh}
            P_{i+1} = [I~~L_{i+1}^{\top}~~K_{i+1}^{\top}]H_{i+1}[I~~L_{i+1}^{\top}~~K_{i+1}^{\top}]^{\top}.$$ Since $K_{i+1}, L_{i+1}$ can be directly obtained using $H_{i+1}$ hence $P_i$ by (\[equ:hp\]), one can verify that (\[hhh\]) has the same expression as (\[def:P\]).

The iterations on $g_{i+1}$ and $z_{i+1}$ in (\[def:g\]) can be analogously derived.

The following theorem shows the convergence of the proposed DR Q-learning algorithm.

Let Assumption \[assumption\] hold and $M > \frac{1}{2}(q+1)(q+2)$, then the sequence $\{\theta_{i}\}$ in Algorithm \[alg:q\_learning\] converges to a unique optimal parameter vector $\theta$.

Lemma \[lemma:3\] shows that the update of $\theta_i = [h_i^{\top}~G_i^{\top}~s_i]^{\top}$ in (\[equ:ls\]) can be written as the value iteration (\[def:P\]) and (\[def:g\]), whose convergence has been proved in Theorem \[coro\]. Thus, $H_i,G_i,s_i$ converge with $H_0 =0,G_0 =0,s_0=0$, namely, $$\notag
    \begin{aligned}
    \lim\limits_{i \rightarrow \infty}H_{i} &= \begin{bmatrix}
    \alpha A^{\top} P A+ Q & \alpha A^{\top} P B & \alpha A^{\top} P E \\
     &\alpha B^{\top} P B+ R & \alpha B^{\top} P E \\
     *&  & \alpha E^{\top} P E-\lambda I
    \end{bmatrix}\\
    \lim\limits_{i \rightarrow \infty}G_{i}^{\top} &= \left[\alpha g^{\top}A ~~~ \alpha g^{\top}B ~~~ \alpha g^{\top}E+2\lambda \bar{w}^{\top}  \right]\\
    \lim\limits_{i \rightarrow \infty}s_{i} &= \alpha z - \lambda \|\bar{w}\|^2,
    \end{aligned}$$ where $P,g,z$ are given by (\[def:P\]) and (\[def:g\]).

\[htbp\]

![The long-term cost converges to the near optimal value within 30 iterations.<span data-label="pic:cost"></span>](cost){width="70mm"}

Numerical Examples {#sec:experiment}
==================

In this section, we demonstrate the effectiveness of our Q-learning algorithm on a regulation problem of a quadrotor and illustrate its convergence.

Experiment Setup
----------------

We consider a quadrotor that operates on a 2-D horizontal plane. The groundtruth discrete-time dynamical model is given by a double integrator as $$\label{def:model}
x_{k+1}=\begin{bmatrix}
1 & 0 & T & 0 \\
0 & 1 & 0 & T \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix} x_{k}+\begin{bmatrix}
\frac{T^2}{2} & 0 \\
0 & \frac{T^2}{2} \\
T & 0 \\
0 & T
\end{bmatrix}\left(u_{k}+w_{k}\right),$$ where the sample period is set as $T=0.1s$, $[x_{k,1},x_{k,2}]$ denotes the position coordinates, $[x_{k,3},x_{k,4}]$ is the corresponding velocity, and the input $u_k$ is the acceleration. Disturbances $w_{k,1}$ and $w_{k,2}$ from the wind are independent random variables, and $w_{k,1} \sim \mathcal{N}(1.8,0.1)$, $w_{k,2} \sim \mathcal{N}(0.5,0.1)$.

Our objective is to regulate the position of the quadrotor to the origin with minimum energy consumption. To this end, the parameters of the cost function are set as $
    Q = I~\text{and}~R = 0.2\times I.
$ By Theorem \[theorem:solution\], the distribution deviation penalty parameter $\lambda$ should satisfy $\lambda I -\alpha E^{\top} P E > 0$, which in our experiments is $\lambda > 0.22$. For a clear presentation we select $\lambda = 6$, and the effect of $\lambda$ is to be examined later. The discount factor $\alpha$ is set as $\alpha = 0.99$ such that Theorem \[coro\] holds. The length of the trajectory $\{x_k^p, \hat{u}_i^*(x_k^p), \hat{w}_i^*(x_k^p), x_{k+1}^p\}_{p=1}^M$ in each iteration is set as $M = 900$.

\[t\]

Convergence of the DR Q-learning Algorithm
------------------------------------------

We now demonstrate the convergence of the proposed DR Q-learning algorithm. Suppose that the disturbance samples from the physical world are given as $\{\hat{w}^{(i)}\}_{i=1}^{10}$ with the sample mean $\bar{w} =[1.7974, 0.5405]^{\top}$. Then, we apply Algorithm \[alg:q\_learning\] to train the WDR-LQR controller. We select the finite-horizon cost $$\label{def:finite_cost}
J_i = \sum_{k=0}^{h} \alpha^{k} (x_k^{\top}Qx_k + (u_k^{i})^{\top}Ru_k^i - \lambda \|w_k^i- \bar{w}\|^2 )$$ as an indicator for the convergence, where $u_k^{i} = K_ix+ r_i$ and $w_k^{i} = L_ix+ l_i$ are the pair of optimal solutions at the i-th iteration. Clearly, the convergence of policies $(K_i,r_i)$ and $(L_i,l_i)$ can be reflected by the convergence of $J_i$ in (\[def:finite\_cost\]). As illustrated in Fig. \[pic:cost\], the finite-horizon cost (\[def:finite\_cost\]) converges almost exponentially fast with respect to the number of the iteration.

Comparisons to Other Controllers
--------------------------------

We illustrate the effectiveness of our Wasserstein DR linear quadratic regulation (WDR-LQR) via comparisons with (a) the canonical LQR and (b) the classical $H_{\infty}$ control (${H}_{\infty}$-LQR), as detailed below.

\(a) The LQR controller is a linear state feedback, namely $u = K_qx$ with $K_q=\left(R+B^{\top} P_q B\right)^{-1} B^{\top} P_q A$, where the matrix $P_q$ is the solution to the algebraic Riccati equation $$A^{\top} P_q A+Q-A^{\top} P_q B\left(R+B^{\top} P_q B\right)^{-1} B^{\top} P_q A=P_q.$$ (b) The classical $H_{\infty}$ control [@bacsar2008h] seeks to solve the following minimax problem $$\label{equ:h_inf}
    \min_{\pi}\max_{\omega} \sum_{k=0}^{\infty} (x_k^{\top}Qx_k + u_k^{\top}Ru_k - \lambda \|w_k\|^2).$$ We manually tune its parameter $\lambda$ to yield good control performance, which is finally set to $\lambda = 0.25$.

In Fig. \[pic:comparex1\] and \[pic:comparex2\], the position $[x_{k,1},x_{k,2}]$ is regulated to the origin under our WDR-LQR controller with the initial state $x_0 = [1.2 ~~0.6~~ 0.5~-0.5]^{\top}$. In contrast, the LQR and ${H}_{\infty}$-LQR controllers fail to steer the position to the origin, though the latter has the well-known robustness and disturbance rejection capabilities [@bacsar2008h]. Fig. \[pic:compareu1\] shows that the WDR-LQR consumes less energy than the ${H}_{\infty}$-LQR.

To test the robustness of the WDR-LQR controller, we apply it to a system where we instead use a Gaussian mixture distribution to generate the disturbance $w_{k,1}$ in (\[def:model\]). The Gaussian mixture distribution is a mixture of $\mathcal{N}(1,0.2)$ and $\mathcal{N}(0.9,0.5)$ with the same weights. The evolution of the position $x_{k,1}$ and input $u_{k,1}$ are displayed in Fig. \[pic:gmm\]. It can be observed that the WDR-LQR exhibits the best trade-off between the state bias and energy costs.

Effects of the Penalty Parameter $\lambda$
------------------------------------------

We observe from (\[equ:wasprob\]) and (\[equ:h\_inf\]) that $\lambda$ is in effect in both WDR-LQR and $H_{\infty}$-LQR. To empirically show how $\lambda$ works, we apply Algorithm \[alg:q\_learning\] under 20 different $\lambda$ ranging from $\lambda = 0.22$ to $\lambda = 10$ and study the performance of the resulting controllers. Based on Monte Carlo methods, we conduct 500 independent trials using each controller and exhibit the mean and variance of the steady position $\bar{x}_1$ at $time =18s$, see Fig. \[pic:mean\] and Fig. \[pic:variance\]. We observe that for the $H_{\infty}$-LQR, there is an apparent steady-state bias. The effect of $\lambda$ on the variance of $\bar{x}_1$ is similar for the $H_{\infty}$-LQR and WDR-LQR.

We further simulate the long-term cost with respect to $\lambda$ in Fig. \[pic:cost\_lambda\]. We provide a possible explanation for this result in the follows. For the $H_{\infty}$-LQR, a large $\lambda$ implies that the adversarial disturbance should be near to zero, see (\[equ:h\_inf\]). Thus, its performance may unexpectedly degrade as largely deviated disturbance $w_{k,1}$ appears. However, in the WDR-LQR, $\lambda$ penalizes the deviation of the adversarial disturbance distribution from the empirical one $\nu_N$. Since the groundtruth distribution is closer to $\nu_N$ than zero, our WDR-LQR performs better.

Conclusion
==========

This paper proposed a sample-based DR Q-learning algorithm to learn a controller with robustness to disturbance distribution errors. We formulated the stochastic optimal control problem as a zero-sum game with Wasserstein penalties. We first derived an explicit solution to the zero-sum game assuming that the system model $(A,B,E)$ was known. Then, we developed its Q-function and showed that the zero-sum game was equivalent to a deterministic version. We designed a Q-learning algorithm for the deterministic game and showed its global convergence. Finally, simulations were conducted to show the effectiveness of our DR RL algorithm.

Recent years the policy gradient methods show tremendous success, which can be used to solve the zero-sum game. This will be our future work.

{'source': 'arXiv_out/2010'}