Robust Reinforcement Learning with General Utility

Q10: The example: If I am not wrong the choices of parameters do not fit to the theory. Do they? If not, that should at least be discussed. How about the assumptions, can they be checked in that example?

A: Good question and suggestion. Our simulation does not exactly follow the theoretical hyperparameter choices and assumptions. We will explain this in our revision.

About Summary: Our work not only provides Algorithm 1 with gradient convergence results, but also Algorithm 2 with global convergence results.

Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review questions/comments. We will revise the manuscript accordingly after the review discussion period. Please let us know if further clarifications are needed.

Q1: The weakness in the O notation requires reworking the long proof.

A: Thank you for your suggestion. Similar to theoretical results in [1,2], our Theorem 2 uses the $\mathcal{O}$ notation to stress the dependence on the large positive constants like $(1-\gamma)^{-1}$ and $\epsilon^{-1}$. For example, $\mathcal{O}[(1-\gamma)^{-8}\epsilon^{-4}]$ is defined as $C(1-\gamma)^{-8}\epsilon^{-4}$ where the constant $C$ does not depend on $\gamma$ and $\epsilon$. This definition fits the following limiting sense.

The proof of Theorem 2 only uses the $\mathcal{O}$ notations to simplify the convergence rates at the end of Appendices N.4-N.5 and to derive the sample complexity in Appendix N.6. These $\mathcal{O}$ notations take about only 1 page in total, and will be changed to explicit expressions in the revision within 3 hours, following the procedure below:

Step 1: At the end of Appendices N.4-N.5, by substituting Eqs. (93-94) into Eqs. (120) and (125), we can obtain O-free convergence rates of $\mathbb{E}\big[\|G_{b}^{(\theta)}(\theta_{\widetilde{k}},\xi_{\widetilde{k}})\|^2\big]$ and $\mathbb{E}\big[\|G_{a}^{(\xi)}(\theta_{\widetilde{k}},\xi_{\widetilde{k}})\|^2\big]$ respectively.

Step 2: In Appendix N.6, the hyperparameters with $\mathcal{O}$-notations will be changed to O-free hyperparameters as follows.

Q5: There should be examples for the assumptions. For instance, what standard class of policies satisfy the policy assumptions? This is certainly standard for PG methods but almost all articles discuss some examples (softmax, linear softmax, ...).

A: Thank you for your suggestion. In the revised paper, we will add the following practical examples for the assumptions.

Assumption 1 covers popular policy parameterizations including softmax policy $\pi_{\theta}(a|s)=\frac{\exp(\theta_{s,a})}{\sum_{a'}\exp(\theta_{s,a'})}$ [1] and log-linear policy $\pi_{\theta}(a|s)=\frac{\exp(\theta\cdot\phi_{s,a})}{\sum_{a'}\exp(\theta\cdot\phi_{s,a'})}$ [1], as well as popular transition kernels including direct parameterization $p_{\xi}(s'|s,a)=\xi _ {s,a,s'}$ [2,3] and linear parameterization $p_{\xi}(s'|s,a)=\xi\cdot\phi_{s,a,s'}$ [4,5] when $\Xi$ is located away from 0, i.e., $\inf_{s,a,s',\xi\in\Xi}p_{\xi}(s'|s,a)\ge p_{\min}$ for a constant $p_{\min}>0$. Assumptions 2-3 cover the three convex utility examples in Section 2 of [6], including MDP with Constraints, pure exploration, and learning to mimic a demonstration. Assumptions 4 and 8 are similar and cover direct policy parameterization $\pi_{\theta}(a|s)=\theta _ {s,a}$, since it has been proved that direct policy parameterization satisfies Assumption 4.1 of [6] which implies Assumptions 4 and 8. Assumptions 5-7 cover $s$-rectangular $L_1$ and $L_{\infty}$ ambiguity sets (defined as $\Xi=\{\xi:\|\xi(s,:,:)-\xi^0(s,:,:)\| _ p\le \alpha_s\}$ for $p\in\{1,\infty\}$ respectively using direct kernel parameterization $p_{\xi}(s'|s,a)=\xi_{s,a,s'}$), which are very popular in robust RL [7,8].

[1] Agarwal, Alekh, et al. "On the theory of policy gradient methods: Optimality, approximation, and distribution shift." Journal of Machine Learning Research 22.98 (2021): 1-76.

[2] Kumar, Navdeep, et al. "Policy gradient for rectangular robust markov decision processes." Advances in Neural Information Processing Systems (2023).

[3] Behzadian, Bahram, Marek Petrik, and Chin Pang Ho. "Fast Algorithms for $L_\infty$-constrained S-rectangular Robust MDPs." Advances in Neural Information Processing Systems (2021).

[4] Ayoub, Alex, et al. "Model-based reinforcement learning with value-targeted regression." International Conference on Machine Learning. PMLR, 2020.

[5] Zhang, Junkai, Weitong Zhang, and Quanquan Gu. "Optimal horizon-free reward-free exploration for linear mixture mdps." International Conference on Machine Learning. PMLR, 2023.

[6] Zhang, Junyu, et al. "Variational policy gradient method for reinforcement learning with general utilities." Advances in Neural Information Processing Systems 33 (2020): 4572-4583.

[7] Hu, Xuemin, et al. "Long and Short-Term Constraints Driven Safe Reinforcement Learning for Autonomous Driving." ArXiv:2403.18209 (2024).

[8] Khairy, Sami, et al. "Constrained deep reinforcement learning for energy sustainable multi-UAV based random access IoT networks with NOMA." IEEE Journal on Selected Areas in Communications 39.4 (2020): 1101-1115.

Q6: The authors should point out that this is a theoretical estimate with no practical implication. Similarly, the theoretical iteration numbers and batch sizes are ridiculously large. This is a theoretical worst case estimate (perfectly fine with me) but it should be mentioned that in practice those numbers would not be used. If I am not wrong those numbers are not used in their own simulation example (which should also be mentioned).

A: Thank you for your suggestion. Yes, you are right. These theoretical and conservatively large hyperparameter choices are not necessarily needed in practical implementation, so the hyperparameters in our simulation are obtained by fine-tuning not theory. We will add this explanation in the revision.

Q7: It might be interesting to think about unbiased gradient estimators for general utility RL. Such have been found in the past years for linear RL, I guess something similar works in the non-linear case.

A: Thank you for your suggestion. All the robust RL with general utility works we found either only provide true gradients or provide gradient estimators with bias which goes to 0 as the truncation level $H\to+\infty$. We select such a gradient estimator with sufficiently large $H$ to bound the bias.

Q8: About Assumption 1 for p, there is no discussion, if (or not) that assumption is strong. In what situation is the assumption satisfied? Is there any interesting situation in which the assumption is satisfied?

A: Thank you for your suggestion. See our answer to your Q5.

Q9: Assumption 4 looks brutal to me. Is there any way to verify that assumption? Is there any example for which it can be verified? Perhaps that was addressed in past work, but some discussion is needed.

A: Good question and suggestion. See our answer to your Q5.

Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review questions/comments. We will revise the manuscript accordingly after the review discussion period. Please let us know if further clarifications are needed.

Q1: The nonconvex case is only handled in the Appendix. I liked the fact that they have much more in their pocket than the content of the main article. The nonconvex case could nevertheless have been mentioned only in the conclusion as it is not really part of the main article.

A: Thank you for your suggestion and appreciation. Based on all the reviewers' feedback, we will remove concave utility and other utilities that satisfy weak Minty variational inequality, since they lack application examples.

Q2: The numerical experiments should be part of the main article as they add a lot to the theoretical results.

A: Thank you for your suggestion and appreciation. We originally planned to put numerical experiments in the main article. Later, we found that after fitting some other necessary parts into the main article, including problem formulation, algorithms and theoretical results for both gradient and global convergence, the 9-page limit did not allow experiments. Therefore, in line 194 in the main article, we refer the experiments to Appendix A.

Q3: The results are very technical and some explanations (for example for the main theorems) could be beneficial to the readers.

A: Thank you for your suggestion.

Theorem 2 provides the first sample complexity result to achieve $\epsilon$-stationtary point of the objective function $f(\lambda_{\theta,\xi})$ for robust RL with general utility. Specifically, we select sufficiently large batchsizes and truncation numbers to ensure that the stochastic gradients are close to the true gradients, and select sufficiently many iterations to ensure optimization progress. These theoretical and conservatively large hyperparameter choices are not necessarily needed in practical implementation.

Theorem 3 provides the first global convergence rate for robust RL with general utility. The global convergence error consists of sublinear convergence rate $\mathcal{O}(1/K)$ with $K$ iterations, and $\max_{1\le k\le K}\epsilon_k$ which denotes the convergence error of the subroutine for maximizing the concave function $A_k$.

Q4: Can the author explain if the control on the size of the gradient with respect to $\xi$ corresponds to a convergence for the functional itself or just that the algorithm is going to slow down?

A: Good question. We select sufficiently large batchsizes and truncation numbers to ensure that the estimated stochastic gradients are close to the true gradients $\nabla_{\theta} f(\lambda_{\theta,\xi})$ and $\nabla_{\xi} f(\lambda_{\theta,\xi})$.

Q5: "134: \quad before ,"

A: Thank you for pointing this out. We will add spaces before the commas.

Q6: 309: $\epsilon_k$ only defined in Algorithm.

A: Thank you for pointing this out. We will modify line 309 to "with $\beta_k=\frac{2\sqrt{2}\ell_{\lambda}}{k+2}$, $\sigma_k=\frac{4\sqrt{2}\ell_{\theta}\ell_{\lambda}}{k+2}$ and any $\epsilon_k>0$", since the convergence rate (20) holds for any $\epsilon_k>0$.

Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review questions/comments. We will revise the manuscript accordingly after the review discussion period. Please let us know if further clarifications are needed.

Q1: I think the authors might do a better job motivating and introducing the problem at the introduction section. I'm confused about the exact definition of robust RL with general utility until the end of section 2. Is it possible to provide intuitive explanations at the beginning?

A: Thank you for your suggestion. In the revised introduction, we will briefly compare the definitions of the existing RL with general utility problem and our proposed robust RL with general utility problem. Specifically, the existing RL with general utility problem is formulated as $\min_{\theta} f(\lambda_{\theta,\xi_0})$ where the agent aims to select its policy parameter $\theta$ to minimize the cost-related utility function $f$, under a fixed transition kernel parameter $\xi_0$. In contrast, our robust RL with general utility problem is formulated as $\min_{\theta} \max_{\xi\in\Xi}f(\lambda_{\theta,\xi})$ where the agent aims to select a robust optimal policy $\theta$ that minimizes the utility under the worst possible transition kernel parameters $\xi\in\Xi$. We will refer the readers to Section 2 for more details. To motivate our research, we will also briefly summarize the useful special cases and application examples of our proposed problem listed in our global response.

Q2: It might be easier to understand the 4 different settings if the authors can motivate with good examples in practice (convex utility, concave utility, polyhedral ambiguity set and weak Minty variational inequality).

A: Thank you for your suggestion.

Based on all the reviewers' feedback, we will remove concave utility and other utilities that satisfy weak Minty variational inequality, since they lack application examples.

We have listed two popular examples of polyhedral ambiguity set, $L_1$ and $L_{\infty}$ ambiguity sets in lines 48-49 in the introduction, and defined these sets right after Assumption 7. To have stronger motivation, we will also add the explanation that these ambiguity sets are popular in robust reinforcement learning, an important special case of our proposed robust RL with general utility.

We will add the following examples of convex utilities [1] to our revised paper.

(1) MDP with Constraints or Barriers, which has safety-critical applications including healthcare [2], autonomous driving [3] and unmanned aerial vehicle [4].

(2) Pure exploration, which can be applied to explore an environment that lacks reward signals [5].

(3) Learning to mimic a demonstration, which is used to help the agent mimic the expert demonstration [1].

Q3: There have been a lot of assumptions in the paper before the convergence results. Can authors comment on how practical those assumptions are? And under such assumptions, can the authors comment on the tightness of the results in terms of sample complexity / iteration complexity?

A: Thank you for your suggestion. In the revised paper, we will add the following practical examples for the assumptions.

Assumption 1 covers popular policy parameterizations including softmax policy $\pi_{\theta}(a|s)=\frac{\exp(\theta_{s,a})}{\sum_{a'}\exp(\theta_{s,a'})}$ [6] and log-linear policy $\pi_{\theta}(a|s)=\frac{\exp(\theta\cdot\phi_{s,a})}{\sum_{a'}\exp(\theta\cdot\phi_{s,a'})}$ [6], as well as popular transition kernels including direct parameterization $p_{\xi}(s'|s,a)=\xi_{s,a,s'}$ [7,8] and linear parameterization $p_{\xi}(s'|s,a)=\xi\cdot\phi_{s,a,s'}$ [9,10] when $\Xi$ is located away from 0, i.e., $\inf_{s,a,s',\xi\in\Xi}p_{\xi}(s'|s,a)\ge p_{\min}$ for a constant $p_{\min}>0$. Assumptions 2-3 cover all the three convex utilities listed in our answer to your Q2. Assumptions 4 and 8 are similar and cover direct policy parameterization $\pi_{\theta}(a|s)=\theta_{s,a}$ (Actually, it has also been proved to satisfy Assumption 4.1 of [1] which implies Assumptions 4 and 8). Assumptions 5-7 cover $s$-rectangular $L_1$ and $L_{\infty}$ ambiguity sets (defined as $\Xi=\{\xi:\|\xi(s,:,:)-\xi^0(s,:,:)\| _ p\le \alpha_s\}$ for $p\in\{1,\infty\}$ respectively using direct kernel parameterization $p_{\xi}(s'|s,a)=\xi_{s,a,s'}$), which are very popular in robust RL [3,4].

We are not sure about the tightness of our results because the complexity lower bounds are unknown for our proposed robust RL with general utility. However, as mentioned in our conclusion, our gradient complexities may still be improved in the future, compared with the state-of-the-art gradient complexities (Lin et al., 2020; Pethick et al., 2023) for minimax optimization.

[1] Zhang, Junyu, et al. "Variational policy gradient method for reinforcement learning with general utilities." Advances in Neural Information Processing Systems 33 (2020): 4572-4583.

[2] Corsi, Davide, et al. "Constrained reinforcement learning and formal verification for safe colonoscopy navigation." 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2023.

[3] Hu, Xuemin, et al. "Long and Short-Term Constraints Driven Safe Reinforcement Learning for Autonomous Driving." ArXiv:2403.18209 (2024).

[4] Khairy, Sami, et al. "Constrained deep reinforcement learning for energy sustainable multi-UAV based random access IoT networks with NOMA." IEEE Journal on Selected Areas in Communications 39.4 (2020): 1101-1115.

[5] Hazan, Elad, et al. "Provably efficient maximum entropy exploration." International Conference on Machine Learning. PMLR, 2019.

[6] Agarwal, Alekh, et al. "On the theory of policy gradient methods: Optimality, approximation, and distribution shift." Journal of Machine Learning Research 22.98 (2021): 1-76.

[7] Kumar, Navdeep, et al. "Policy gradient for rectangular robust markov decision processes." Advances in Neural Information Processing Systems (2023).

[8] Behzadian, Bahram, Marek Petrik, and Chin Pang Ho. "Fast Algorithms for $L_\infty$-constrained S-rectangular Robust MDPs." Advances in Neural Information Processing Systems (2021).

[9] Ayoub, Alex, et al. "Model-based reinforcement learning with value-targeted regression." International Conference on Machine Learning. PMLR, 2020.

[10] Zhang, Junkai, Weitong Zhang, and Quanquan Gu. "Optimal horizon-free reward-free exploration for linear mixture mdps." International Conference on Machine Learning. PMLR, 2023.

Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review questions/comments. We will revise the manuscript accordingly after the review discussion period. Please let us know if further clarifications are needed.

Q1: Modeling motivation: The paper lacks a comparative analysis to demonstrate superiority over existing non-robust methods in handling scenarios like constrained and risk-averse RL. To solidify its contributions, it should include empirical or theoretical evidence comparing its performance against established methods, especially in real-world scenarios that involve distributional shifts.

A: Thank you for your suggestion. Our work is fundamentally different from the works on non-robust RL with general utility, not only in methodology, but also in the objective function and convergence measures. Specifically, non-robust RL with general utility aims to solve $\min_{\theta\in\Theta}f(\lambda_{\theta,\xi_0})$ under a fixed environment $\xi_0\in\Xi$, while our proposed robust RL with general utility aims to solve $\min_{\theta\in\Theta}\max_{\xi\in\Xi}f(\lambda_{\theta,\xi})$ under the worst possible test environment $\xi\in\Xi$. As a result, our convergence measures are also very different, so the performance is not directly comparable. We will stress these fundamental differences in our revised paper.

Q2: Computational costs. Detailed evaluations of the computational overhead comparing to non-robust approaches needs to be presented to demonstrate the price of robustness and usefulness of the modeling.

A: Thank you for your suggestion. As mentioned in our answer to Q1, the computational overhead is not directly comparable, since the non-robust approaches and our robust approaches have different objectives and different convergence measures.

Q3: Scalability. The robustness in transition kernels is modeled through s-rectangular uncertainty with direct parameterization of the transition kernels, which appears to be less advantageous for scalability and generalization in complex or continuous environments. The paper should discuss potential adaptations or extensions of the method that can handle larger state spaces without compromising theoretical integrity.

A: Thank you for your suggestion. To extend to large state spaces, we can adopt linear occupancy measure $\lambda_H^{\pi_{\theta}}(s,a)\approx \omega_{\theta}\cdot\phi(s,a)$ (Barakat et al. 2023) and linear transition kernel parameterization $p_{\xi}(s'|s,a)=\xi\cdot\phi_{s,a,s'}$ [1,2], with parameters $\omega_{\theta}$ and $\xi$ of scalable dimensionality. To extend to Robust RL with continuous state space, we can adopt Gaussian policy (Barakat et al. 2023) and transition kernel $s_{t+1}=f(s_t,a_t)+\omega_t$ with Gaussian noise $\omega_t\in\mathbb{R}^d$ [3]. We will add these potential extensions to our conclusion section.

[1] Ayoub, Alex, et al. "Model-based reinforcement learning with value-targeted regression." International Conference on Machine Learning. PMLR, 2020.

[2] Zhang, Junkai, Weitong Zhang, and Quanquan Gu. "Optimal horizon-free reward-free exploration for linear mixture mdps." International Conference on Machine Learning. PMLR, 2023.

[3] Ramesh, Shyam Sundhar, et al. "Distributionally robust model-based reinforcement learning with large state spaces." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.

Q4: Hyperparameters. The algorithm requires managing an extensive set of hyperparameters, complicating its practical implementation. The paper should propose methods to reduce the complexity of hyperparameters, such as adaptive tuning or simplified parameter settings, to improve usability and accessibility.

A: Thank you for your suggestion. Based on Theorem 2, we can reduce the hyperparameters in Algorithm 1 by replacing $m_{\lambda}^{(1)}, m_{\theta}^{(1)}, m_{\lambda}^{(3)}, m_{\theta}^{(3)}, m_{\lambda}^{(4)}, m_{\theta}^{(4)}$ with $m^{(1)}$, replacing $m_{\lambda}^{(2)}, m_{\theta}^{(2)}$ with $m^{(2)}$, and replacing $\{H_{\lambda}^{(k)},H_{\theta}^{(k)}\}_{k=1}^4$ with $H$. Based on Theorem 3 and Corollary 1, we can reduce the hyperparameters in Algorithm 2 by replacing $\sigma_k$, $\epsilon_k$ and $\beta_k$ with $\frac{\sigma}{k+2}$, $\epsilon$ and $\frac{\beta}{k+2}$ respectively.

Q5: Comparison with Barakat et al. 2023: It would be helpful if the authors could provide a more detailed comparative analysis of their approach with the work by Barakat et al., especially in terms of algorithmic differences and performance in continuous state-action spaces.

A: Thank you for your suggestion. As mentioned in our answer to Q1, the most fundamental difference between our work and (Barakat et al. 2023) is that we aim at different objectives and convergence measures. As a result, the biggest difference in algorithms is that (Barakat et al. 2023) only updates policy parameter $\theta$ under fixed transition kernel parameter $\xi_0\in\Xi$ while we update both $\theta$ and $\xi\in\Xi$. The performance is not directly comparable also due to the differences in objectives and convergence measures.

Q6: $\ell_{\lambda^{-1}}$: please provide an explicit example of this constant and its dependence on |S| and |A|.

A: Thank you for your suggestion. It has been proved in [4] that for direct policy parameterization $\pi_{\theta}(a|s)=\theta_{s,a}$, $\ell_{\lambda^{-1}}=\frac{2}{\min_s\rho(s)}\ge \frac{2}{|S|}$ where $\rho$ is the initial state distribution.

[4] Zhang, Junyu, et al. "Variational policy gradient method for reinforcement learning with general utilities." Advances in Neural Information Processing Systems 33 (2020): 4572-4583.

Q7: Line 230: Inversible -> Invertible.

A: Thank you for pointing out this typo. We will correct that.

The properties mentioned in Reviewer joNT's summary belong to two algorithms respectively.

Algorithm 1: stochastic gradient descent with gradient sampling subroutines, general uncertainty set, gradient convergence.

Algorithm 2: polyhedral s-rectangular uncertainty set, global convergence.