How does Your RL Agent Explore? An Optimal Transport Analysis of Occupancy Measure Trajectories
reinforcement learning;wasserstein distance;occupancy measure;exploration-exploitation;effort of learning
Yes
No ethics review needed.
- The plots in Fig 3 and 4 are tough to parse - what is the big line in Fig 3 for SAC and DQN. Is this the time it takes to fill the replay buffer? If so, why are the colors of the line changing?
- The approach is innovative and valuable as it effectively incorporates the exploratory components of the learning problem, successfully capturing these aspects. 
- The methodology is both theoretically robust and practically applicable. Experiments conducted on grid world and mountain car environments suggest that the proposed methodology can capture key aspects related to exploratory dynamics within the learning problem. 
- The paper is clearly written and easy to follow.
The paper introduces a novel method to assess the difficulty of learning in sequential decision-making problems. This is achieved by conceptualizing the learning problem as the cumulative optimal transport distance between consecutive occupancy measures, which correspond to the policies generated by a learning algorithm. The authors utilize the Wasserstein distance between occupancy measures to define the notion of distance between policies within a manifold. This leads to the definition of the hardness of the learning problem, termed as the Effort of Sequential Learning (ESL), and its connection to regret via the Optimal Movement Ratio (OMR). The authors also present finite-sample estimates for these quantities, with corresponding approximation guarantees. The efficacy of their metrics is demonstrated on classic reinforcement learning (RL) tasks, incorporating a variety of popular RL algorithms.
- The main limitation of this work is found in the assumption made in Proposition 1, where the authors presume the existence of the inverse of $P^{\pi}(s,s')$. This assumption effectively implies that any policy $\pi$ is reversible within the environment, meaning the agent following such a policy can always undo its actions. This is a very strong assumption; for example, in an environment where an agent can break a vase, this assumption suggests the agent can also reverse this action and restore the vase to its original state. This assumption is not highlighted enough and significantly narrows the scope of this work in comparison to broader decision-making settings. I recommend the authors explicitly state this assumption and discuss its implications.

- The practical utility of the proposed metrics is unclear. The 3D plots (Fig 3 and 4) are challenging to interpret. I suggest the authors present the same findings using separate 2D plots—one for the distance to optimal and another for the stepwise-distance.
Yes
No ethics review needed.
1. What information do ESL and OMR provide about the learning process beyond that provided by sample complexity / UC and regret?
2. Why is ESL better for measuring task complexity than sample complexity / UC or regret?
Overall, the paper's objective of developing metrics for quantitative comparison of the learning processes of RL algorithms that go beyond the standard sample complexity / total number of update steps and regret is well-motivated and likely of interest to the community. In particular, the idea of achieving this by examining the effort expended in shifting probability mass around in occupancy measure space during the learning process is an interesting one and worth further investigation. Finally, the paper is clearly written and straightforward to understand.
The paper proposes new metrics, effort of sequential learning (ESL) and optimal movement ratio (OMR), that are used to study the sequence of policies, $\pi_{\theta_1}, \ldots, \pi_{\theta_n}$, generated by a reinforcement learning (RL) algorithm by examining the corresponding sequence of state-action occupancy measures, $v_{\pi_{\theta_1}}, \ldots, v_{\pi_{\theta_n}}$, induced by those policies. These metrics consider the 1-Wasserstein distances between consecutive occupancy measures $W_1(v_{\pi_{\theta_k}}, v_{\pi_{\theta_{k+1}}})$ over the entire space of state-action occupancy measures, $\Delta(S \times A)$. Theoretical results are provided stating that the set $\mathcal{M} =$ {$v_{\pi_{\theta}} \ | \ \theta \in \Theta$} $\subset \Delta(S \times A)$ is a differentiable manifold and that regret of an RL algorithm is upper-bounded by the sum of Wasserstein distances, and practical approximations of ESL and OMR computed using finite-rollout datasets are proposed and upper bounds on their approximation error are given. Experimental results are provided on a 5x5 gridworld problem and the MountainCar environment that visualize occupancy measure trajectories of a variety of algorithms (Q-learning, UCRL, PSRL, SAC, DQN), compare their ESR, OMR and total number of updates performed until convergence (UC), and illustrate that ESL tends to increase with task difficulty.
Despite its strengths, the paper has key weaknesses.

First, the ESR and OMR metrics are misguided, since the effort measured by Wasserstein distance in the space of state-action occupancy measures does not necessarily correspond to effort performed by the algorithm. This arises due to Definition 1 not taking the differential structure of the manifold $\mathcal{M}$ into account: specifically, the distance $d_{\mathcal{X}}$ that the paper uses in the definition of the Wasserstein distance is $\ell$1 distance in the space $\Delta( S \times A)$, instead of a corresponding distance over the surface of the manifold $\mathcal{M}$ (see the discussion following eq. (2)). This means that ESL and OMR may misrepresent occupancy measures that are far apart (or close together) over the surface of $\mathcal{M}$ as close together (or far apart) by only considering their distance over $\Delta( S \times A)$.

To see this, suppose that two different algorithms, algorithm 1 and algorithm 2, yield a sequence of policies $\pi_{\theta_1}, \ldots, \pi_{\theta_m}$ and $\pi_{\theta_1}', \ldots, \pi_{\theta_n}'$, respectively, where $m \ll n$ and $\pi_{\theta_m} = \pi_{\theta_n}' = \pi^*$. Suppose furthermore that the occupancy measure trajectories $v_{\pi_{\theta_1}}, \ldots, v_{\pi_{\theta_m}}$ and $v_{\pi_{\theta_1}'}, \ldots, v_{\pi_{\theta_n}'}$ are such that $C = \sum_{k=1}^{m-1} W_1(v_{\pi_{\theta_k}}, v_{\pi_{\theta_{k+1}}}) \gg 1$, while $C' = \sum_{k=1}^{n-1} W_1(v_{\pi_{\theta_k}'}, v_{\pi_{\theta_{k+1}}'}) = 1$ (see eq. (4) for $C$ definition). Without imposing special structure on the policy parametrization, there is nothing preventing such a situation from arising. In this case, we have that the ESL $\eta$ of algorithm 1 (see ESL definition in eq. (5)) satisfies $\eta \gg 1$, while the ESL $\eta'$ of algorithm 2 satisfies $\eta' = 1$, despite the fact that algorithm 1 achieved optimality in far fewer steps ($m \ll n$) than algorithm 2. This casts doubt on the usefulness of ESL and OMR as proxies for the efficiency of the learning process. **Notice that this kind of situation actually arises in the experiments provided in the paper:** in Table 1 and the top half of Table 2 the algorithms with lowest UC have large ESL and OMR values, while the algorithms with smallest ESL and OMR values have large UC values. Since ESL and OMR are thus not positively correlated with sample complexity or UC, this raises the question: why are ESL and OMR useful? what insight into the learning process do they provide that sample complexity / UC or regret do not? The answer to these questions is not clear from the paper.

In addition, the experimental results do not provide clear arguments supporting the usefulness of ESL and OMR. While visualizing occupancy measure trajectories in Sec. 5.1 is an interesting exercise, it is not clear how these results support the main goal of providing "insight into the exploration processes of RL algorithms" stated in the abstract. For the reasons described at the end of the preceding paragraph, the results of Sec. 5.2 raise concerns regarding the usefulness of ESL and OMR for comparing the learning processes of RL algorithms. Finally, though Sec. 5.3 does provide evidence that ESL is positively correlated with task difficulty, it also raises an important question: aren't sample complexity / total number of update steps or even regret useful for measuring task complexity as well? why should ESL be preferred?

**Suggestion:** ESL and OMR may be more rigorously grounded by developing a version of Definition 1 that accounts for the structure of $\mathcal{M}$. This will complicate the theoretical and approximation results, but it may be possible to consider versions of those results when the differential structure of $\mathcal{M}$ is particularly simple, such as with tabular or softmax policies.
Yes
No ethics review needed.
1. Normally the Wasserstein distances are not very easy to calculate, hence people usually use approximation algorithms, e.g. Sinkhorn algorithms to approximate the W-distances. How does this approximation error affects the value of ESL and OMR?

2. Is there any relation between the performance of the algorithm and these two notions of complexity, either theoretically or practically?
1. This paper is well-written. The proofs are correct.

2. This paper proposes the ESL and OMR notions, which makes contribution in understanding the effectiveness of training dynamics of RL algorithms.
This paper proposes two ratios to characterize the learning pattern of RL algorithms, the ESL and OMR. ESL characterize how straight is the training trajectories, which takes smaller values if the occupancy measures admits some straight lines. OMR characterizes the proportion of trajectories which has positive effects toward the optimal policy.

This paper propose some finite-sample analysis in approximating the ESL and OMR with iid samples. They also provide numerical experiments to calculate ESL and OMR values for some popular algorithms in RL literatures.
1. The definition of OMR seems very weird. This notion is not continuous to the training trajectories, which means that the OMR value can change a lot if the model is only perturbed a little (maybe due to randomness or small approximation error). It will be good if there is a more robust notion which serves the same purpose of OMR.

2. According to the finite sample proposition (Proposition 4), the number of samples required to get a good approximation is proportional to the number of states and number of actions, which could be exponentially large for real tasks.

3. This two notions of complexity only characterize the training dynamics, but there still exist some algorithms which enjoys good performances even though the dynamics are volatile. These two notions cannot capture such properties of the algorithms.
Quantitative assessment and comparison of the exploratory processes of reinforcement learning algorithms through analysis of policy trajectories in the occupancy measure space
@inproceedings{
anonymous2024how,
title={How does Your {RL} Agent Explore? An Optimal Transport Analysis of Occupancy Measure Trajectories},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=LOiYxBcGA9},
note={under review}
}
The rising successes of RL are propelled by combining smart algorithmic strategies and deep architectures to optimize the distribution of returns and visitations over the state-action space. A quantitative framework to compare the learning processes of these eclectic RL algorithms is currently absent but desired in practice. We address this gap by representing the learning process of an RL algorithm as a sequence of policies generated during training, and then studying the policy trajectory induced in the manifold of occupancy measures. 
Using an optimal transport-based metric, we measure the length of the paths induced by the policy sequence yielded by an RL algorithm between an initial policy and a final optimal policy. Hence, we first define the *Effort of Sequential Learning* (ESL). ESL quantifies the relative distance that an RL algorithm travels compared to the shortest path from the initial to the optimal policy. Further, we connect the dynamics of policies in the occupancy measure space and regret, another metric to understand the suboptimality of an RL algorithm, by defining the *Optimal Movement Ratio* (OMR). OMR assesses the fraction of movements in the occupancy measure space that effectively reduce an analogue of regret. Finally, we derive approximation guarantees to estimate ESL and OMR with finite number of samples and without access to an optimal policy. Through empirical analyses across various environments and algorithms, we demonstrate that ESL and OMR provide insights into the exploration processes of RL algorithms and hardness of different tasks in discrete and continuous MDPs.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
reinforcement learning wasserstein distance occupancy measure exploration-exploitation effort of learning
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/7774f1798f6af8ff3aa663f1e7096246b7d10777.pdf
reinforcement learning
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
How does Your RL Agent Explore? An Optimal Transport Analysis of Occupancy Measure Trajectories
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission