Single-Trajectory Distributionally Robust Reinforcement Learning

We appreciate the reviewer's comments and efforts sincerely. We believe the following point-to-point response can address all the concerns and misunderstandings.

---

Q. Confusing presentation and too many assumptions. How to justify them.

A. We apologize for the confusing presentation of the results, particularly the organization of the assumptions.

For the main theoretical result (Theorem 3.3), which focuses on the asymptotic convergence of the DRRL algorithm, we only require ONE assumption about the learning rate (Assumption C.10). This assumption can be easily satisfied by some common choices, such as $\zeta_1(n) = \frac{1}{1+n^{0.6}}$, $\zeta_2(n) = \frac{1}{1+n^{0.8}}$, and $\zeta_3(n) = \frac{1}{1+n}$.

The remaining assumptions are not directly related to the specific application of our proposed algorithm but serve to support our general three-timescale stochastic approximation framework. This framework is a side-product of our paper and aims to ensure its generality and independent usage value. Regarding the soundness of the convergence results, we verify that our proposed algorithm (Algorithm 1) meets all the necessary assumptions on Pages 23-24 in the proof of convergence. Consequently, its associated ODE has a unique asymptotically stable equilibrium.

These assumptions are standard and essential in the classical two-timescale stochastic approximation framework (refer to Section 6 in Borkar 2009), and we extend them to establish a three-timescale counterpart.

---

Q. The reason why this DRO problem can be solved by the GD?

A. Although smoothness can contribute to faster convergence speeds when using GD, our DRRL problem is convex and Lipschitz with respect to the dual variable $\eta$, which is sufficient to establish asymptotic convergence.

In our DRO problem (Equation 4), the gradient is almost defined on the entire real line, except when $\eta = \max_{a'}Q(s',a')$. In such cases, we can utilize the subgradient, and our algorithm will still function effectively. In fact, Duchi and Hongseok (2021) also consider the same DRO problem with Cressie-Read divergence of the $f$-family. Our DRRL problem is included in their problem if the $Q$ function is fixed. They apply gradient descent with backtracking Armijo line-searches to address the DRO problem for large datasets.

GD-based approaches are prevalent in past DRO studies, such as those by Namkoong Hongseok and John C. Duchi (2017), Jin, Jikai et al (2021), Qi, Qi et al (2021), Sinha, Aman et al (2017), and Blanchet, Jose et al (2022). Our work is closely related to Duchi and Hongseok (2021), focusing on the Cressie-Read divergence of the $f$-family. Our DRRL problem is included by their DRO problem when the $Q$ function is fixed. They use gradient descent with backtracking Armijo line-searches (Boyd, Stephen P. 2004) for large datasets (Duchi and Hongseok, 2021). Namkoong and John (2016) reformulate the DRO problem as a two-player game and develop a stochastic gradient-based solution combined with bandit learning. In the DRRL community, Wenhao Yang et al. (2023) propose a model-free DRRL algorithm using gradient descent. We believe GD-based DRRL solutions could be promising for efficient problem-solving, especially for online update requirements in RL applications.

---

[1] Duchi, John C., and Hongseok Namkoong. "Learning models with uniform performance via distributionally robust optimization." The Annals of Statistics 49.3 (2021): 1378-1406.

[2] Borkar, Vivek S. Stochastic approximation: a dynamical systems viewpoint. Vol. 48. Springer, 2009.

[3] Namkoong, Hongseok, and John C. Duchi. "Stochastic gradient methods for distributionally robust optimization with f-divergences." Advances in neural information processing systems 29 (2016).

[4] Namkoong, Hongseok, and John C. Duchi. "Variance-based regularization with convex objectives." Advances in neural information processing systems 30 (2017).

[5] Yang, Wenhao, et al. "Avoiding model estimation in robust markov decision processes with a generative model." arXiv preprint arXiv:2302.01248 (2023).

[6] Jin, Jikai, et al. "Non-convex distributionally robust optimization: Non-asymptotic analysis." Advances in Neural Information Processing Systems 34 (2021): 2771-2782.

[7] Qi, Qi, et al. "An online method for a class of distributionally robust optimization with non-convex objectives." Advances in Neural Information Processing Systems 34 (2021): 10067-10080.

[8] Sinha, Aman, et al. "Certifying some distributional robustness with principled adversarial training." arXiv preprint arXiv:1710.10571 (2017).

[9] Boyd, Stephen P., and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

[10] Blanchet, Jose, Karthyek Murthy, and Fan Zhang. "Optimal transport-based distributionally robust optimization: Structural properties and iterative schemes." Mathematics of Operations Research 47.2 (2022): 1500-1529.

We appreciate the reviewer's comments and efforts sincerely. We believe the following point-to-point response can address all the concerns and misunderstandings.

---

Q. Could you please clarify the meaning of the misspecified MDP in the paper?

A. We apologize for not providing a formal definition of the misspecified MDP in the paper. In the context of distributionally robust reinforcement learning (DRRL), the main objective is to learn an optimal policy that is robust to unknown environmental changes. This becomes important when the transition model P and reward function r used during the training data collection differ from those in the test environment. In such cases, we refer to the MDP environment (consisting of the transition model P and reward function r) used for training data collection as the misspecified MDP. A detailed and rigorous definition can be found in Section 2.3. We appreciate your understanding and will ensure to provide clearer explanations in future work.

---

Q. Comparison with Roy et al. (2017) and Badrinath & Kalathil (2021).

A. First, we would like to clarify that the uncertainty sets considered in Roy et al. (2017) and Badrinath & Kalathil (2021) do not cover the ones in our work, as they do not require the transition model to be a valid probability transition in the test environment. In fact, their uncertainty set is equivalent to R-contamination set. This leads to over-conservatism and significantly simplifies the theoretical difficulty and algorithmic design.

In their works, Roy et al. (2017) and Badrinath & Kalathil (2021) use the following ambiguity set:

$$P_i^a := \\{x+ p_i^a \lvert x\in U_{i}^a \\},$$

where $p_i^a$ is the unknown state transition probability vector from the state $i\in \mathcal{X}$ to every other state in $\mathcal{X}$. The confidence region $U_i^a$ must be constrained to ensure $x+p_{i}^a$ lies within the probability simplex. However, they drop the requirement and consider a proxy confidence region. Recall the definition of the R-contamination model,

$$P_s^a=\\{(1-R) p_s^a+R q \mid q \in \Delta_{|S|}\\}, s \in S, a \in A, \text { for some } 0 \leq R \leq 1.$$

Note that $(1-R)p_s^a+R q$ may also lie outside the probability simplex. Thus under the relaxation, the ambiguity set used in Roy et al. (2017) and Badrinath & Kalathil (2021) are equivalent to the R-contamination model. In contrast, our approach requires every element in the ambiguity set to lie within the probability simplex.

This relaxation simplifies the algorithmic design and the convergence establishment. In particular, the $Q$-learning algorithm can be reformulated (see Equation (32) in Roy et al. (2017)) in terms of the operator $H$ as

$$Q_t(i,a) = (1-\gamma_t) Q_{t-1}(i,a) + \gamma_t (HQ_t(i,a) + \eta_t(i,a)),$$

where $\eta_t(i,a)$ is some martingale noise in the non-robust $Q$-learning.

In the robust Q-learning approaches of Roy et al. (2017) and Badrinath & Kalathil (2021), they also benefit from the relaxation mentioned earlier, as the proxy uncertainty set in Equation 10 in Roy et al. (2017) does not depend on the incoming sample $j$. Despite having sufficient samples, their algorithm may still penalize some cases that will never occur, as their ambiguity set lacks distribution-awareness. Thus they mainly focus on ellipsoid and parallelepiped as concrete examples.

In contrast, our approach maintains the worst-case distribution as a valid transition probability (referred to as distributionally aware) to prevent over-conservatism. As a result, $\eta_t(i,a)$ is not mean zero in our paper, as we require the transition to always fall within the probability complex. To address this challenge, our three-timescale algorithmic design, particularly the innermost loop and the second loop, along with the extended stochastic approximation framework, has been proposed.

---

Q. Why the first equation on Page 5 is true?

A. Recall that the definition of $c_k(\rho)$ defined in Lemma 3.1 as $c_k(\rho) = (1+k(k-1)\rho)^{1/k}\ge 1$. Define

$$f(\eta) = \eta-c_k(\rho)(\eta - \max_{a'}Q(s',a'))^+.$$

Then the first order $f'(\eta) = 1 - c_k(\rho) \mathbb{1}\\{\eta \ge \max_{a'}Q(s',a')\\}$.

We know $f'(\eta) = 1>0$ when $\eta <\max_{a'}Q(s',a')$ and $f'(\eta) = 0$ when $\eta \ge \max_{a'}Q(s',a')$.

Thus $\max_{\eta\in \mathbb{R}}f(\eta) = f(\max_{a'}Q(s',a')) = \max_{a'}Q(s',a')$.

Plug it into Equation 5 we have

$$\begin{aligned} r(s,a)+\gamma \sup_{\eta\in \mathbb{R}}\\{\eta-c_k(\rho)(\eta - \max_{a'}Q(s',a'))\\} = r(s,a)+\gamma \{\max_{a'}Q(s',a')-c_k(\rho) \cdot 0\} = r(s,a) + \gamma \max_{a'}Q(s', a'). \end{aligned}$$

Q. Clarification about Algorithm 4.

A. We are sincerely sorry that mistakenly attaching the Algorithm 4 to the appendix, which is the same as Algorithm 1. The more practical algorithm using DQN type of learning scheme is summarized into Algorithm 2.

In particular, in Algorithm 2, we utilize the Deep Q-Network (DQN) architecture and neural networks as functional approximators for the dual variable and Q function in place of the tabular function in Algorithm 1. To improve training stability, we introduce target networks that are updated at a slower rate. We adopt a two-timescale update approach, which is employed to minimize the Bellman error for the Q network and maximize the DR Q value for the dual variable network. Even though this may introduce bias in the dual variable's convergence, resulting in a lower target value for the Q network, this approach serves as a robust update strategy for our DRRL problem, with further discussion in Appendix B.3. Moreover, Algorithm 1 updates on each data arrival, while the practical implementation uses a batch scheme, training the neural networks on a resampled subset of samples with a replay buffer retaining all previous samples. We will move its connection and modifications with algorithm 1 to the main text.

---

Q. The motivation of the combination of online RL with DRO.

A. We appreciate the reviewer's suggestion that combining DRO with offline RL would have more direct application value. One potential application of our online DRRL algorithm is in situations where the test environment's transition or reward functions change incrementally over time. In such cases, a promising algorithm should continuously learn a robust policy to counter potential upcoming perturbations.

Our paper aligns with the model-free Robust RL literature, such as works by Dong, Jing, et al. (2022), Badrinath, et al. (2021), and Wang, Yue, and Shaofeng Zou (2021). These works present model-free algorithms capable of learning optimal robust policies without the need for a simulator or a pre-collected dataset. Our novel analysis of the Cressie-Read family of $f$-divergence and the multi-timescale algorithmic design are generic and can be easily integrated with other non-robust offline RL algorithms, such as the CQL algorithm (Kumar, Aviral, et al., 2020). We chose to present our method using online learning to demonstrate its value under the most stringent update requirements.

---

[1] Dong, Jing, et al. "Online policy optimization for robust MDP." arXiv preprint arXiv:2209.13841 (2022).

[2] Badrinath, Kishan Panaganti, and Dileep Kalathil. "Robust reinforcement learning using least squares policy iteration with provable performance guarantees." International Conference on Machine Learning. PMLR, 2021.

[3] Wang, Yue, and Shaofeng Zou. "Online robust reinforcement learning with model uncertainty." Advances in Neural Information Processing Systems 34 (2021): 7193-7206.

[4] Kumar, Aviral, et al. "Conservative q-learning for offline reinforcement learning." Advances in Neural Information Processing Systems 33 (2020): 1179-1191.

We thank gratefully the reviewer for various valuable suggestions and the praise of our interesting findings and clear writing! The points you raised are explained in the following.

---

Q. Comparison with Panaganti et al. 2022.

A. We appreciate your feedback and agree that our initial claim in the abstract may have been overstated. We will make the necessary corrections to our claim.

We acknowledge the valuable contribution of the RFQI algorithm proposed by Panaganti et al. in 2022 and their novel work in addressing the DR offline RL problem with both theoretical guarantees and practical applications. Our primary focus is on the single trajectory scheme, which presents unique challenges compared to other papers, including Panaganti et al. 2022.

At the time of completion of our paper, the existing literature on model-free DRRL was limited, with the closest works being Panaganti et al. 2022 and Liu et al. 2022. We have already provided a thorough comparison of our algorithm with Liu et al. 2022 in the main text.

We would like to kindly point out the primary distinctions between our proposed algorithm and Panaganti's approach:

1. Ambiguity Set: RFQI concentrates on the total variation distance, while we consider the Creese-Read family of $f$-divergence which can cover several commonly used divergence.

2. Technical Assumptions: RFQI heavily relies on the fail-state assumption, which assumes the existence of a state that yields a 0 reward regardless of the chosen action and must return to itself once entered. Such assumption aids to bypass the nonlinearity in the dual problem of the DRO problem with TV distance, i.e., the $\inf_{s''}V(s'')$ part in Equation 4 in Panaganti et al. 2022, and significantly simplify the estimation. This assumption may not be applicable in certain cases, such as infinite-horizon problems. Instead, the dual problem of the Creese-Read family of $f$-divergence is nonliear with respect the expectation part and we don't impose assumption to remove the nonlinearity. Instead we propose our multi-timescale algorithmic design to address it directly.

3. Data Collection Requirement: While RFQI aims to learn an optimal DR RL policy using a pre-collected offline dataset, our algorithm offers greater flexibility by allowing data to be fed in a single trajectory manner, which includes the pre-collected dataset setting.

4. Algorithmic Design: RFQI is based on the batch data scheme and develops their algorithm from value iteration with function approximation, alternating between updating the dual variable and the $Q$ value to ensure satisfactory optimization before updating the other variable. Conversely, our algorithm is grounded in the $Q$-learning approach and incrementally updates both the dual variable and the $Q$ value function simultaneously upon each data arrival, albeit with distinct learning rates.

   Our algorithm employs the Cressie-Read family of $f$-divergence and can accommodate several common divergences, including KL and $\chi^2$ divergence. The dual problem under this family is highly nonlinear with respect to the expectation, which is addressed by our multiple-timescale algorithmic design. Additionally, we do not impose extra assumptions for our chosen ambiguity set.

Thank you for your detailed reading and valuable comments. Please find our response to the comments below:

---

Q. Disscussion about the similar performance of the proposed DDQR algorithm with the existing robust algorithm SR-DQN.

A. The SR-DQN algorithm demonstrates comparable performance to our proposed DDQR method, primarily when environmental parameters are perturbed (e.g., FMP perturbation in the Cartpole environment and EPP perturbation in the LunarLander environment). In these perturbations, even if the force magnitude (FMP) or engine power (EPP) is altered in the test environment, the transition remains almost deterministic, meaning only one state transitions when an action is taken under the current state. Consequently, these perturbations maintain a similar level of randomness as the original environment, which might not substantially degrade the learned policy. As a result, the soft-robustness principle employed in SR-DQN may be sufficient to manage the perturbation, leading to similar performance as our proposed algorithm.

However, when it comes to action perturbations in both the Cartpole and LunarLander environments, multiple states can be transitioned as different actions are deployed in the environment due to the perturbation. This increases the randomness level, and SR-DQN is notably outperformed by our DDQR algorithm, as it does not provide adequate robustness.

It is worth mentioning that SR-DQN does perform well in certain situations, as demonstrated in the Cartpole experiment by Panaganti et al. (2022).

---

Q. The potential of the proposed algorithm to work in s-rectangular setting.

A. We agree with the reviewer's insight that our proposed algorithm can work in s-rectangular setting by tracking the optimal dual variable for each state, rather then for each state-action pair in the current sa-rectangular setting.

---

[1] Panaganti, Kishan, et al. "Robust reinforcement learning using offline data." Advances in neural information processing systems 35 (2022): 32211-32224.

Thank you for your review and positive comments on our paper. Please find our response to the comments below:

---

Q. Comparison of the sample-complexity of the proposed algorithm with Panaganti et al. 2022.

A. Based on the current literature, a reasonable guess of the sample complexity of our proposed algorithm might be $O(n^{-1/3})$, which may not be as efficient as the $O(n^{-1/2})$ in Panaganti et al. 2022. Our algorithm is based on the multi-timescale nonlinear stochastic approximation method, which, to our knowledge, has not been considered for finite sample efficiency in existing literature. While previous works have mostly focused on the linear case for the two-timescale scenario, there is limited information available for the nonlinear counterpart.

Broadly speaking, for linear stochastic approximation, a notable result in Dalal et al. 2018 suggests that the sample efficiency can be at most $O(n^{-1/3})$, where $n$ represents the sample size. Subsequently, Kaledin Maxim et al. 2020 and Dalal Gal et al. 2020 improved this rate to $O(n^{-1/2})$ by further exploiting the linear structure. In the case of nonlinear two-timescale stochastic approximation, Doan Thinh T has established a $O(n^{-1/3})$ sample efficiency guarantee. Given the current progress in understanding two-timescale nonlinear stochastic approximation, we anticipate that the optimal sample efficiency we can achieve is $O(n^{-1/3})$.

---

Q: Discussion about the practical implementation of DQR algorithm.

A: We have deferred the discussion of the specific implementation to Appendix B.3 and summarized into Algorithm 2. In this answer, we restate the implementation details, particularly the differences from the DRQ algorithm (Algorithm 1), and will move the main part of the discussion to the main text.

Instead of the tabular function in Algorithm 1, we adopt the Deep Q-Network (DQN) architecture (Mnih et al., 2015) and choose neural networks as functional approximators for the dual variable and the Q function. To enhance training stability, we introduce another set of neural networks as the corresponding target networks, which are updated at a slower rate. Due to the existence of approximation error, we adopt a two-timescale update approach: our Q network aims to minimize the Bellman error, while the dual variable $\eta$ network strives to maximize the DR Q value. The two-timescale update approach could introduce bias in the convergence of the dual variable, and thus the dual variable η may not be the optimal dual variable for the primal problem. Given the primal-dual structure of this DR problem, this could render an even lower target value for the Q network to learn. This approach can be understood as a robust update strategy for our original DRRL problem. More discussion about the validity of this update strategy can be found in Appendix B.3.

Another significant difference is in the update scheme. While in Algorithm 1, we update on each data arrival, in the practical implementation, the neural networks are updated in a batch scheme, i.e., trained on a resampled subset of samples with a replay buffer keeping all the previous samples.

---

[1] Mnih, Volodymyr, et al. "Human-level control through deep reinforcement learning." nature 518.7540 (2015): 529-533.

[2] Dalal, Gal, et al. "Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning." Conference On Learning Theory. PMLR, 2018.

[3] Panaganti, Kishan, et al. "Robust reinforcement learning using offline data." Advances in neural information processing systems 35 (2022): 32211-32224.

[4] Kaledin, Maxim, et al. "Finite time analysis of linear two-timescale stochastic approximation with Markovian noise." Conference on Learning Theory. PMLR, 2020.

[5] Dalal, Gal, Balazs Szorenyi, and Gugan Thoppe. "A tale of two-timescale reinforcement learning with the tightest finite-time bound." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 04. 2020.

[6] Doan, Thinh T. "Nonlinear two-time-scale stochastic approximation convergence and finite-time performance." IEEE Transactions on Automatic Control (2022).