Solving Robust MDPs through No-Regret Dynamics
Authors: Etash Kumar Guha
Venue: Accepted by TMLR ()

Abstract: Reinforcement learning is a powerful framework for training agents to navigate different situations, but it is susceptible to changes in environmental dynamics. Generating an algorithm that can find environmentally robust policies efficiently and handle different model parameterizations without imposing stringent assumptions on the uncertainty set of transitions is difficult due to the intricate interactions between policy and environment. In this paper, we address both of these issues with a No-Regret Dynamics framework that utilizes policy gradient methods and iteratively approximates the worst case environment during training, avoiding assumptions on the uncertainty set. Alongside a toolbox of nonconvex online learning algorithms, we demonstrate that our framework can achieve fast convergence rates for many different problem settings and relax assumptions on the uncertainty set of transitions.

Published in Transactions on Machine Learning Research (06/2024)
Solving Robust MDPs through No-Regret Dynamics
Etash Guha
SambaNova Systems, University of Woshington
Reviewed on OpenReview: https: // openreview. net/ forun? id= SdCuffaghh
Abstract
Reinforcement. learning is powerful framework for training agents to navigale different situations, but it is susceptible to changes in environmental dynamics. Generating algorithm that can find environmentally robust policies efficiently and handle different model parameterizattons without imposing stringent assumptions on the uncertainly set of transitions difficult due to the intricate interactions between policy and environment. In this paper, we address both of these issues with a No-Regret Dynamics framework that utilizes policy gradient methods and iteratively approximates the worst case environment during training, avoiding assumptions the uncertainty set. Alongside a toolbox of nonconvex online learning algorithms,, we demonstrate that our framework can achieve fast convergence rates for many different problem settings and relax assumptions on the uncertainly set of transitions.
1 Introduction
Reinforcement learning (RT) is a powerful subset of machine learning that enables agents to learn through trial-and-error interactions with their environment. RL has succeeded in various applications such as game playing, robotics, and finance (Sutton & Barto 2018). However, when trained policy operates in different environmental dynamics than the training environment, it often underperforms and achieves suboptimal rewards (Farebrother et al., 2018 Packer et al. 2018 Cobbe et al. 2018 [onn al., 2019 Raileanu &
Fergus 2021). Mitigating disastrous failures of RI-trained agents in practice can prevent many undesirable
outcomes (Srinivasan et al.) 2020 Choi et al. 2021 Robust Markov Decision Processes (MDPs) have emerged
as a promising solution to mitigate this problem and address the issue of the sensitivity of reinforcement learning to changing environments. The Robust MDP problem is finding a policy that maximizes some chosen objective iunction in the worst-case environment. By optimizing policies against hostile environmental dynamics, Robust MDPs provide a more stable approach to training agents (Nilim & Ghaoui 2003 Bagnell
ct al. Lyngaar 2005).
While the Robust MDP is powerful framework for changing environments, designing robust. algorithms that solve such MDPs still presents significant challenges. One primary difficulty arises from the nonconvexity of many objective functions in Robust MDPs. Additionally, the intricate interactions between policy and environment in many MDPs make the problem difficult to handle. Many Value Iteration based approaches have been studied to solve Robust MDPs under a Direct Parameterization sctting (Nilim Ghaoui 2003
Iyengar 2005 [Bdrinnth & Kalathil 2021 Wiesemann et al. 2013 Roy al., 2017 Tamaa et al.] 2014].
However, many recent works have focussed extending these methodologies past the direct parameterization
setting (Dong et al. 2022 Wang & Zou 2022) by utilizing modern policy gradient methods. Such gradient techniques are popular for their scalability and versatility to many different problem settings (Williams) 1992 Sutton et al. 1999: Konda & Tsitsiklis 1999 Kakade [201]) Most works make convergence explicit in Robust MDPs with such gradient techniques often by assuming that the set of possible adversarial environments, known as the uncortainty set, take on specific shapes, such as Rectangular scts (Dong et al., 2022), R- Contamination sets (Wang & Zou 2022), or Wasserstein balls Clement & Kroer (2021). Finding algorithms that solve Robust MDPs for general shapes of uncertainty sets is a complex and open problem.

---

Published in Transactions on Machine Learning Research (06/2024)
To more fundamentally attack this problem, we want to form an algorithmic framework to design algorithms to solve Robust MDPs under many different settings. Several works have solved finding robust minima in different problem settings using& No-Regret Dynamics framework (Wang et al. 2022a Balduzzi et al.) 2018) Syrgkanis et al. 2015). Such a framework frames an algorithm to find robust minima as a two-player game between a learner and the environment. These frameworks enjoy both versatility in design and simplicity of analysis. Most importantly, the convergence of an algorithm from this framework can be bounded in terms of the expected regrets of both players' online strategies without strong assumptions. We use a similar framework style to attack the Robust MDP to more fundamentally attack the challenges of limiting assumptions and versatility to different settings. Our proposed game precisely consists of two players: policy and environment players. In each round of the game, the policy player first picks a policy and tries to maximize its objective function. After that, the enviromment observes the policy and then chooses a hostile environment to minimize the policy player's objective function. The two players repeatedly play against each other, and the goal to converge to a robust minimum, which naturally yiclds a policy that is robust to worst-case environments. This framework has three concrete advantages. First, in each round, the framework calls for explicitly approximating the worst-case environment. This step is critical to relax assumptions the shape of uncertainty set of environments. Second, both players can choose any online strategy, including gradient-based updates. This flexibility makes this framework applicable to host of problem settings. Third, the time taken till the algorithm converges to a robust equilibrium is bounded by the regret of the two players' chosen strategies. This makes both algorithm design and convergence analysis simple.
To utilize our framework, we provide various possible online strategies for each player. Given the nonconvexity of the objective functions in Robust. MDPs, we explore the existing nonconvex online learning literature to develop our toolbox and augment it with several new nonconvex online algorithms that work well in our framework. For the first augmentation, can see the incoming loss function and developed two new algorithms known as Best-Response and Follow the Perturbed Leader Plus (FTPL+), which enjoy improved regret rates with this ability to peak at the policy player's 's chosen policy. The second augmentation is that the nonconvex online learning literature often depends on a minimization oracle that can find a global minimizer of the nonconvex loss function (Suggala & Netrapalli 2019). While this is impossible to build in every setting, we identify the MDP settings under which such an oracle is accessible. To be more specific, we demonstrate that for both the policy and environmental players, the Value Function, common objective for Robust MDPs, exhibits gradienl-dominaacee Thus, using Projected Gradient Descent (PGD) will surprisingly suffice as minimization oracle for both players. This choice has the added benefit of enjoying the scalability of gradient methods. Thus, under different conditions, inchuding simple mndieen-dominance, smooth MDPs, or strongly gradient-dominated MDPs, we build different algorithms from our framework using different algorithms that take advantage of each setting. With our framework, proving convergence for each algorithm is simple yet powerful. For example, in the most common setting where the objective function is the Value Function, our algorithm achieves the strong convergence rate of O (T-t) where T is the number of iterations of our algorithm. This rate is competitive with the most recent Robust MDP algorithms from the literature. Moreover, due to the explicit approximation of the worst-case environment throughout the training process, we do not need an assumption on the uncertainty set shape; instead, we only need the uncertainty set to be convex.
make use of the fact that the environment player in our framework
We utilize our algorithmic framework to provide different algorithms for Robust MDPs with gradient- dominance, smooth MDPs, and strongly dominntt-dmmintee MDPs. We also prove robust convergence rates with only a convexity assumption on the uncertainty set of environments. Alongside these guarantees, we run several small experiments on the convergence behavior of our algorithm where the Value Function is the optimization objective in the GridWorld MDP. Our small experiments corroborate this convergence rate in Section i
Contributions Our contributions are as follows.
We design an algorithmic framework for generating algorithms to solve Robust MDPs based on No- Regret Dynamics. Alongside our framework, we develop novel, no-regret online learning algorithms to use with our framework. This framework is versatile and can work for various problem settings, including direct parameterization. Moreover, due to the explicit approximation of the worst-case
2

---

Published in Transactions on Machine Learning Research (06/2024)
environment during training, we need only the uncertainty set of transitions to be convex to guarantee convergence.
Many of the no-regrel online algorithms in our framework require access to a Minimization Oracle. We show that when the objective function of the game is gradient-dominated for both players, we can use Projected Gradient Descent the oracle. We also provide tools for identifying the conditions under which the gradienl-dominated property of an objective function is ensured. For example, we show that when the MDPs' objective function is the Value Function in the tabular setting, both players' objective functions enjoy peadient-dominanee We then prove that when the objective function is the Value Function in the direct parameterization setting, our framework can generate an algorithm that convergence rate. We empirically verify that our algorithm finds a robust policy at a rate of roughly O (I) in the GridWorld MDP across several uncertainty set shapes and sizes.
yields an O T
3. Finally, we demonstrate that even faster convergence rates can be obtained when the objective function is Lipschitz smooth or enjoys strong gradient-dominance with advanced online dynamics. To our knowledge, this is the first work to study Robust MDPs with strong gradient-dominant
2 Related Works
Some of the first algorithms to solve Robust MDPs with convergence guarantecs and empirical performance are via transition dynamics set assumptions/ Nilim & Ghaoui 2003 [yengar 2005).
Robust MDPs
Sinha & Ghate, 2016) or Robust Q-Learning (Wang & Zou 2021). After the introduction of Robust MDPs, several works studied the sctting
Robust Policy Iteration (Mankowitz et al. 2019 Tamar et al. 2014
where only samples from the MDP are accessible (Wang & Zou 2022 Badrinath & KKlathil 2021 Roy et al.
2017 Tessler et al. 2019). Goyal & Grand-Clement (2023) expanded the rectangular uncertainty set using Factor Matrix Uncertainty Sets to be more general. Zhang et al. (021) introduced a different adversary where the stochastic samples from the central MDP are adversarial. This work focuses solely on optimizing the policy where the uncertainty set is known. Regarding robust policy optimization, Mankowitz et al. (2018) proposed robust learning through policy gradient for learning temporally extended action. Mankowitz et al. (2019) used Bellman contractors to optimize the robust objective but did not provide any sub-optimality guarantees, only convergence. Dong al. (2022) used online approach similar to ours but used rectangular uncertainty set assumptions and did not utilize any no-regret dynamics. Wann et al. (0223 and TTamar ct al. 2014] discussed a policy iteration approach to improving the Average Reward Robust MDP using Bellman Equations. Wang et al. (2022b) uses a similar game framework but does not use no-regret dynamics or sophisticated online learning algorithms to achieve their guarantees, achieving a worse convergence rate with less robust guarantocs.
Wang & Zou (022) one of the best-known algorithms for solving Robust MDPs in this setting with policy gradient methods. Unlike our work, they rely on the uncertainty set taking the form of R- CoCommmmination set, while our algorithm needs no such assumption. Morcover, CCement & Krocr (0021) do approximate the worst-case environment iteratively. However, unlike our work, they utilize Wasserstein uncertainty set assumptions and focus on direct parameterizations. There are also other forms of Robust MDPs, including
distributionally robust MDPs (Xu & Mannor 2010 Ruszezyúski] 2010 Shapiro 2016 Xu & Mannor 2009
Petrik 2012 Ghavamzadeh et 2016 Chen et al., 2019), soft-robust MDPs (Buchholz & Scheftelowitsch
2019 .obo et al.] 2020 Steimle et al. 2021 and noise robustness (Pattanaik et al.] 2017 Eysenbach &
Levine 2021b.
No-Regret Learning In the context of game no-regret learning, McMahan & Abernethy 2013) used similar game framework to solve lincar optimization. In contrast, Wang et al. (2022al) used this framework for solving binary linear classification. Wang et al. (2021) used these frameworks to solve Fenchel games, phrasing many optimization algorithms. Daskalakis et al. (2017) showed that using a similar framework using online players for training GANs yields strong thcoretical and empirical improvements. The classical [Syrgkanis] et al. (2015) uses No-Regret Dynamics to solve social welfare games. Balduzzi et al. (2018) helped show the convergence of these games even in adversarial settings and explained gradient descent as two-player game.
3

---

Published in Transactions on Machine Learning Research (06/2024)
3
Preliminaries
In this section, we present the problem setup along with some standard assumptions and definitions.
3.1 Notation
We denote our infinite horizon, 7-discounted MDP tuple of (8, Pw, R), where S is set of states, A is a set of actions, Pw is a transition dynamics function parameterized by W that maps a state-action-state triple 8, a' E S x A x S to a probability between O and 1, and R is a reward function that maps a state s to reward т. Here, W parameterizes the transition dynamics belonging to some bounded convex set W. Moreover, we will denote Rmax as a constant denoting the largest possible value of R. We will assume that both S and A are finite sets. We will design a policy Te parameterized by a term 0 T where T is a bounded convex set of vectors of dimension d for some constant d. This policy xo maps a state action pair 8, E 8 x A to probability [0. For most of this paper, will refer to my π where clear. We will not specify the form W and 9 take since that depends on the parameterization of the policy and transition dynamics. For example, under direct parameterization for both transition dynamics and policy, W belongs to probability simplex W E |iS]x|A|xI and belongs to the probability simplex E Six|AI
We denote the value function V of state s under the policy a and transition dynamics Pww as (s) This function is the expected value function of arriving in a state s. We will define μ A as some probability will slightly abuse notation and call V = μ VV where will define d% (s) and d5
distribution over the initial states. Moreover, VH is the vector of value functions for all states. Moreover, distribution over the occupancy of states when policy π interacts with an environment of dynamics W given the initial state so. Formally, this is written as
dz, (s) as the probability
d (s) = (3)
= (1-1) 7)
PPP(s s|so, n, TV.
t=0
We choose to use either (s))) (s) and d=, (s) based on the context. Moroever, the state visitation distribution under initial state distribution is formally (7(() =
[d%, (s) and dW (s) = E [dW (s)].
3.2
Robust Policies
Our main goal is to create a policy where some objective function over the initial state distribution is large as possible against the worst environments. Within different formulations of Robust MDPs, there may be different objective functions for the robust optimization, which we denote as g(T,, W). One common setup of Robust MDPs is where g( W) is simply the Value Function given x and W, specifically g(T, W) = V (n).
Definition 3.1. We are in the infinite horizon setting where Y serves as a discount factor and is a positive constant less than Given a policy a and a transilion dynamiics Pw, we defic the value function vecursively as
(s) R(s) + Σ (a,
Σ Pw (s)
S'ES
In this setting, the Robust MDP problem simply the task of finding a policy л that maximizes the Value Function under worst-case transition dynamics as in
arg max min TET WEW g(T, arg max min V (n).
RET WEW
However, in different setups such as Control Regularized MDPs (Bhandari & Russo 2022 it may be desirable to find policy solving similar robust optimization problem with differont objective function. For example, one may wish to regularize the policy parameter as in g(TT, W) = Vi7" (n)) - ||0 To generalize the Robust MDP problem to all such possible MDPs, we will denote the optimization problem as the following. Definition 3.2. The Robust MDP problem is that of finding a such that क = arg max min g(TT, W). RET wew
4

---

Published in Transactions on Machine Learning Research (06/2024)
To connect this more clearly to work repeated games, we will view this as finding a policy that minimizes the suboptimality, Lee, arg max min g(T",, () min g(T, W). Improving the robustness of the policy can WeW
x'ET Wew similarly be seen as reducing the difference between our policy's robustness and the best policy's robustness. The second definition intuitively connects to the online learning literature definition of regret. We will similarly use this algorithmic perspective to design a Robust Policy Optimization algorithm that minimizes the suboptimality of the learned policy with the least amount of computational complexity possible. Similar min-max games have been solved in the past using No-Regret Dynamics, a powerful and versatile framework for algorithm design. Given its existing connect ion to robustness (Wang el al. 2022a ), we explore how to use a No-Regret Dynamics based framework to solve the Robust MDP problem.
4 No Regret Dynamics
In this section, we present a general No-Regret Dynamics framework. We then demonstrate how such a framework can be used to generate algorithms for Robust MDPs.
Algorithm 1: No-Regret RL
4.1 The General Framework
Data: T
for t E [T] do
Our No-Regret framework is presented in Al- gorithm Intuitively, we iteratively choose policy that performs well in previously seen adversarial environments, and we iteratively look for adversarial environments. In the end, the policies produced at the later rounds will become more and more robust. Specifically, in each round / of this algorithum, our policy player called OL*, chooses policy ne time step t. Our second player is W-player, called OLW
OL" chooses a policy: n. f- OL";
OLW sees the policy: OLW + Te
OL W chooses transition dynamics: W f-
OT,W;
OL" sees the transition dynamics: OL We
OLW W incur losses: OLW < lWW);
OL" incur losses: OL +- hT(T)):
end
which will see the policy Te outputted by the policy player and, then, outputs a transition dynamic W,. The policy player then sees the W; that was chosen. The policy player incurs loss he(me), and the environment player then incurs a loss (W,) corresponding to their decision. They repeatedly play this game until an equilibrium is reached. Here, the online players OL* and OL W can be any online stratogy. In Wang et al. (2022a), example strategies for online players include Mirror Descent and Follow the Leader. The performance of strategy for either online players can be measured in terms of regret. By definition, the regret of the W- W-player is equivalent to Similarly, for the player, we have that
Regw 4(W,) min Σ 4(W))
T Reg. Σ ha( - min Σ hx(TT)
t=0
t=0
This framework is a simple and versatile method of solving many optimization problems. We need only choose the online algorithms that the r-player and W-player employ and the loss function they see. The benefit of a No-Regret Dynamics framework that when the loss functions for both players are negative of the others, the algorithm's 'ss convergence is simply the convergence for two players. By setting (W,) gWW, to m,) and h,(m,) WW,, n4), have Theorem 4.1.
Theorem 4.1. We have the difference between the robustnesses of the chosen policies and any policy ā is upper bounded by the regret of the two players
min
g(W ())
min Σ
g(" TT) S Regw + Regx.
T TW-
T
TW-EW eW
t=0
t=
5

---

Published in Transactions on Machine Learning Research (06/2024)
Here, Regw and Reg, are the two average regrets of the two players OLW and OL
As in Theorem 4.1 the convergence of Algorithun] explained by the regret of the two players. This framework is both powerful and intuitive. Say we are in the traditional Robust MDP setting where g(W, T) = VW (1). We can get convergence guarantees for the robustness of our setting by configuring the loss functions 4 and hy in the following way. In this setting, the tth loss function for the W W-player is 4<W)) = VW; (4) and for the 7-player is ( = - WW; (p). Setting the loss functions according to the above, we similarly get the following convergence guarantee based on the regret of the two players, just like in Theorem 1.1 Therefore, despite the nonconvexity, we have simple framework for solving the Robust MDP problem. Since we approximate the worst-case environment at every round, only need an assumption that the uncertainty set of transitions is convex. Morcover, we have the flexibility to generate many algorithms for different scttings by choosing different online learning algorithms for both players. However, many recent online learning results require the underlying loss functions to be convex or strongly convex. Regrettably, in the simplest setting where (W, x) Vi (μ), neither of these properties are satisfied. Therefore, we must look for efficient online learning algorithms for nonconvex loss functions. We now present a toolbox of such online learning algorithms.
4.2 Online Learning Toolbox
To generate an algorithum from our No-Regret framework in Algorithm | we need only choose strategies for both players. Here, we develop toolbox of nonconvex online learning algorithms usable in our framework. We summarize our toolbox in Algorithm 2
Online algorithms for the x-player First, we present two existing algorithms from Suggala & Netrapalli (2019), namely Follow the Perturbed Leader and Optimistic Follow the Perturbed Leader, which achieves strong convergence in expectation in nonconvex settings and is suitable for the 7-player. At each time step, the Follow the Perturbed Leader algorithm generates a random noise vector o, according to an Exponential distribution with parameter y). Intuitively, this noise vector helps the online learner avoid local minima. It. then chooses 2, Oa [E=|]h h, - -.).. Here, O& is Approximate Optimization Oracle that approximately minimizes the received loss function h; to accuracy a. The Optimistic Follow the Perturbed Leader follows a similar procedure, except it chooses x, = Oa (m, + E h o,) where m, is some optimistic function. The main dependency of their regret bounds is that there exists Approximate Optimization Oracle O.. Definition 4.1. An optimization oracle is a function that takes some nonconeez function f and returns approzimate minimizer x² such that
f(x*) - (a,,") < [inff())
(o, - a.
Throughout this section, we will assume the presence of such an oracle and discuss how to set this oracle later. Suggala & Netrapalli (2019) prove a regret bound for Follow the Perturbed Leader and Optimistic Follow the Perturbed Leader algorithms when they can access such an oracle.
Online algorithms for the W-player Note that, for our framework, the environmental player can see the incoming loss function before choosing an environment, but neither of the aforementioned methods can account for this. To address this problem, we prove that 'Best Response' algorithm achieves even smaller upper bound regarding regret. The Best Response algorithm assumes knowledge of the coming loss function and returns the value that minimizes the incoming loss function. Formally, the Best Response algorithm outputs I, = arg min (x). This is a useful algorithm given that the W player can see the output of the x player when making its decision and greatly reduce its regret. We prove this in the following regret bound. Lemma 4.1. Suppose have incoming sequence of loss functions f. for t E [T] with optimization oracle that can ménómize a function to less than ervor. The Best Response algorithm satisfies the following regret bound
T
T inf TREX t=1
f((x))
T
6

---

in Published in Transactions on Machine Learning Research (06/2024)
Algorithm 2: A set of useful online learning algorithms Input: 7), Oa for f ,,...;I do
Sample a E Rd and 0r ~ Exp(1) where i E [d]
FTPL: : :4 Oa
Σ [i(x) - -(0
OFTPL[m}] :2x= O.. Σ li(x)) mm(()) (0,
Best-Response 2t = On (ft(z))
FTPL+: 31 Oa Σ (((())((00))
end
We will also prove the regret of one more algorithm, Follow the Perturbed Leader Plus. Similar the Follow the Leader Plus algorithm from Wang et al. (2021), Follow the Perturbed Leader Plus assumes knowledge of the incoming loss function and then outputs the minimizer of the sum of all the loss functions minus the noise term. Formally, Follow the Perturbed Leader Plus outputs 2, that satisfies 2; arg min E 4(xx)) - (o, zz).
2, While this algorithm achieves worse regret than Best Response, it produces more stable outcomes. This will useful for later extensions, such as Smooth Robust MDPs. In fact, Follow the Perturbed Leader Plus is equivalent to OFTPL, when the optimistic function m, = 4 the true loss function 4. We present the regret of this algorithm here.
Lemma 4.2. Let 1) be the constant paramelerizing the exponential distribation from which the noise at is drawn and be the dimensionality of the set of choices X' Moreover, denote the marimum distance between any two points in X, i.e. D max _|ax,IIx= [||xx= x' 112. Assume access to an optimization oracle that yields a. Ex
solutions with at most error a. Given a series of choices by FTPL+ Z1,..., DT with loss functions l....,,ry the regret in expeclation upper bounded by
T Σ T
dD 0
((x))
inf Σ T ZEe
(())
+ +a) n/T
We summarize these online strategies in Algorithm 2 These two algorithms are suitable choices for the environmental player, and the two algorithms from Suggala & Netrapalli (2019) suitable choices for the policy player. However, we still have the issue that an Approximation Optinization Oracle is generally challenging to parameterize. However, While the objective functions of Robust MDPs do not exhibit convexity, they exhibit some settings. This property helps us design sufficiont Approximation Oracle.
exploit a unique characteristic of many Robust MDP variants.
5 Constructing the Optimization Oracle
The ouline learning algorithms demonstrated in the previous section require having access lo an approzimale optimization oracle. However, designing the approximate optimization oracle can a complex problem. In this section, we first show that such an oracle can be casily constructed when the objective function is gradient-dominated We then demonstrate that under direct parameterization, the gradient-dominanee property is satisfied.
7

---

Published in Transactions on Machine Learning Research (06/2024)
5.1
Dominene
Algorithm 3: Projected Gradient Descent
Data: Initial guess Ho, step size 3, projection operator Projx
A function is gradienl-dominated if the difference between the function value at a point and the minimal function value is upper bounded on the order of the function's gradient at the point I. We formalize this in the below definition.
for = to To 1 do
2++1 + Projx fVf()))
end
Definition 5.1. We say a function f gradient-dominne for set X with constant K. if
f(x) min fx=") -Kmin Vf(x)). BEX
2+xx
Here, K. is some constant greater than 0.
As noted by Bhandari & Russo [2022), this gradient-dominated property is relatively common for many different RL scttings, including Quadratic Control or direct parameterization. It is useful for proving convergence guarantees for traditional policy gradient methods (Agarwal et al. 2019). For gradient-dominalel
functions, one can use projected gradient descent to minimize the function f. We recap projected gradient descent in Algorithm 3 Namely, Bhandari & Russo
2022 shows that
Here, To the number of iterations of Projected Gradient Descent runs. Moreover, the function Cr. is used for brevity for ea and ow later. Also, D max
Lemma 5.1. The below properly only holds if f is gradient-dominated and 3 & min supli
x.r ||x- ||x=x'll 1211.. Given that V f is L-Lipschitz continuous, the sequence
2141 = Projx((2 (vf(z))) enjoys the property
2T2 inff(x)))
f(XTe) - (inff(=)( x
BTO
(T,
Ideally, we would like to use projected gradient descent our Approximate Optimization Oracle for OL and OLW since it is simple and utilizes scalable gradient-based based techniques. However, this would require the loss functions 4 and he to be gradient-dominated. While not generally true, this is known to hold in many cases. Gradient-dominance is a well-known phenomenon for the æ-player when the Value Function is the objective function, as seen in Agarwal al. (2019). We formally list some helpful conditions here.
Condition 5.1. Here, we list the conditions we have.
The function f1)(() - (a, x)) is gradient-dominate enabling the use of FTPL+
The function Σ fi(x) - (a,x)) is gradient-dominatee enabling the use of FTPL.
The function En-1 f1(x) + Se- (a,x)) is gradient-dominaale enabling the use of OFTPL.
4. The function f( is setiient-ddminateed enabling the use of Best Response.
We will first provide tools useful for showing when these conditions hold.
5.2 Tools for Demonstrating Gradient-Dominare
Here, we will provide the tools to show that any of these conditions hold for the objective functions for cither the or W players. We have a gradient term within the terms of gradient-dominanee from Definition 5.1 In many cases, the loss function will often contain the Value Function. Therefore, we must know what the gradients of the Value Functions will be for both players. While this known for the policy player from the Policy Gradient Theorem (Sutton Barto 2018), we demonstrate similar result for the gradient of the Value Function for the W W-player.
8

---

Published in Transactions on Machine Learning Research (06/2024)
Lemma 5.2. The gradient of the value function v with respect to the parameter W, denoted as Vw VW (s)),, is given by
1 Σ d (t) (s').
Vw (s)
Now, we express the suboptimality of transition dynamies parameter W in terms of the gradient of the Value Function.
While this is shown via the Performance Difference Lemma from Kakade & Langford (0022) for the policy player, we need a similar lemma for the transition dynamics. The Performance Difference Lemma relies on the Advantage function. We will define an analogous advantage function for the transition dynamics. Intuitively, this Advantage Function is the value of laking state over the expected value over all states. Given this, we can provide an analog of the Performance Difference Lemma for the W-Player. We provide such lemma here.
Lemma 5.3. Given two different transition dynamics parameters W and W we have that a, (w(n) (w)(u)) = =E dw ( A (6' a,,))
8'
Here, we define the W- WV-Avantage Function AW (s',,,s) 7V Vs(s).
We have presented the tools necessary to demonstrate gradient- domiinanoiinneeee in many cases. While many MDP scttings exhibit gradient-domnance (Bhandari & Russo 2022), we demonstrato how to prove gradient- dominance for both players' loss functions under direct parameterization.
5.3 Direct Parameterization
We now begin with the direct parameterization case with standard Robust MDPs. This setting is of the most standard settings for MDPs. Here, (w(s',a,ss a) "W. directly parameterizes the transition dynamics, (a, = Q a, and g(W,*) = VW (n). Morcover, the set of transition dynamics is some convex bounded sct, such as rectangular uncertainty set (Dong et al. 2022). We demonstrate that in this setting, Subcondition 2 holds for the loss function of the policy player, and Subcondition holds for the loss function of the W-player. Lemma 5.4. Let the objective Sunction be the Value Function. For any posilive noise term 0, we have that under direct parameterization. Σ 44-) - (a, and Σ ha(-) (a.-) are both gradient- dominnted for the
W W-player and the x-player sets W and T with constants Kw= - d"
and K 1
respectively. Therefore, Subcondition 2 hold for both the loss functions for both players.
Algorithm 4: Algorithm under Direct Parameterization
Data: T
for E [2'] do
Sample 0g ~ Exp(n):
Te + 0, [ - -V: (4) (o,, (o,, /* Follow the Perturbed Leader
*/
W. O. (V#) (n)) /* Best-Response
end
Now, we have shown that when the objective function is the loss function, the loss functions for the policy player satisfy Subcondition _ Therefore, we can use Follow the Perturbed Leader for OL" Now, we wish to show Subcondition ! holds for the loss function of the W player.
Lemma 5.5. Under direct parameterization,
have that the Vw is wradient-dominaae with constant as in for an arbitrary W E W and the optimal parameter W W, we have
Kw 1 wwa
Vw (w) - (w)(p)= S -KW min wew
[ -w) VwVWlwu).
9

---

Published in Transactions on Machine Learning Research (06/2024)
Here, we have that Subcondition 4 holds for the W- W-plager.
Now that we have that Subcondition f holds for the W player, we know we can use Best Response for the OLW player. Thus, in the direct paramctcrization sctting with standard Robust MDPs, we can use our framework from Algorithm | with Follow the Perturbed Leader for OL and Best Response for OL where both Projected Gradient Descent as their Approximate Optimization Oracle. We present our algorithm in prove the convergence and robustness of our framework using our proof framework.
Algorithm We
5.4 Overall Convergence Rates
Now, the policy player employs FTPL, and the environment player employs Best- cest-Response, we get the following convergence bound when the objective function is the Value Function.
Theorem 5.1. Assume that the set of possible transition matrices W is conver. Let L be the smoothness constant of he with respect to the & norm, D = max | - T21,, and dx be the dimension of the input
a,
for the r-player. Let OL* use FTPL and OLW use Best- Ress-Resp..se. Under direct parameterization, when 1) = LavTa the robustness of the set of truined algorithmss for any ã
T Σ
T V- (n)
2d D
min EW
VW-
min W.EW
Σ
S
+ or (To, + fow (To,Kw).
VT
We formalize this in Algorithm in expectation is O (T-3 To with simple gradient-dominance assumptions.
4 Here, we have shown that in this simple setting, we have that the robustness
5.5 Comparison to Existing Rates and Algorithms
Our resulting algorithm is similar to that of Wang et al. (022b). Both algorithms iteratively optimize the policy and transition matrix in turns. However, their policy update is a single step of Projected Gradient Descent, and our framework utilized different updates for the policy player. With our framework, our method gets a more powerful convergence rale with less stringent. assumptions. Moreover, Wang Zou (2022) ouly update the policy on each step by using the gradient of the worst-case Value Function. However, their method relies on stringent assumptions on the uncertainty set make the gradient computable. [lement & Kroer (2021) in structure is similar to that of Wang al. (2022b) given that it iteratively updates both the policy and environment by directly optimizing the objective function. Instead,, our method uses different updates, such as OFTPL. Overall, our algorithm differs from existing algorithms by optimizing both the policy and environment and exploring different updates for cach, resulting in better convergence rates with weaker assumptions.
Both our algorithm and Wang & Zou (022) achieve rates of roughly O ( However, they assume the uncertainty set is n-Contamination set. Moreover, Cleient & Kroer [2021 achieves slightly faster rate of O However, their analysis is limited to the tabular setting and relies on the uncertainty set being a Wasserstein ball. To our knowledge, these are the fastest rates in the litcrature that solve Robust MDPs with gradient-based updates. Thus, our work roughly meets or comes near the fastest rales for solving Robust. MDPs while requiring the least stringent assumptions. However, given some additional properties, it may be possible to improve this bound. We will investigate this in the following sections.
6 Faster Rates
Our framework can be applied with only the gradient-dominance property of each player's loss function. However, with different assumptions, the algorithm's convergence rate can be improved by utilizing different properties. The two properties we will investigate are smoothness and strong gradient-dominance.
10

---

Published in Transactions on Machine Learning Research (06/2024)
6.1 Smoothness
As in Agarwal et al. (2019), for the direct paramelerization, we have that the Value Function is smooth with respect to the r-player as in (w) VW (u) O (2 | π 1112))
(1-7)-
Algorithm 5: Algorithm under Smoothness
Data: T
for E [T] do
Sample ~ Exp(n);
Te O, E
-V: (11) (or, mt) -Wii, / Optim. Follow the Perturbed Leader
W. O. Σ (w) - ow), / Follow the Perturbed Leader Plus
end
If our objective function is the value function and we can sufficiently demonstrate that the difference of value functions under different transition dynamics is smooth, we can improve our bounds by exploiting this smoothness. Formally, such smoothness would take the form of Condition 6.1
Condition 6.1. The difference in value functions between subsequent rounds is smooth with respect to policies such that for all s E and policies a and n', we have that
(V) Vir VV (p) VT (+) S L|[W-W[WI
W'lla/ 1'111-
In general, difficult show that such an L is smaller than the value that of the Lipschitz constant of the (1-7)² However, we are in a setting such that L is small, we can take advantage of this by using Optimistic Follow the Perturbed Leader Plus for the т-player where the optimistic function is simply the last loss function ht-1- Condition 6.1 holds, we have that h - h is very smooth, and we can directly improve our rate of convergence. However, from the formulation of Condition 6.1] we also nood choose online strategy for the environment such that IIW - W is bounded, which we can Remonsttate is the case if the W-player uses FTPL+ We summarize these algorithmic choices in Algorithm 5 Tn the direct parameterization setting with the traditional objective function, seen by OFTPL for the policy player and FTPL+ satisfy our gradient-dominanee properties. In the direct parameterization case with traditional objective, these conditions hold as shown in the appendix respectively (see Lemma B.1 and Lemma B.2). Furthermore, in this setting, we have the robustness as such. Indoed, if L is small here, we can improve convergence and robustness of our trained algorithun.
Value Function, 21
also show that the loss functions
Theorem 6.1. Assume that the set of possible transition matrices W convex and we are in the direct parmmeterization setting. Let OL use OFTPL and OT,W use FTPL+. Given that Condition 6. holds, we have that the robustness of the algorithm is for any ß when setting
205 (d, tw td, D,) D L2 dr
T
T
(
50 [ dd
+ dz) (T,,
Dr (1
+1 1 ea (To, (To,
min eW
V (n)
min W EWW
W- (1))
1=
6.2 Strong Gradient-Dominanee
We now explore another extension: strong gradient-dominance. Moreover, in specific paramelerizations, the objective functions for Robust MDPs will obey strong gradient-dominane also known famously as the
Polyak-Lojasiewiez condition (Polyak 1963). This condition helps improve convergence in nonconvex settings,
analogous to the strong convexity condition. We formally state such a property in Condition 6.2
Condition 6.2. A function a(x) satisfies K, 8-strong madienttddmmnnane if for any point E X,
min min)a("") 2 a(x) + min #'E
K((a' - x, Va(x)) + 11 - xx1 Z'E
11

---

Published in Transactions on Machine Learning Research (06/2024)
In general, this is useful for achieving even tighter optimization bounds. Indeed, from Karimi al (2016) if we have this, Projected Gradient Descent enjoys better convergence.
Lemma 6.1. Here, x" arg min at(2") is the minimizer of a. cg is used for brevity. Given is L- Lipishhhttz x
continuous and is K. C.ō-stryngly dominated, we have that using projected gradient descent gets global linear converyence as in
(x(x)) - ar(x*) - ( K2L) (oe(xv) (ait)))(((x")) c² (k))
6.3 Direct Parameterization with Regularization
Say we are in a setting where we want to maximize Vi and ensure that the policy æ regularized according to the lg norm. In this way, we can redefine the loss function to be g(W, π) = V (p) || 12. Again, the sets W and T are bounded convex sets in this setting.
Algorithm 6: Algorithm under Regularization
Data: T
for E [T] do
Sample ~ Exp(n):
Te O. E/=l V. (m) || m)) /* Follow the Perturbed Leader
W. O, VW, (n) | /* Best-Reaponse
end
Lemma 6.2. We have ((, = (w) ||/ Kr,, strongly grudient-dominated on set T
In this setting, if the π player employs FTPL where its Approximate Optimization Oracle enjoys even better convergence and the W-Player employs Best Response, have the robustness bound as follows. We summarize this algorithm in Algorithm Indeed, given strong gradient-dominance, we have that the dependence the complexity for the Optimization Oracle is better for the T-player, slightly improving the robustness bounds.
Theorem 6.2. We are in the direct parmmeterization setting where the objective function is the regularized Value Function. Assume that the set of possible transition matrices W is conver. Let OL use FTPL and OLW use Resposes. Under direct purameterizatinn, given that Condition 0.2 holds and vj L.VTa we have that the robustness of Algorithm 1 is for any π
2d DnLn + c To, 1)) ow (To, me)
min (p) WWWW
||||
min W-EW
Σ
VT
7 Experiments
We now turn to explore how our algorithm finds robust minima empirically. We will use Algorithm A to optimize a policy in the GridWorld MDP (Sutton & Barto 2018). This setting is a traditional MDP where the world a grid where the initial state is one corner the grid. The goal state is the opposite corner of the grid. At each step, the policy can take any of four actions. The next state is sampled respectively from the transition matrix. If the policy lands in the goal state, it receives reward of 10, and the MDP is finished. Otherwise, it receives a reward of -1. We experiment in the setting where the grid is 5 states tall and 5 states widc. We wish to measure how quickly the robustness of policy is improved through cach iteration of our alg. As metric to measure robustness, given a policy, we choose the (ransition matrix that minimizes the expected reward of the initial state and reports the initial state's expected reward. We do this for every itcration of our algorithm. We will do this over different adversarial transition matrix sets. The in question will be
T = (T s.t. IT Tolla S TT.
12

---

Published in Transactions on Machine Learning Research (06/2024)
min V
min Vi(ee
min V (5(1e)
(riM) uitu
Ours DRPG
Ours DRPG
Ours DRPG
Ours
DRPG
(a) 11
(b) 7 2
(c) 7 =1
(d) .5.9
min (564))
min Vi
min Vidlu)
(o2t wiw
DRPG
DRPG
DRPG
DRPG
T
T
(e) = =1
(1) == 22
(g) == =
(h) 7 = 559=2
Figure We plot the convergence of our algorithm over many different transition matrix uncertainty set shapes. We see that over all shapes, our algorithm converges roughly the predicted 1 rate predicted by our results. The convergence curves of DRPG and our algorithms are very similar.
VT
Here, To is some randomly generated initial transition matrix, is a hyperparameter affecting the shape the transition set, and t is the radius of the transition set. We demonstrate robustness improvement over several values of and q. We plot the convergence of our algorithm over q E {1.2] and T E f.1, 33 .5} in Figure I As baseline, we provide the convergence results for Double-Loop Robust Policy Gradient (DRPG) from Wang et al. (202b)). We see in these convergence plots that our algorithm roughly achieves convergence rate of O (T- This is achieved across all uncertainty set shapes and radii. This corroborates the theoretical results of our framework's versatility and efficiency in different environmental settings. When comparing our results the bascline, we see that our method and DRPG achieve similar convergence curves. Overall, these results suggest that, empirically, this algorithm performs competitively with existing algorithms and slightly.
7.1 Implementation of the Practical Algorithm
We have provided a GitHub repository to reproduce our experiments. We use the OpenAI Gym environment. to set up our experiments. For all optimization tasks, we utilitize the constrained optimization libraries in SciPy. Morcover, implementing projected gradient descent unfortunately requires manually designing the gradient calculation depending on the problem setting.
8 Discussion and Limitations
In this paper, we developed a nonconvex No-Regret framework that has decoupled the convergence for Robust MDP algorithms. Based on the proposed framework, we designed different Robust MDP algorithms under standard gradienl-dominancee strong gradient-dominance, and smooth MDPs. The proven convergence results are of the strongest in the literature, with only convexity assumption the set of possible transition matrices. Possible extensions include using this nonconvex No-Regret Framework for other nonconvex problems, such as other nonconvex games, exploring how different minimization oracles could empirically improve the performance of our algorithmo hms. Another possible avenue could be studying Robust. MDPs where the optimization objective obeys the strict saddle property.
Limitations However, our work has several limitations. Firstly, we require some gradient-dominann conditions for the policy and environmental dynamics player. In many settings, the objective function for the Robust MDP does not satisfy this. This assumption does reduce the scope of our work. Moreover, many of our convergence guarantees only made in expectation, while many other bounds in the literature are
13

---

Published in Transactions on Machine Learning Research (06/2024)
made absolutely. Moreover, do not generate single policy that achieves strong robustness but, instead, series of policies that, if used together, obey our convergence guarantees.
References
Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. CoRR, 0bss/190..0025 2019. URL http:
Kishan Panaganti Badrinath and Dileep Kalathil. Robust reinforcement learning using least squares policy iter- ation with provable performance guarantees. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 511-520. PMLR, 18-24 Jul 2021. URL https:: attpps:/prroceedings. mlr, http::/poocceuuggs......eesss/as hatmlla..mmmmmmm html
Andrew Bagnell, Andrew Ng, and Jeff G Schneider. Solving uncertain markov decision processes.
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The mechanics of n-player differentiable games. In International Conference on Machine Learning, pp. 354-363.
PMLR, 2018.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods, 2022.
Peter Buchholz and Dimitri Scheftelowitsch. Light robustness in the optimization of markov decision processes
with uncertain parameters. Computers & Operations Research, 108:69-80 81, 2019.
Zhi Chen, Penggian Yu, and William B Haskell. Distributionally robust optimization for sequential decision- making. Optimization, 68(12) 2426, 2019.
Jason J. Choi, Donggum Lee, Koushil Sreenath, Claire J. Tomlin, and Sylvia L. Herbert. Robust control barrier-value functions for safety-critical control, 2021.
Julien Grand Clement and Christian Kroer. First-order methods for wasserstein distributionally robust mdp. In International Conference on Machine Learning, pp. 2010 2019. PMLR, 2021.
Karl Cobbe, Oleg Klimov, Christopher Hesse, Taehoon Kim, and John Schulman. Quantifying generalization in reinforcement learning. CoRR, abs/1812.02341, 2018. URL http:://axii..o// www. axgg/bbs/812..00 02341
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism.
arXiv preprial ar arXic:17/1.00144 2017.
Jing Dong, Jingwei Li, Baoxiang Wang, and Jingzhao Zhang. Online policy optimization for robust mdp. Xix preprinl arXiv:2200.3388 13841, 2022.
Benjamin Eysenbach and Sergey Levine. Maximum entropy rl (provably) solves some robust problems. arXiv preprint (xXf::213300255 2021.
Jesse Farebrother, Marlos C. Machado, and Michael Bowling, Generalization and regularization in DQN. 00123
CoRR, abs/1810.00012 2018. URL
Mohammad Ghavamzadeh, Marek Petrik, and Yinlam Chow. Safe policy improvement by minimizing robust baseline regret. Advances in Neural Information Processing Systems, 29, 2016.
Vincet Goyal and Julien Grand-Clement. Robust markov docision processes: Beyond rectangularity. Mathe- matics of Operations Research, 48(1):203 226, 2023.
Garud N Iyengar. Robust dynamic programming, Mathematics of Operations Research, 30(2):257 280, 2005.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, ICML '02, pp. 267-274, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc. ISBN 1558608737.
14

---

Published in Transactions on Machine Learning Research (06/2024)
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Hamed Karimi, Julie Nutimi, and Mark Schmidt. Linear convergence gradient and proximal-gradient methods under the polyak-lojasiewicr condition. CoRR, abs/1608. 04008, 2016. URL http://arxiv..rrg
abs/1608. 04636
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
Elita A. Lobo, Mohammad Ghavamzzaehh and Marek Petrik. Soft-robust algorithms for handling model misspecification. ColRR, abs/2011.144933 2020. URL
14495
Daniel J. Mankowitz, Timothy A. Mann, Picrro-Luc Bacon, Doina Procup, and Shic Mannor. Learning robust options. CoRR, abs/1882.03223,, 2018. URL http:///aaxxxx..rggaaa///112222
Daniel J. Mankowitz, Nir Levine, Rae Jeong, Abbas Abdolmaleki, Jost Tobias Springenbery, Timothy A. Mann, Todd Hester, and Martin A. Riedmiller. Robust reinforcement learning for continuous control with model misspocification. CoRR, abs/1906.07516 2019. URL
Brendan McMahan and Jacob Abernethy. Minimax optimal algorithms for unconstrained linear optimization. Advances in Newral Information Processing Systems, 26, 2013.
Arnab Nilim and Laurent Ghaoui. Robustness in markov decision problems with uncertain transition matrices. In S. Thrun, L. Saul, and B. Schölkopf (eds.), Advances in Newral Information Processing Systems, volume 16. MIT Press, 2003. URL
Charles Packer, Katelyn Gao, Jernej Kos, Philipp Krähenbühhl, Vladlen Koltun, and Dawn Song. Assessing generalization deep reinforcement learning. CoRR, abs/1810. 12282, 2018. URL httpspppprrrllsppppppeepeeepp abs/1810. 12282
Anay Pattanaik, Zhenyi Tang, Shuijing Liu, Gautham Bommannan, and Girish Chowdhary. Robust deep reinforcement learning with adversarial attacks. arXiv preprint 1rX603171,.0333,, 2017.
Marek Petrik. Approximate dynamic programming by minimizing distributionally robust bounds. arXiv preprint ar Xiv::12205. 182, 2012.
B.T. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics, 3(4):864 878, 1963. ISSN 0041-5553. doi: 90382-3. URL https::/ wwwww/wwwwwww/.o/ http://wwwwoeeeeeccccoooooaaaaaa
Roberta Railcamu and Rob Fergus. Decoupling value and policy for generalization in reinforcement learning. CoRR, abs/2102.10330, 2021. URL http://wwwwaaooooooooooooo/ooosa
Aurko Roy, Huan Xu, and Sebastian Pokutta. Reinforcement learning under model mismatch. Advonces in neural information processing systems, 30, 2017.
Andrzej Ruszczyáski. Risk-averse dynamic programming for markov decision processes. Mathematical programming, 125:235 261, 2010.
Alexander Shapiro. Rectangular sets of probability measures. Operations Research, 64(2):528 541, 2016.
Saumya Sinha and Archis Ghate. Policy iteration for robust nonstationary markov decision processes. Optimization Letters, 10:1613-1628, 2016.
Xingyou Song, Yiding Jiang, Stephen Tu, Yilun Du, and Behnam Neyshabur. Observational overfitting in reinforcement learning. CoRR, abs/ Abs/1912.009975, 2019. URL http:://arr....oggg//////2.2...0
Krishnan Srinivasan, Benjamin Eysenbach, Schoon Ha, Jie Tan, and Chelsea Finn. Learning to be safe: Deep RL with safety critic. CoRR, Ads/2000.1400,, 2020. URL btttas//aaxiv.orr/aa////1..111
15

---

Published in Transactions on Machine Learning Research (06/2024)
Lauren N Steimle, David L Kaufman, and Brian T Denton. Multi-model markov decision processes. IISE Transactions, 53(10))1124-1333 1139, 2021.
Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. CoRR, abs/1903.08110, 2019. URL /tt.tttt.//arrr...og//////////. 08100
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. URL http://iincompeeeeieea. wwt.seet//ebbbbbbobeeooooo bho--toe------ooeeeeeoooooooteee 2nd. html
Richard S Sutton, David McAllesterr Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning in games, 2015.
Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust mdps using function approximation. In International conference on machine learning, pp. 181-189. PMLR, 2014.
Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and applications in continuous control. In International Conference on Machine Learning, pp. 6215 6224. PMLR, 2019.
Guanghui Wang, Rafael Hanashiro, Etash Guha, and Jacob Abernethy. On accelerated perceptrons and beyond. arXiv preprint arXiv:2210.00877. 2022a.
Jun-Kun Wang, Jacob D. Abernethy, and Kfir Y. Levy. No-regret dynamics in the fenchel game: A unified framework for algorithmic convex optimization. CoRR, abs/2111.11309, 2021. URL https: 11309
Qiuhao Wang, Chin Pang Ho, and Marek Petrik. On the convergence of policy gradient in robust mdps. ar preprint 21X::22122.1439, 2022b.
Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty. Advonces in Neural Information Processing Systems, 34:7193-720 2021.
Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. In International Conference on Machine Learning, pp. 23484-23526. PMLR, 2022.
Yue Wang, Alvaro Velasquez, George Atia, Ashley Benter-Bennette, and Shaofeng Zou. Robust avcrage-reward markov decision processes. arXiv preprint vrXiw:2301.00855 2023.
Wolfram Wicsemann, Daniel Kuhn, and Berç Rustem. Robust markov decision processes. Mathematics of Operations Research, 38(1):153 183, 2013.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning, Machine learning, 8:229-256 256, 1992.
Huan Xu and Shie Mannor. Parametric regret in uncertain markov decision processes. In Proceedings of the 48h IEFE Conference Decision and Control (CDC) held jointly with 2009 28th Chvness Control Conference, pp. 3606 3613. IEEE, 2009.
Huan Xu and Shie Mannor. Distributionally robust markov decision processes. Advances Neural Information Processing Systems, 23, 2010.
Huan Zhang, Hongge Chen, Duane S. Boning, and Cho-Jui Hsieh. Robust reinforcement learning on state observations with learned optimal adversary. CoRR, abs/2101 Abs/2001008452, 2021. URL https://arxiv.cm 0////2111.084555
16

---

Published in Transactions on Machine Learning Research (06/2024)
Symbol
Meaning
Discount Factor
S
Set of Actions
Pw
Transition Matrix parameterized by W
R
Reward Function
Parameter for Environment
Rmax
Maximumn Reward
0
Parameter for the policy
T
Set of Policy Parameters
To.
Policy
Distribution over starting states Value Function
Vi
dw d5,
Occupancy Measure of state Objective function of Robust MDP
4
Loss Function for Environmental Player
hu
Loss Function for Policy Player Regret Of Environment Player Regret Of Policy Player
Regw
Regæ
Oa
Optimization Oracle Noise Vector for Online Algorithms Parameter for the Noise Distribution
a
KC,
Gradient Dominance Constant for W and Number of Iterations for Optimization Oracle Suboptimality of Projected Gradient Descent Lipschitz Smoothness Constant of he Radius of Set of Policies Dimension of 0 Suboptimality of Projected Gradient Descent for Environment Player Suboplimality of Projected Gradient Descent for Policy Player Lipschitz Constant of Difference of Objective Functions Constant for Strong Gradient Dominance Suboptimality of Projected Gradient Descent under Strong Gradient Dominance
To
(T(T,,
L
Dx
dx
ow (To.Kw)
ex (To,Kx)
T.
(To,K)
Table 1: Table of Notation
A Proof of Preliminary Theorems
A.1 Proof of Theorem
Theorem 4.1. We have the difference between the robustnesses of the chosen policies and any policy is upper bounded by the regret of the two players
Σ (W"
Σ g(" m)) < Regw + Reg.
min T EWW
min
T TW
t=0
Here, Regw and Reg, are the two average regrets of the two players OT. and OIF.
17

---

Published in Transactions on Machine Learning Research (06/2024)
Proof. By definition, the regret of the W W-player is equivalent to
T
Regw
min 4(W)
4(W")
W
-
t=0
g(W,, me) min
Σ
g(W", mT)
1=
t=0
Similarly, for the π player, we have that
T ( min Σ ((TT)
Reg
T
max x²
gW,, x²) Σ g(W,, m1)
(1)
Therefore, upper bound the sum of objective functions throughout training process
T
9(,, m.) Regw + min Σ
9( m.).
W
A=
t=
We similarly lower bound the sum of value functions throughout our training process as
o(W, 1, m2)
9 (W,, x²) Reg,
T
g (W,, 7) Reg,
T
2 min W
g( σ) - Reg,
(2)
Combining Equation and Equation
2 we have our desired statement
min
g W T)
min W
gWV* me) S Regw + Rega
B Proofs of Gradient Dominance
B.1 Proof of Lemma 5.2
Lemma 5.2. The gradient of the value function V with respect to the parameter W, denoted as V VW (8),
is given by
VWVW (s) 1-
Σ d s) (8').
18

---

Published in Transactions on Machine Learning Research (06/2024)
Proof. We wish to calculate the gradient of the value function VW with respect to (w a, a)s. We have that
VwV = Vw
Σ T( (1
Σ [((
VVla,s)Vw a(s,a) + 77 [Pw(s,a,))
(3)
En 8)
= Σ (T(a, (Pllss))W.ss... + I=(as)/W/(ssssa)
Here, the Equation
3 comes from the definition of the Q function. Unrolling this makes it such that we have
VwVW(W)
Σ
Pr(s: = ma,) (V) ()
t= 8',
o () (s')
We have now arrived at our desired quantity.
B.2 Proof of Lemma 5.3
Lemma 5.3. Given two different transition dynamics parameters W and W', we have that
Vw(p) (W) = Σ d (s) a, s)T(a, s)AW (s'
s',0,
Here, define the W W-Advantage Function AW ( = (V)() - Vw(
Proof. This proof follows mainly from the proof of the Performance Difference Lemma from Kakade & Langford 2002).
(w - Vwr(u) - =E
y r ar) wW (4)
1r((8, 0z) + (VV of vwr(()) - vw (1)
=Epw v3
= -E m
1r(8,, az) - (Vv - - ((Vrr((s))
= EE m
A W (s141, Gr.
(s' (d' ( S)A" (s' a)
(4)
Here, Equation proof.
4 comes from our definition of the Advantage function for the W -lplayer. This concludes the
19

---

Published in Transactions on Machine Learning Research (06/2024)
B.3 Proof of Lemma 5.5
Lemma 5.5. Under direct paramelerization, we have that the Vw(p) is gradient-dominalee with consland
Kw
as in for an arbitrary W E W and the optimal parameter W E W, we have
1-7
Vw (w) VW-(u) -Kw min Wew (w- VWVVi(H))
Here, we have that Subcondition 4 holds for the W -plaaer.
Proof. We can use Lemma 5.3 to prove this. We will lower bound the difference between the optimal Vw- and the Vw((), . In order to prove Gradient Dominance, we need that Vw(u) - Vw (4) to be upper-bounded. We will equivalently lower bound the negative of this. We have
(w) - Vw- (1)
-1
Σ
y dW" (s))(a, 8)P (8'1a, A)A a,
1-
8' 8'00,
Σ
hh'd (s)T(a, s)min (AW (s', a, s]]
(5)
WWa' (s)
Σ ,',
Σ (h' (s) s) min (A" (s', a, s)s)
max
W
Here, the Equation comes from seeing that the value Pw- Fs-(s''a, A (s', a, s) is minimized when Pw- puts the most weight on the state minimizing the advantage function. Looking only at that last term, we can bound it in the following manner
-1
Σ 7
(da (s)t(a,s) s) min (A" (s', (s',a,s)) a,s)
min
Σ (dd (s)=(a,)) (WH (d',,,)))
(6)
W
-1
min W
b'' (s)=(a,s) (s Pw s)) (A (s',a, s))]
(7)
1
st,a,
min W
b'd (s)=(a,s) (P a, Pw a. 5)) (Vw (s'))
(8)
s',a,
-inn
[w (W-W) Vw.Vw(()) W
(9)
Here, Equation 6 comes from secing that the value Pw- (s'la, s)AW (s',a, a. is minimized when Pw- puts the most weight on the state minimizing the advantage function. Equation 7 comes from the fact that the Σg (s'(('s a, s)4 (s,,a,)) = Equation (8) comes from the definition of the W-p W-player advantage function.
Finally, Equation comees from Lemma 5.2 Combining these yield
dy min W
(W w) T Vw Vw.Vw((H)
Vi(() Vw- (H) s
dW
dW
[ ww) Vw..ww()) min W
(10)
Equation 10 comes from the fact that dW" (s) (1 (s)ss)) by definition. Here, flipping this, we have W
Vw( Vw- (H) 5 1-7
min [W w) Vw..vw(w))
w
This is satisfying definition of gradient dominance.
20

---

Published in Transactions on Machine Learning Research (06/2024)
B.4 Proof of Lemma 5.4
Lemma 5.4. Let the objective function be the Value Function. For any positive noise term o, we have that dominated for the
under direct parameterization, Σ: [.(+) - (a,-) and Σ.- ha(:) (a.-) are both gradient- grudient-dominated
W W-player and the x-player on sets W and T with constants Kw = dw
d
and K 1-7
respectively. Therefore, Subcondition hold for both the loss functions for both players.
Proof. We can use Lemin 5.3 to prove both. We start with the W player.
W (1)
w (1) (o, W W*)
Σ
8) (8' - (0, W W
(11)
,0,0,3
dW (s)
Σ
[dw (s)ma(a(ss) Pw- (s'la, (A (s'a,))))
max
W (s)
s'
(o, W - W.))
-W-)
W (8)
max 1
min Σ Σ
d (s)m(al)))P (A
(6' (d,
(12)
W (8)
e',a
- (a, W - w)
Here, Equation comes from the fact that the maximum of the interior of the RHS is always nonnegative, and Equation 12 comes from using the minimizing transition dynamics W. Looking at the inside term, we have that.
(aw (s)ms(als) Pw(s',,s)) (4 (s',a,))) - (o, lo, w)
min
80,0
min W
(s) (Pw-ss', a (w (A (A" (s'
(13)
Y aa,
-a, W w)
min W
Σ Σ
dd (s)s) (Pw(s Pw(s',a,s) (Vw(s'))
(14)
s',a,a
- (a, - (wy-ww)
min (W (W- (W) Vw
Σ Ve (n) - (o, W)
(15)
Equation 13 comes from the fact that the Eg (s', a. s) (s', a, 0. Equation comes from the definition of the W-player advantage function. Finally, comes from Lemma 5.2 Combining these, we have
21

---

Published in Transactions on Machine Learning Research (06/2024)
that
V (1) -V:. (o, W W0)
1
min
(W w) Vw
Σ W (1) - (o,
y W
Moreover, we use the fact that d (+) 2 (1 - (>) by definition. We now do this for the 7-player. By the Performance Difference Lemma,
W. VW; -Y,, π x²)
Σ
di (s)
x x*)
(16)
min
di (3)
(0, -0)
7
min
((s))(s.a)44(ss.) -0,, - x))
min
([))(((ss.)) T(a, (s) - (0,, - RT)
(17)
d
t-1
min
# (s) -(aa - a
(18)
d5
8.0
dxa
min(#
x) V TV,
Σ VW: (0,
(19)
Here, Equation 16 comes from the Performance Difference Lemma, Equation 17 comes from the fact that I
O, Equation (18) comes from the definition of the Advantage Function for the т-player, and Equation 19 comes from the both the Policy Gradient Theorem and the fact that ds)(s) 2 (1 - ())(s)
AF a))
We now have proven both claims of our lemma.
Lemma B.1, The T-player enjoys Subcondition S i.e. E.-1 h2(-)) + 1--(()) - a is gradient- dominated with
d=
constant 1-
Proof. For simplicity, we will call h,²
hy()) + h-1(--) where j indexes over the set (m,,..., -h.....--2... h4-1, 1. With this, we can follow through with our proof. By the performance difference
Ex-hh(()
22

---

Published in Transactions on Machine Learning Research (06/2024)
lemma,
Σ W: W: - (0, π - n²)
(a))
(20)
ΣΣ (0)) -0,
min
5,8
d
(10 (0, -
d
00
4
min
(T))((((s,)) - ((,,)))A"(ssdl - (0, т - T)
(21)
d
min
ΣΣ (T) a)
(a. - T))
(22)
d=
min(T x) V Σ -W TT,
(23)
Here, Equation 20
comes from the Performance Difference Lemma, Equation 21 comes from the fact that
Ea s) (s, (,aa) a 0, Equation (22 comes from the definition of the Advantage Function for the т --player,
and Equation
23 comes from the both the Policy Gradient Theorem and the fact that di (8) 2 (1-7)u(s).
Lemma B.2. Subcondition is salisfied for the W -player, i.e. E.4 a is gradient dominated.
Proof. We can use Lemma 5.3 to prove both. We start with the W player.
Vw (v)- (w) (o, W W")
プー 1-
Σ
Σ
(0, W (W--)
(s)
Σ プニ
Σ
[d (s)m.(al)))
Pw- (w- (A (s',a,)))
d: (s)
s',a,s
(o, W way
W (8)
min
Σ
Σ
d"' (s) (A (s', (A (s',a,))) s))]
(24)
dW (s)
W
1
(0, W- w)
23

---

Published in Transactions on Machine Learning Research (06/2024)
Here, Equation we have that
24
comes from using the minimizing transition dynamics W. Looking the inside term,
Σ
d (s)t((als)
Pw((', (A (s', (.))) W w)
min
,,,,
min W
Σ Σl
d (s)ms(als) (Pwi''',,,)) aw (A (5' a, s)s)
(25)
?
.a,
(o, W w)
min W
Σ
Σ
d (s)ms(als) (Pw a, s) - Ps
a, a)) (Vw
(26)
(0, W W)
min W
(w (W-w) w) Vw
(v (o,
(27)
Equation definition the W W-player advantage function. Finally, Equation (27 comes from Lemma 5.2 these, we have that
25 comes from the fact that the Eg (s', s)A a).s) = 0. Equation 126
comes from the
Combining
Σ (w)) (4) -V) (a, W- W S
-1
min
( w) Vw
Σ V (n) (a, w)
7 /
W
Moreover, we use the fact that d (8) 2 (1
r)p(s) by definition.
C Proofs for Convergence
Here, we detail lemma on the convergence FTPL and OFTPL as proven in Suggala & Netrapalli (2019) Lemma C.1. Let D be the lox diameler of the space X. Suppose the losses encountered by the learner are L-Lipschitz w.r.t & norm. Moreover, suppose the optimization oracle used has error a. For any fized the predictions of Follow the Perturbed Leader satisfy the following regret bound. Here, d is the dimension of the noise vector.
E
T Σ fe(x,)
-
1 inf Timt E s so (n
T
dD
+ +a )
nT
For OFTPL, suppose our guess gt such that 9t - fc is L,- Lipischhhitz w.r.t & norm, for all t E [T]. The predictions of Optimistic Follow the Perturbed Leader satisfy the following regret bound.
1 inf Σ f((x) 1=1
L3
dD
E
Σ
flxx))
50
bdl D
+
T
TzEK
T
n
t=1
C.1 Proof of Lemma 4.1
Lemma 4.1. Suppose have incoming sequence of loss functions f. for t E [T] with optimization orucle that can ménimize function to less than ervor. The Best Response algorithm satisfies the following regret bound
T
T {(t) TEX t=1
fe(x))
inf T
T
24

---

Published in Transactions on Machine Learning Research (06/2024)
Proof. The regret term is defined $ f( inf Et= f((x) where 2, the choices taken by the BestResponse algorithm. For arbitrary time step t, we have that
f((x)) ft(a)= + fe(x)
(28)
S a
where Equation (28) comes from the fact that an optimization oracle is used to calculate Iy and has error upper bounded by a. Therefore, we have that
T
T aa
Σ f((x))
inf T Texx t=1
Σ f(())
T
Proofs for Extension Section
D.1 Proof of Lemma D.1
Lemma D.1. Given series of choices by FTPL+ 31:-..,37 ør with smooth and gradient dominated loss
functions fi...., ft and noise sampled Exp(n), the stability in choices is bounded in ezpectation by
B([|=++1 zxlli) < 125nLd a
20L
To prove this, we will first prove two properties of monolonicity of the loss function on inpul of noise Much of this proof structure is inspired by (Sugaala & Netrapallij (2019).
Lemma D.2. Let xz( be the solution chosen by FTPL+ under noise sigma. Let = o + ces for some positive constant e, then we have that
xe,((o)) 2 01,(0) 2a
Proof. Given that the approximate optimality of (0), we have that
Σ f((x((o)) + mi(z((o)) (o, x()))
(29)
f((a(o')) - xo,)x(d')) ta
(30)
(())((o))) ((l,(oo))+m(((l) + x((') + (o' -a,x((0))) +
[((x(()) + + xx(()) + (o' - o, + 20x
(31)
+ + - (a, (0)) + (0' - a.z)(0') x((0a) + 2a
(32)
comes from the fact that 2x( is approximate minimizer for the loss function, and Equation 33 comes from the fact that z. (o))) minimizes the loss function with noise set to o' by definition.
Here, Equation 30
Combining Equation (29) and Equation 32 we have that
0 5 (o' a,zi(o') - Iz(la) + 2a
+ 2a
We, therefore, get that (00)) 2 (0)
20
25

---

Published in Transactions on Machine Learning Research (06/2024)
Morcover, have that the difference between predictions made by our algorithm at sequential timesteps is close.
Lemma D.3. If [2)(()) (c-1(1)]11 [0d] 2141,(00) and o' 100Lde; o, have that
1 fe,i(0) - x2+1.i(0')l
3a
min
10
100Ld
Proof. We have that
E (o, + f((x(()) + m441(11(o))
- (o, (0, - + f((x+1(0)) + ( + ta
(33)
[((+1100 - (0, f1( + ((+1(((2(0)))
(34)
L[ zr(0))l1 (c)))= +
Here, have Equation (33 from the approximate optimality of u4(() and Equation of the optimistic function. Moreover, from the opposite direction, we have that
34 from the smoothness
Σ f((x(()) xo,) + f((z(()) m
Σ [(xx(o)) (0' a(()) (0' a, + M((x(()) + me+1(1)(())
Σ f(x((o))) - (d' 2141(000)) (0' o, (,)) + f(((4)(00))
(35)
+ m1+1 - a
Σ M((x((o)) - (a, (0,0x+1(00)) + (d' o,I;(o) - 2(41(0')) + f(((41((0))
(m=1 -
[(xx(()) (a, (.)1)) (0' a, - 2141(0')) + (((112(0))
(36)
+ + 2a
Here, Equation 335 from the approximate optimality of ze(a') and Equation 36 from the approximate optimality of (0) From these and our original assumption, we have that,
101d| x + 100Td(ss,(()) x141,((0)) 2a.
Using similar argument, we have that
10Ld| x1, + 100Ld(241,(0)) xr,( 2a.
Morcover, from Lemma D.2 know that x0)1;(00) 0141,(0) 2 100ld and 21,(0') x1,((0) 2 100Ld' Combining these, we have our claim.
We can now finally prove our claim. This proof is very similar to the proof of Theorem 1 Suggala & Netrapalli (2019).
26

---

Published in Transactions on Machine Learning Research (06/2024)
Proof. We note that can decompose the l norm in E [o)x((0) -x++1(0)ll1 as
E [l|x((o) - xx+1(0))l)]=
Σ B ( - xx+1,(()))
To bound E (o) - [ derive an upper bound for each dimension [(x,)(0)= x(+1,(0)]] wi [d]. For any i E [d], define E_ (xx))(()) - 1,)1]( as
E- [xx,(o)) x++1,(0)]] TE [xx,(0) - x [0))
where o, is the jth coordinate o. Intuitively, we are computing in expectation of the noise of a single dimension while holding the other dimensions' noise constant. Let (o) max (x,,1()),x xx)),((o) and (o) min (x), x(t,(())) Then, by definition, have that
E_ (xx),(0) X++1,(00]]] = E_ [Xmax, (()] - EE [xmin,
Define event & as
= to: [|x+(o) - x S 10d (x,,(o)) x
For notational ease, let 1app--10nLLL be constant. Consider the following
E_; (Xmin;(o)) =Ip(a < 100Ld) R-i (m)n, as < 1000dd]
+ + 100Ld) E_i (Xmin.(o) lo 2 1000d
2 (1 P) (E=: Xmax, (0)] D)
(37)
PEL; X (ar 100Lde;)
(38)
where Equation 37 follows from the fact that the domain of 5th coordinate lies within some interval of length D and since E (m)n,(()) a, < 100Ld and E_ ((r] are points in this interval, their difference is bounded by D. We can further lower bound E_; (()) as follows
E ( 2(1 11--P -P) (E_ (xmax, D)
+ PP (E),(E)B_: [Xmin, (a + 100Lde;) E]
+ PP-s (Ea) EE [mmin (a + 100Lde;) [*]
where (-)(E) is defined as P-((E)= = P ( {o,))zz) We now use the monotonicity properties proved Lemma D.2 and Lemnma D.3 further lower bound E_, (xmin,()))] Then
E_j (Xmin, (o)) 2(1 P) (E_ (xmax, - D)
(39)
3a
+ PI (E)BB
Xmax.: (o)
(x) - xx+1+(0))
10
100Ld
2a g
+ PPP (89) E-
Xmin.i(o)
100Ld
2(1 P) (E_, [Xmax (0)] -D)
(40)
3a
+ (P)_
Xmax. (0)
10 (x) xx)1)(0))
3
100Ld
1
2a
+ PPP, (89) E_; Xmax,ilo)
|x)(()
X++1(o)11
g
10d
1000d
where Equation 339 follows from Lemma D.2 and Lemma D.3. Equation
40
follows from the definition of
Eº. Rearranging the terms in the RHS and using P_,(E) gives
27

---

Published in Transactions on Machine Learning Research (06/2024)
E- [-i(xmin,:()) 2(1- - P) (B-s Xmax, x - DD
3a
+ PE
Xmax, (0) 100Ld
PE
10 (xe,(o)= xx+11 + 10d
[xx(a) xxm1
3a
ZE_, [max, (o)) 100gLdD 100ld
(41)
-_
10 xx,i(o) x++1,(()]
(xx(() - x
10d
where Equation uses the the fact that exp(x) 2 1 z. Rearranging the terms in the last inequality gives
E-1 (0)))(0)) xx+1, - E-,
B (o) - x++1(=)]l]]+ nLDD +
1000
E_
(42)
9d
30Ld
Since Equation
42
holds for any {og) we get the following bound on the unconditioned expectation
1 S 9d
1000
E[a]
[[)),(()) X (o))l
[||x((0) x+1(())ll)++ LdD
(43)
30Ld
Substituting Equation
43
with the above yields the following bound the stability of predictions of FTPL+
E [[]x((0) - (++1()))l) 125m 20T
Utilizing Appendix D.I gives us the required bound on regret.
D.2 Proofs for Strong Gradient Dominance
We will first prove what the gradient of the value function is with respect to in this setting.
Lemma 6.2. We have gW, VW (n)) ||= is Kr, strongly gradient--ominnaeel on set T
28

---

Published in Transactions on Machine Learning Research (06/2024)
Proof. By the Performance Difference Lemma,
Σ WW.
W.,
(0, x - n²) + | |
th (a, (0, - --) || 11 1|=
(44)
7
min
ΣΣ
(1)(6))) -a,, - - - + ||
8
d
min
1 (() (0, | + |
d
8,0
d
min
(T))((((.)) T(a.5))A"(s.0) (0, m)
(45)
d=
|| + ||
d
Σ ΣΣ
min
(())((()))) - T(a, - (a, π x)
(46)
dr
|| || 12
d
14
min
1 ΣΣ (T)((((s,a)) (s))s)) - (a, t x)
(47)
dr
(2T,, T) 지| T12
(- Σ Va -a, T| 1
T - 1112
min
( T) VV
(48)
1
Here, Equation
44
comes from the Performance Difference Lemma, Equation 45 comes from the fact that 0, Equation (46) comes from the definition of the Advantage Function for the r-player,
())
and Equation 48 comes from the both the Policy Gradient Theorem and the fact that d[[(s) 2 (1 - (s). Morcover, Equation
47
comes from the following logic
|| +
+
- π 2n
[|| || + 2(T - -5, =- =-1|=11 + + 2( -,, T)
From this, we have that the value function done in this manner is strongly gradient dominated with constant T. 2.
D.3 Proof of Theorem 5.1
Theorem 5.1. Assume that the set of possible transition matrices W is conver. Let T,z be the smoothness constant of h with respect to the & norm, D max || n' 122 and dx be the dimension of the input
म..'
for the r-player. Let OI use FTPL and OT. use Best Rest-Ress..se Under direct parameterization, when
29

---

Published in Transactions on Machine Learning Research (06/2024)
1) = L LaVTd the robustness of the set of trained algorithms is for any N
T Σ
T (1))
2d DxL
min W-EW
Vw (10) - R
min W.EW
W
S
+ (To, + KTo,
VT
t=
t=
Proof. From Theorem 4.1 we have that
min W
Σ
W.
(14)
min W
V (1)) - Regw + Regx
t=0
1=0
When the 7-plaaer is using FTPL, its regret. is bounded according to
dz
E (Reg I
nd
D
L +
+ a
1/f
Setting 17 La VTd
minimize this, we have
2d D La
E(Reg S O
+a
VT
Moreover, a is the Oracle Error lerm. Therefore, given that have gradient dominance, using Projected Gradient Descent yields from Lemma 5.1
E(Rg S 2d D cr (a).
VT
Given the W-player employs Best-Response, we have that the regret of the W-player is bounded by the following by Lemma 4.1
B(Regw) S
where is the optimization error. Given that have gradient dominance properties for the W W-player well, we have that using the Projected Gradient Descent for
B(Regw) S ew (To,Kw).
Adding these two inequalities together gets our final result.
D.4 Proof of Theorem 6.1
Theorem 6.1. Assume that the set of possible transition matrices W is convex and we are in the direct paramelerization selling. Let OL use OFTPL and OLW use FTPL+. Given that Condilion 6. holds, have that the robustness of the algorithm for any when setting 17 201 (d. Dw 4d, D.)² DzLLaT, (
de
T
T
so( dd Dz (dhn (1
Drr + d
min - W.EW
(n)-E
min W'EW
Vw (14)
+ c C Kz) (To:Kw)
To,
1=0
1=0
Proof. From Thcorem
we have that
min W
v
(p)
min W
VRL (n) S Regw + Reg.
1=
1=0
Given the T-player employs OFTPL, have from Lemma
C.I that the regret is upper bounded by
Reg, 0o Ind Dr
Σ
T
22
d Dx
+ a
T
nT
30

---

Published in Transactions on Machine Learning Research (06/2024)
However, have that
E(LE) = L'I Wo-1lli
- i? 1255LL + a
20Lx
Here, the last inequality comes from the fact that the W-player uses FTPL+, and the decisions made by FTPL+ are stable from Lemma D.1 Using this above, we have that
Dr n7
Reg, <
1id D 1
12 Dr + 20T
+
+
Since our r-player enjoys gradient dominance for its loss function, we have from Lemma 5.1
that
S Gn (To, Kx).
Morcover, given the W-player is employing FTPL+, from Lemma bounded by
4.2
we have that regret of the W W-player is
dw Dw T/f
Regw 5o
+
In this setting, the W-player still enjoys gradient dominance properties, so using Projected Gradient Descent has
S cw
Adding these together yields
dw Dw dr Dr
Reg. + Regw S Ond 1. Dx + 20I
+
1/T
C (T), + ew (To, Kw)).
/ 20L (ow (dw +dx D LTTa, we have that
Setting
d,
Reg, + Regw 0o
/ Dr + dd),) Te, (To, K₂)
cr (T) ow (wo,
+1
D.5 Proof for Theorem 6.2
Theorem 6.2. We are in the direct parumelerization selling where the objective funclion is the regularized Value Function. Assume that the set of possible transition matrices W is conver. Let OL use FTPL and OLW use Rest-Response. Under direct parameterization, given that Condition 6.2 holds and rj L.VTU," we have that the robustness of Algoritham is for any π
2d Len
+ + (o, 2)) oo (To,T,
min Σ VVW-(w) (p) |||| WOEW
min w N'W
Σ V.. (x)0 T
VT
Proof. From Theorem
we have that
min W'
Σ va (m) (14
min W.
Σ
s (n) < Regw + Reg.
When the π- r-player is using FTPL, its regret is bounded according to
dr TT
E (Reg S
1d D2 1.2 +
+ 0
31

---

Published in Transactions on Machine Learning Research (06/2024)
Setting 17 1
LvTa to minimize this, we have
2d DuLT +a)
[[Reg 50
VT
Moreover, is the Oracle Error term Therefore, given that we have strong gradient dominance, using Projected Gradient Descent yields from Lemma 6.1
( D
2d D tct Ko.k
E(Reg,) ) S 5o
Given the W-player employs Best-Response, we have that the regret of the W W-player is bounded by the following by Lemma
B(Regw) S a
where a the optimization error. Given that we have gradient dominance propertics for the W- player as well, we have that using the Projected Gradient Descent for
B(Regw) S ew (To, Kw).
Adding these two inequalities together gets our final result.
32


Reviews:
[{"review_id": "jTb6aBJ3Zz", "reviewer": "Reviewer_BhiD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1.\tThe studied problem, designing an algorithm that can find environmentally robust policies and handle different model parameterizations, is an interesting and important to the MDP literature.\n2.\tThe authors design an algorithmic framework for generating algorithms to solve Robust MDPs based on No-Regret Dynamics. Under this framework, the authors further develop novel no-regret online learning algorithms. This framework works for various problem settings, including direct parameterization. Moreover, due to the explicit approximation of the worst-case environment during training, to guarantee convergence, this paper only needs the assumption that the uncertainty set of transitions is convex.\n3.\tThis paper shows that when the objective function of the game is gradient-dominated for both players, one can use Projected Gradient Descent as the oracle. This paper provides tools for identifying the conditions under which the gradient-dominated property of an objective function is ensured. This paper proves that when the objective function is the Value Function in the direct parameterization setting, the proposed algorithm achieves an $O(T^{-1/2})$ convergence rate.\n4.\tThis paper demonstrates that when the objective function is Lipschitz smooth or enjoys strong gradient-dominance with advanced online dynamics, faster convergence rates can be obtained.\n5.\tThis paper is well-written and easy to follow.\n\n**Weaknesses:**\n\n1.\tThe experiments should be put in the main paper, instead of Appendix. It seems that the experiments only include the results of the proposed algorithm. It would enhance the experiment part if the authors can add more baselines, e.g., the adaptations of prior algorithms or ablated variations, and compare the empirical performance of the proposed algorithm and baselines.\n2.\tIt would facilitate the readers’ understanding if the authors can give more discussions on the connection between the proposed algorithmic framework and results and existing algorithms and results in the no-regret and robust MDP literature.\n3.\tIn addition to direct parameterization, softmax parameterization is also widely used in policy gradient methods for RL. Can the proposed algorithmic framework work for softmax parameterization? Can the authors give some comments on possible extensions to softmax parameterization?\n\nOverall, I think this submission is a good paper, and would further improve if the authors can address the above comments. I tend to weakly accept.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies designing an algorithm that can find environmentally robust policies efficiently and handle different model parameterizations. To solve this problem, this paper proposes a No-Regret Dynamics framework that utilizes policy gradient methods and iteratively approximates the worst case environment during training, avoiding assumptions on the uncertainty set. With a toolbox of nonconvex online learning algorithms, the authors demonstrate that the proposed framework can achieve fast convergence rates for many problem settings and relax assumptions on the uncertainty set of transitions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the review on weaknesses above.", "broader_impact_concerns": "I do not have ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BSA5BVpFrv", "reviewer": "Reviewer_ypfF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper aims to address an interesting and important problem through the lens of a unified framework. My main concert with the work lies on its formality and presentation. \n\n- It is not clear what is the exact contribution of this work is, given that the proposed algorithms are already known. It looks like the application of these algorithms to the specific scenario of this work. The formalization of them into a framework for robust MDPs can be a valuable contribution, but it's presentation should be clarified.\n\n- The use of notation is sometimes confusing, e.g., the double definition of the probability of the state distribution d^W and d^\\pi? Why the introduction of a generic objective g(\\pi,W), when the rest of the paper relies on the value function? Overall the paper lacks formalism.\n\n- The lack of equation numbering and lack of referencing across the paper makes it sometimes difficult to follow. This is specially so in the appendices, where proofs are presented in a not completely formal way, which makes it difficult to check for correctness. E.g, Lemma 5.2 claims, \"[...] the third inequality comes from [...]\", instead of using numbering and in this case, there are no inequalities in the previous equation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a framework for solving robust MDPs based on no-regret dynamics. Different algorithms are provided under this framework: Best-Response and Follow the Perturbed Leader Plus (FTPL+) are proposed. Further, under the nonconvexity of the setting, a usual necessity of these algorithms is the need for a global minimizer oracle. The show that for robust MDPs, the value function shows gradient-dominance, a sufficient condition to use projected gradient descent as an oracle. Convergence rates are provided for the algorithm of study.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The aspects previously mentioned should be addressed.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TpcFgfic7h", "reviewer": "Reviewer_E21q", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n* The writing is clear and easy to follow.\n* The paper makes important contributions towards solving Robust MDPs under little structure assumptions. The proposed framework is general, versatile, and suitable for various problem settings.\n\nComment and questions:\n* Including some discussions on implementing a practical algorithm based on the theoretical framework would further strengthen the paper.\n* Why FTPL and OFTPL are suitable for the policy player?\n* What is $d_w$ in Theorem 6.1?\n* The framework has a general loss $g(W,\\pi)$. Can you give more examples? Can it be used in, say, pure exploration?\n\nMinor changes:\n* Including descriptions for the GridWorld MDP (for completeness) would be better for reading.\n* Bottom line on Page 1, \"Several works\": Please add the references.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of solving robust MDPs. The authors propose to use a No-Regret Dynamics framework that iterates between policy learning and worst-case transition approximation. This two-player framework doesn't require stringent assumptions about the uncertainty set except convexity. A toolbox of non-convex online learning algorithms for both players is provided. By leveraging the gradient dominance property of robust MDPs, the framework can use Projected Gradient Descent as an optimization oracle for the online algorithms. With that, the proposed algorithm can yields an $\\mathcal{O}(T^{-\\frac{1}{2}})$ convergence rate. In addition, the authors also discuss achieving faster convergence rates under stronger assumptions (e.g., smoothness).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers felt that the revisions made by the authors during the review process satisfied their main questions and concerns.
Decision: Accept (poster)