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

Authors: Reabetswe M. Nkhumise, Debabrota Basu, Tony J. Prescott, Aditya Gilra
Primary area: reinforcement learning
Keywords: reinforcement learning, wasserstein distance, occupancy measure, exploration-exploitation, effort of learning

Abstract:
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.

Decision: reject
Reviewer scores: 6, 3, 6

Reviews and discussion:
<thread>
creation date:
1729728715564

thread_type:
official_review

<thread_object>
creator: reviewer_rcfe

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730663530705

thread_type:
official_review

<thread_object>
creator: reviewer_yman

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731000113331

thread_type:
official_review

<thread_object>
creator: reviewer_ghmn

<content>
summary:
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.

strengths:
- 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.

weaknesses:
- 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.

questions:
- 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731956640283

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Utility of proposed metrics : ESL and OMR are complementary to regret and number of policy updates

comment:
We would like to thank the reviewers for acknowledging the strengths of the contribution as well as for their thoughtful comments and efforts towards improving the manuscript. In the following, we highlight general concerns of reviewers. We then address comments specific to each reviewer by responding to them directly.

**Concerns:**

- *Reviewer GHMN:* The practical utility of the proposed metrics is unclear.
- *Reviewer yMaN:* What information do ESL and OMR provide about the learning process beyond that provided by sample complexity / UC and regret?.


**Response.** In ICML 2018, Exploration in RL workshop (https://sites.google.com/view/erl-2018/open-problems) posed the lack of metrics to quantitatively evaluate different exploration methods as an open problem. The reason is that quantities like regret and number of updates (UC) are outcomes of the exploratory processes, and thus reflect only a partial view of the underlying exploration mechanisms. We propose ESL and OMR to complement regret and number of updates as metrics but not to replace them.

**1. Complementarity of ESL and OMR with respect to UC:** 

a. **Case 1.** Let us consider two RL algorithms that reach optimality with the same number of updates, i.e. they have the same UC. How would one be able to distinguish the exploratory processes of these algorithms? ESL and OMR are the summary metrics of the policy trajectory during learning (Figs. 1 \& 2). These can reveal which algorithm's exploratory process is more direct versus meandering, smooth versus noisy, or has large versus small coverage area in the policy space (Figs. 3 \& 4, top rows). Therefore, *ESL and OMR quantify with granularity the characteristics of the exploratory process of an RL algorithm for any given environment.* 

b. **Case 2.** Let us consider the case when optimality is not reached but the maximum number of updates is attained by two RL algorithms. How would one be able to evaluate the exploratory processes of these algorithms and systematically uncover which exploratory process demonstrate desired characteristics? Looking into the training trajectories of RL algorithms in an environment and corresponding higher/lower ESLs ($\eta_{sub}$, Sec 4.2), we can make a knowledgeable choice of an RL algorithm exhibiting desired characteristics (e.g. high coverage, smooth exploration). We have shown in Sec 4.2 and results in Appendix B.5 that ranking based on suboptimal ESL is aligned with true ESL, and additionally, the visualisation of the training trajectories (Figs. 3 \& 4) can indicate the characteristics of corresponding RL algorithms even when optimal policy is not reached. 

c. **Experimental Evidence.** UCRL2 is known to be provably regret-optimal and is designed to continuously explore. SAC does not have such rigorous theoretical guarantees but is known to be practically efficient. In Table 1, by UC, we observe that SAC is significantly suboptimal than UCRL2. But SAC has lower ESL than UCRL2 as its exploration is smoother. Additionally, OMR for SAC is higher than that of UCRL2. They together indicate that SAC takes smoother but larger number of policy transitions aligned to optimal direction for exploration, while UCRL2 exhibits bigger policy changes and in diverse manner trying to cover the environment faster.

**2. Complementarity of ESL and OMR with respect to Regret.** UCRL2 and PSRL have the same order of regret bound [1]. But PSRL leads to smoother policy transitions that are much more orientated towards optimality (as shown in Fig 3), while UCRL2 leads to less smooth policy transitions that do not taper as it approaches optimality. This information is not evident from regret but from corresponding ESLs and OMRs (Table 1). 

**3. Insights for Algorithm Design.** Knowing ESL (or suboptimal ESL) and OMR can assist with developing algorithms that emphasize certain exploratory characteristics. We can develop algorithms with grades of coverage or directness, while also being able to visualize this. Ultimately, depending on the environment, we can choose which characteristics of exploratory process are well suited. In contrast, looking only at the final outcomes of RL algorithms like regret and number of updates does not include these nuances. 

We will include a summary of above points in the Discussion in the updated version, and upload it before the end of the Discussion period.

[1] I. Osband, B. V. Roy, and D. Russo. (more) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, pp. 3003—-3011, 2013.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732293793946

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Updated pdf of paper. Looking forward to discussion.

comment:
We hope that our responses address the reviewers' questions. We have also updated the pdf (uploaded in openreview) in line with what we mentioned in our responses.

If our answers address your concerns affirmatively, we hope you would reconsider your assessment. If you have any further questions or comments, we are looking forward to discussing further.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces the Effort of Sequential Learning (ESL) and Optimal Movement Ratio (OMR) metrics to analyze the learning dynamics of reinforcement learning (RL) algorithms by examining the trajectories of state-action occupancy measures. The paper provides theoretical results and empirical evaluations on standard RL environments like gridworld and MountainCar.

The paper is well-written, and the introduction of ESL and OMR offers a novel perspective on RL training dynamics, moving beyond traditional metrics like sample complexity and regret. However, several concerns were raised by reviewers. The primary issue is the robustness of OMR, which is highly sensitive to small changes during training, making it unreliable in practice. Additionally, ESL and OMR are not well-aligned with learning efficiency or performance metrics, casting doubt on their practical utility. The paper also lacks a clear connection between these metrics and the overall performance of RL algorithms. Further, the finite-sample proposition suggests that the number of samples required to approximate ESL and OMR could be excessively large in real-world tasks.

The paper would benefit from addressing these concerns, particularly by refining the OMR definition for robustness and improving the alignment of ESL and OMR with actual learning efficiency. Additionally, more concrete examples showing the practical applicability of these metrics in RL tasks are needed. Though the paper’s contributions are valuable, the usefulness of ESL and OMR remains unclear without further refinement and demonstration of their relevance to algorithm performance.