How does Your RL Agent Explore? An Optimal Transport Analysis of Occupancy Measure Trajectories

We thank the reviewer for the time and effort spent reviewing. We try to address the concerns and questions here.

1. Intuitions behind OMR. 1) We agree that OMR is not continuous over the training trajectory as the steps towards optimal changes are stochastic for any randomized RL algorithm. Similar discontinuity emerges when we try to measure and bound the number of pulls of a specific suboptimal action in regret minimization (e.g. for bandits we refer to Sec 4.5. in [1]), but still this quantity helps to measure the suboptimality of an RL algorithm in terms of regret. 2) We understand that the OMR can change due to smaller changes in the training and the environment. But in expectation, it should depend on the RL algorithm's dynamics for a given environment. Thus, we present an average OMR ($\\pm$ standard deviation) over multiple runs of an RL algorithm in a given environment.

2. Dependence on size of state-action space. The problem-dependent constant in Proposition 4, i.e. $\mathcal{E}_{2}$, is upper-bounded by the product of the state-action space diameter and a sublinear function of its cardinality (in and following Eq (45), Appendix A.7.1). So, number of samples would not grow exponentially with the cardinality of the state-action space ($|\mathcal{Z}|$). Specifically, in Appendix A.7.1., we state that

1. $\mathcal{E}_{2} \leq 4B^{1/2} \text{diam}(\mathcal{Z}) \cdot ( 2 + \frac{1}{2} \text{log} |\mathcal{Z}| )$ $\text{, if } B = 2$
2. $\mathcal{E}_{2} \leq 4B^{1/2} \text{diam}(\mathcal{Z}) \cdot ( |\mathcal{Z}|^{1/2 - 1/B}$ 2 + \frac{1}{2^{B/2 -1} - 1} $)$ $\text{, if } B > 2$

where $|\mathcal{Z}|$ and $diam(\mathcal{Z})$ denote the cardinality and diameter of space $\mathcal{Z}$, respectively, given that $\mathcal{Z} \in \mathbb{R}^{B}$.

3. Computing ESL and OMR during training. Exploration and learning of RL algorithms mainly occur during training. Hence, our metrics are defined within this phase. OMR does use the change in distance to optimal (reduction or increase) at each training step. Also, ESL is the ratio of the learning path to the geodesic path from initial to the final optimal policy. Thus both performance and training dynamics are captured by our metrics.

We are not clear about what you mean by "enjoys good performances even though the dynamics are volatile". If you can explain, we would be happy to respond further.

4. Computing Wasserstein distance. Thanks for the suggestion. For the environments that we studied, we did not need to use Sinkhorn approximations. This is interesting for future work for environments where Wasserstein is costlier to compute. And if we use Sinkhorn, specifically Online Sinkhorn [2], the approximation error will also be of similar order 1/\sqrt{\\#\text{samples}} as in Proposition 4.

5. Exploratory process and performance. Performance is an outcome of the exploratory process and it frequently occurs (depending on the environment) that different exploratory processes (algorithms) have the same performance. However, ESL and OMR directly capture and evaluate the inherent characteristics of the exploratory processes. For example, regret is a common measure of performance, whereas our measures are complementary. Please see our general comment ("Utility of proposed metrics"). Additionally, Proposition 2 connects distance-to-optimal with regret. Depending on the environment, some characteristics might benefit or harm the performance of the algorithm. It should be noted that these characteristics are also impacted by the nature of the environment (sparse vs. dense, stochastic vs. deterministic) as shown in the experiments.

[1] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020. ISBN 978-1-108-48682-8.

[2] A. Mensch and G. Peyré. Online sinkhorn: Optimal transport distances from sample streams. Advances in Neural Information Processing Systems, 33, 1657-1667, 2020.

We thank the reviewer for the time spent reviewing and acknowledging the clarity of our paper and contributions. We refer to the general comment ("Utility of proposed metrics") for detailed discussion on usefulness ESL and OMR. Here, we respond to the other questions/concerns in detail.

1. Wasserstein distance and geodesics. 1) The Wasserstein metric incorporates the geometry of the manifold $\mathcal{M}$ through the coupling distribution $d\pi$ (seen in Eq (2)). Additionally, [1,2] show that 1-Wasserstein and $L_1$ distances between probability measures are related but different (see also Fig 5 https://www.stat.cmu.edu/~larry/=sml/Opt.pdf). 2) $(d_{\mathcal{X}})^p$ is the cost function used to define Wasserstein distance, and $d_{\mathcal{X}}$ is the metric defined over the domain $\mathcal{X}$ of the probability distributions. $d_{\mathcal{X}}$ can be any metric reflecting the structure of optimal transport plans in the space $\mathcal{X}$ [3,4]. Thus, we used L1 metric for discrete gridworld environments and L2 for continuous mountaincar.

[5] states that "An important property of $(P(\Omega),W_{p})$ is that it is a geodesic space and that geodesics are easy to characterize." Chapter 5 in [4] provides details about geodesics in the space ($P(\mathcal{X}), W_{p}$) for $p \ge 1$. $P(\Omega)$ and $P(\mathcal{X})$ are probability distribution spaces, in our work denoted as $\mathcal{M}$, with metric $W_{p}$. Thus, $W_1(\mu,\nu)$ measures the geodesic distance (shortest path on the surface of the manifold) between probability distributions $\mu$ and $\nu$.

We will add a section in the Appendices to clarify these points.

2. ESL and OMR are not correlated with UC. We do not expect any correlation between number of updates (UC) and ESL/OMR because any policy update, irrespective of its stepwise-distance $W_{1}(v_{\pi_{\theta_k}},v_{\pi_{\theta_{k+1}}})$, may not be in the direction towards an optimal policy. For example, one algorithm may make shorter transitions but in the correct direction with higher UC (e.g. SAC). While another algorithm may make longer transitions yet meander towards the correct direction with lower UC (e.g. UCRL2). Meandering expends notable effort hence higher ESL though it may reduce UC. This is well illustrated in Fig 3. We refer to our general comment ("Utility of proposed metrics") for a detailed discussion.

3. Insights from visualizing the exploratory processes. 1) Visualization of exploratory processes is one of the key contributions of our work, as it helps to visually characterize behaviors of RL algorithms and provide visual saliency. There is utility in this visualization as it can enhance understanding of the exploratory process, build intuitions, and allow validation of models. To our knowledge, visualizing RL exploration in a 3D space reflecting the geometry of high-dimensional learning paths has not appeared in the literature. Hence this contribution should not be overlooked. 2) The results in Section 5.1 are consistent with literature but offer insights beyond performance. For example, [6] highlighted that exploration in PSRL is guided by the variance of sampled policies as opposed to optimism in UCRL2. In Fig 3, we see that the guiding variance in PSRL reduces after every policy update until optimality is reached, while UCRL2 maintains high variance due to optimism. Figures in [6] have no way of showing this intuitively.

4. Experimental evidences for ESL and OMR. We refer to our general comment ("Utility of proposed metrics") explaining the usefulness of ESL and OMR. Specifically, the aim of Sec 5.2 is to use ESL and OMR to compare exploratory processes in familiar environments while revealing which exploratory characteristics are more suited to the problem (sparse vs. dense reward, deterministic vs. stochastic).

5. ESL to indicate task complexity. The purpose of Section 5.3 was to test whether ESL scales with task difficulty, but not to propose it as a measure of task complexity. Since ESL captures the effort expended by the exploratory process, it is expected to increase as task difficulty increases - indeed it does.

[1] Indyk, P. and Thaper, N. Fast image retrieval via embeddings. In 3rd international workshop on statistical and computational theories of vision, volume 2, pp. 5, 2003.

[2] A. Gibbs and F. E. Su. On choosing and bounding probability metrics. International Statistical Review / Revue Internationale de Statistique, 2002.

[3] C. Villani. Optimal Transport Old and New. Springer Berlin, Heidelberg, 2009.

[4] F. Santambrogio. Optimal Transport for Applied Mathematicians. Bikhauser Cham, 2015.

[5] S. Kolouri, et. al. Optimal mass transport: Signal processing and machine learning applications. IEEE Signal Processing Magazine, 2017.

[6] I. Osband, B. V. Roy, and D. Russo. (more) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, 2013.

Dear Reviewer yMaN,

We believe that we have fully addressed your concerns with our responses and updated pdf. We hope that you can update your rating if satisfied and / or ask any further questions within the 1 day discussion period remaining.

Thanks.

We thank the reviewer for appreciating the problem of interest and our contributions. While we elaborate on the utility of ESL and OMR in the general comment ("Utility of proposed metrics"), we respond to other specific questions here.

1. Invertibility of Transition Matrix. First, we would like to clarify that $P^{\pi}(s,s')$ denotes the transition matrix $\mathbf{P}^{\pi}$ rather than an entry in the matrix. We will modify the theorem to clearly state "the transition matrix $\mathbf{P}^{\pi}$". Second, this means that the 'reversibility' between individual states is not needed, and entries in the transition matrix $\mathbf{P}^{\pi}$ can be zero. As long as the transition matrix has an inverse, the occupancy measure space is a differentiable manifold. Otherwise, it is a non-differentiable topological space. Eqs. (24) - (28) shows this concretely. We would also like to highlight that the prior works on linear programming and occupancy measures for MDPs [1,2,3] require existence of similar inverse forms of the transition matrix.

2. Interpreting Figures 3 and 4. The plots aim to visualize policy updates and the corresponding dynamics in the occupancy measure space induced by the exploratory processes. More scattered successive points demonstrate large policy updates. The experimental plots Figs. 3 & 4, showing step-wise distance and distance-to-optimal versus update count (UC), should be interpreted keeping Fig. 2 in mind. Close-by successive points forming a line indicate unchanging or little changing policies - possibly 'stuck in suboptimality'. This can occur even when the policy model is updating e.g. case of ($\epsilon=1$)-greedy. The reviewer is right that for SAC and DQN, the big lines are due partly to waiting to fill up the replay buffer but also due to 'stuck in suboptimality'. We will update the figures with the replay buffer collection removed in the revised pdf.

3. 2D plots for the distance-to-optimal and another for the stepwise-distance. 2D versions of plots in Figs. 3 & 4 have been presented in Appendix D.2 for algorithms PSRL, UCRL, DQN, DDPG and SAC, while Appendix D.1 provide enlarged versions of plots in Figs. 3 & 4. In our revised version, we will also have all 2D plots corresponding to Figs. 3 & 4 top rows, side by side for comparison, in the appendix.

[1] M. L. Puterman. Markov decision processes: Discrete stochastic dynamic programming. John Wiley and Sons, 1994.

[2] U. Syed, M. Bowling, and R. E. Schapire. Apprenticeship learning using linear programming. In Proceedings of the 25th International Conference on Machine Learning, pp. 1032–1039. PMLR, 2008.

[3] P. N. Ward. Linear programming in reinforcement learning, 2021. URL https://escholarship.mcgill.ca/downloads/xs55mh725. MSc thesis.

Dear Reviewer GHMN,

We believe that we have fully addressed your concerns with our responses and updated pdf. We hope that you can update your rating if satisfied and / or ask any further questions within the 1 day discussion period remaining.

Thanks.