Thank you for your comprehensive review of our paper. We really appreciate your kind words about the importance of our problem statement, the clarity of our writing, the quality of our theoretical results, and the value of our work to the research community. We have tried to address each point of confusion that you mentioned below:

Q6: While you asked this question last, we wanted to address this one at the onset as it is related to a few other points of confusion that you mentioned. We really like the way that you put “there is a difference between the context required to express a policy and the context available to the model.” We will update Sections 2 and 3 to emphasize this point. For example, let’s consider the irrelevant variable example from Figure 1 where it is only necessary for the policy to leverage $x$ and not $y$. Because the optimal policy only depends on $x$, this policy is included within the set of policies that only depend on $x$. However, the optimal policy is also included within the set of policies that take both $x$ and $y$ as input. Even though the functional form of this policy depends on both $x$ and $y$, the actions of this particular policy are only conditionally dependent on $x$. So regardless of the functional form used to search for the optimal policy, the optimal policy is the same in both cases. It receives the same reward rate and encounters the same mixing time. This is why we focused on $\epsilon$-optimal policies that depend on both $x$ and $y$, making the point that there are very good policies with higher mixing times than any policy that only depends on $x$. So yes, any policy that receives input that is a sufficient statistic of the environment state and trains for long enough with a principled learning algorithm will arrive at the same optimal policy. The differences is not at this theoretical asymptotic limit, but rather at the points encountered along the way. In real-world problems of sufficient complexity, arriving at the truly optimal policy is generally considered infeasible.

Convergence in Figure 3 and 4: As described above, the optimal reward rate is associated with the same optimal policy regardless of the context length and model class. As noted in the caption of Figure 3, policies with context length $k=1$ do not have sufficient context to achieve the optimal policy. However, every policy class that takes in a greater context length, does eventually achieve the same optimal policy by the end of training. What is more interesting is the mixing times associated with policies experienced along the way for each model class.

Transformers vs. MLP (Q4): To clarify all models in Figure 4 use the same context length and Figure 7 of the appendix includes a chart for each of the other context lengths. Keep in mind that we were careful to control for the number of parameters so that the architecture is the main source of variation. The comparison with MLPs is not straightforward and we should note that they do have the highest mixing times relative to Transformers when looked at across different context lengths, experiencing similar mixing times to Transformers i.e. for $k=10$. We hypothesize that these results indicate that MLPs are on average a bit less sensitive to the full context than Transformers when considered over the full course of learning.

Number of Parameters: We are not sure that we were fully able to follow this comment. Figure 9 is from experiments using the Decision Transformer architecture, which does not introduce more parameters when dealing with longer contexts due to parameter sharing within the sequence model.

Q1: Thank you for pointing this out. This was a simple artifact of our plotting library which filtered out the points at reward rates of 0.4 and 0.5 for $k=10$ just because there was a bit less data (because of slower learning). When we take out this filter, we predictably see that the mixing time is above the other context lengths at a reward rate of 0.4 and, as expected, converges to the same optimal policy mixing time as the other context lengths. We are really sorry about this mistake and will update the final draft to address this omission.

Q2: Yes. Our models train to convergence in all experiments. For our simple RGB world experiments, we did a search over Adam learning rates with gradient clipping until finding one that consistently converged at every context length. For our Decision Transformers experiments, we followed the code from the original paper, which included gradient clipping, Adam optimization, and a learning rate schedule that consists of linear warmup following by cosine learning rate decay. These details were copied from the original paper and we did a grid search over the initial learning rate. We will add these details in Appendix B.

Q3: As explained above, the optimal policy is the same regardless of the function class, so convergence of all models around a reward rate of 0.5 is expected. We hypothesize that when multiple model classes have the same reward rate and same mixing time, they are likely learning the same simple policy i.e. always go right regardless of the state. In general, all policies that do not depend on the state of the environment at all will receive a reward of 0 for this problem and would also have the minimal mixing time bound following Theorem 2. We also really like your idea to look at the state occupancy directly and will do a deeper investigation into what is learned by each model at a reward rate of 0 in the appendix of the final draft.

Q5: There is indeed no guarantee that it will always be possible to achieve a training accuracy of 100 percent with limited context. This is actually exactly the point we are trying to make in this figure. Our argument is that models like decision transformers must leverage context lengths far greater than the context lengths used for any behavior policy i.e. $k=1$ in this example.

Thank you for your detailed review of our paper. We very much appreciate your kind words regarding the originality, quality, clarity, and significance of our work. We have attempted to address your key concerns and all points of confusion mentioned in your review below.

Definitions of aperiodic and unichain: Thank you for pointing out that this can be a potential source of confusion for readers. We actually did have a relevant part of the appendix where we go through the assumptions and implications of these assumptions for the theoretical findings of our paper at the beginning of Appendix A. For example, we did discuss the implications of the unichain assumption in this section (line 478). However, we can also definitely take this opportunity to provide detailed definitions for all terminology used that we did not have space for in the main text. We will also make sure to direct readers to this section.

Proof Sketches: Thank you for your feedback on this point. We didn’t include proof sketches in the submitted draft due to space constraints, but we agree that this can greatly improve comprehension of our results for readers without expecting them to go through our detailed proofs in the appendix. You are right that the reason we mentioned the coupling time was because of its importance in the proof of Theorem 1, but we did not make this link clear enough in the main text. Likewise, the causal parent state variables play a key role in the proof of Theorem 2 and this link was not clear enough in the main text. We believe that providing these sketches is a great idea and will let us better explain to readers why we introduce some important notation, terminology, and assumptions.

Connections to $\beta$ and $g$ in Figures 1 and 6: We really like the idea to provide explicit information on $\beta$ and $g$ in the description of these figures. See below when we discuss bound tightness an example of these values for Figure 1. In section B.1 of the appendix of the submission, we did make an initial attempt to explain state variable structure of these domains, but it would definitely also be help to take it a step further to make the connection with our theoretical findings more concrete.

$\ell$ in Theorem 1: Thank you for bringing this up. We introduced $\ell$ chiefly to contrast with the prior result from Kearns and Kholler (line 153). It would indeed be better to introduce $\ell$ at this point after the theorem statement.

$k$ in Theorem 2: Thank you also from bringing this up. On a similar point reviewer kzFL also suggested that it could be useful to provide line 663 from the appendix to make the connection with $k$ clearer in the main text. We will make this clear in the statement of Theorem 2 and subsequent proof sketch in the final draft.

Reward rate hardly factors into the theory: In the theory we mostly do not mention reward rates in order to keep our results applicable to general $\epsilon$-mixing times. However, our experiments are highly dependent on the reward rate because we use the $\epsilon$-return mixing time in order to not overly focus on spurious state features. $\epsilon$-return mixing time itself is fundamentally grounded in the reward rate (line 108).

Consistency of trends in Figures 3 and 4: There is a difference between the input required to express a policy and the input available to a policy. For example, let’s consider the irrelevant variable example from Figure 1 where it is only necessary for the policy to leverage $x$ and not $y$. Because the optimal policy only depends on $x$, this policy is included within the set of policies that only depend on $x$. However, the optimal policy is also included within the set of policies that take both $x$ and $y$ as input. Even though the functional form of this policy depends on both $x$ and $y$, the actions of this particular policy are only conditionally dependent on $x$. So regardless of the functional form used to search for the optimal policy, the optimal policy is the same in both cases. It receives the same reward rate and encounters the same mixing time. As a result, the optimal reward rate in Figures 3 and 4 is associated with the same optimal policy regardless of the context length and model class. What is more interesting is the mixing times associated with policies experienced along the way for each model class.

Evidence of bound tightness: Thank you for this great suggestion. We will add an analysis of bound tightness to section 2.3 for the problems highlighted in Figure 1. In every case $\beta=0.1$. In the irrelevant variables example, $g=1$ for policies that only condition on $x$, and $g=2$ for policies that condition on both $x$ and $y$. As a result, the bound should be 10 times tighter for the set of policies that only condition on $x$ than the set of policies that condition on both $x$ and $y$. In practice the maximum $\epsilon$-return mixing time is 7.6 times smaller. In the independent subtasks example, $g=2$ for policies that always condition on $x$, $y$, and $z$. Meanwhile, $g=1$ for policies that focus on the relevant variable $x$ or $y$ depending on the value of $z$. So the bound should once again be 10 times tighter, but the maximum $\epsilon$-return mixing time is 3.6 times smaller in this case. One reason that we believe these bounds are not as tight as possible for this experiment has to do with using the $\epsilon$-return mixing time that is not sensitive to state changes that don’t have an impact on the reward. In these examples, we adopted a simple sparse reward where many states get a reward of 0. For the final draft we will also include a variant of the experiment where the reward is set to be different at each state such that the Markov chain over states must fully mix for the $\epsilon$-return mixing time to also mix. We expect that this setting will verify these bounds to be even significantly tighter than what we have measured here in practice.

Thank you for your thoughtful review of our paper. We appreciate that you highlighted our theoretical contribution and want to thank you for your praise regarding the writing quality and empirical verification of our theoretical results. Below we have tried to provide clarity regarding each of your questions in the weaknesses section. We hope that you will consider raising your score if we have adequately addressed your concerns.

Question 1: Thank you for pointing out your confusion regarding $\beta$ and $g$ in Figure 1. In the lines between 180 and 213 we went over the main facts needed to derive these terms in combination with the figure caption, but you are definitely right that it is much better to state them clearly as readers will not be as familiar with this kind of analysis and may find it difficult to follow along. In every case $\beta=0.1$. In the irrelevant variables example, $g=1$ for policies that only condition on $x$, and $g=2$ for policies that condition on both $x$ and $y$. In the independent subtasks example, $g=2$ for policies that always condition on $x$, $y$, and $z$. Meanwhile, $g=1$ for policies that focus on the relevant variable $x$ or $y$ depending on the value of $z$. We will be sure to substantially update this section in the final draft to eliminate any potential confusion.

Question 2: Thank you for mentioning that line 243 was confusing. Our motivation for introducing the prime notation was simply to draw a distinction between the parametric class of policies over the state space $\theta’ \in \Theta’$ and policies over interaction history windows $\theta \in \Theta$. The point being that the set of possible policies are not the same or directly comparable due to the different functional form resulting from different input spaces. We will add a footnote to the final draft to clarify this point.

Question 3: Thank you for this insightful comment highlighting this potential area of confusion. We will definitely include this context about how $\beta_k$ and $g_k$ evolve with $k$ from line 663 of the appendix in the main text to better explain Theorem 2. We should not have assumed readers will figure this out themselves as this provides unneeded cognitive load when interpreting Theorem 2 and we want the results to be easily accessible to as wide as audience as possible.

Question 4: Thank you also for you comment about visualizing attention maps to validate our conclusion on line 286. This is a really fabulous suggestion in order to validate whether this intuition we presented actually is consistent with the results. Unfortunately, we did not log data related to attention when we conducted these experiments and doing so will require us to rerun the experiments highlighted in Figure 8 from scratch. This corresponds to 1,000 individual experiments with specific seeds, requiring significant computational resources and time. For the final draft we will rerun these experiments while keeping track of the average attention attributed to each element of the interaction history window across the 8 heads in each layer. It will be interesting to see if the spread of attention is indeed more even on average for Transformer models that experience higher average mixing times. Theorem 2 shows theoretically that what leads to potentially high mixing times is when our model is highly sensitive to a large part of the interaction history at all times. Following from this insight, it seems natural that we may see higher mixing times for Transformers than LSTMs and for bigger Transformers than smaller Transformers. However, we definitely agree that this conclusion will be much stronger if each element of this hypothesis is empirically validated. We really appreciate this suggestion and are excited about being able to provide more clarity about the mechanisms at play in Figure 8 for the final draft.

Please let us know if we can provide any further clarity regarding any of these points during the discussion period.

Thank you for participating in the discussion period and for your constructive feedback that we believe has helped improve our paper. We were wondering if you could clarify further about what concerns regarding the presentation and experiments of our paper still remain after our response to your review. We just ask because many of your comments, especially regarding the presentation, seemed straightforward for us to address. We want to make sure that we understand how our paper can be improved to address your recent feedback.

We wanted to begin by thanking you for the kind words in your review regarding a number of aspects of our paper including the novelty, comprehensive empirical analysis, and writing quality. We really appreciate this validation of our work. We also wanted to make sure to engage with all of your concerns and suggestions.

Experiments in Appendix: We definitely agree that space limits us in being able to provide our experiments in the main text, but we do feel that it should be possible to provide a concise overview of the key findings in the space limitations of a standard conference paper. This would allow us to reach the biggest audience possible (given that a much smaller community would be interested to read through an extended version). We were wondering if there were any experiments in particular that you felt would make a significant addition to the main text. If so, we would be happy to see if the paper could be restructured to accommodate for this.

Possible Architectural Changes: We really appreciate this question as it cuts to the chase of the core motivations of our work. Most work on RL that even acknowledges the challenges of high mixing times does so with a defeatist mentality, assuming that problems with high mixing times are unavoidably harder and that there is basically nothing that could be done about it. If our work makes any contribution to the community, we hope it will be to highlight that this isn’t actually true and that the policy class we choose to optimize over itself can have a big impact on mixing properties. We hope that readers of our paper come away from it asking exactly the question that you did. What our paper shows in Theorem 2 is that what leads to potentially high mixing times is when our model leverages a monolithic representation that is highly sensitive to a large part of the interaction history at all times. This is particularly descriptive of how generic transformers work, but there are multiple already existing research directions that seem well suited to scaling to high context lengths while providing less history sensitivity at each step:

• Hierarchical RL: In hierarchical RL frameworks such as options [1] it should be possible in domains with temporal coherence to approximate a policy with a longer context length by multiple sub-policies with a smaller context length. This is particularly relevant for approaches to option learning that learn an independent lower dimensional representation space for each option as in [2].

• Hybrid Transformer Working Memory Architectures: Recent work has aimed to improve the effective context length of transformers by augmenting them with some kind of bounded working memory component [3, 4, 5]. While these papers are typically solely motivated by computational efficiency, they effectively serve the role of extending Transformers to longer contexts while making them less sensitive to experiences in this context that are not reflected in the memory. This effectively bring Transformers closer to some of the incremental design patterns of RNNs, which our experiments indicate experience lower mixing times. This makes sense because they must commit to a single representation of the history at each step and do not have the capability to constantly reassess their history representation dynamically as the context changes the way Transformers do. As such, even state-space models [6, 7, 8] or hybrid alternatives could be attractive in achieving the performance of Transformers while potentially alleviating mixing time concerns during learning.

• Tracking Policies: If we aim to learn a non-stationary tracking policy solution concept as argued by [9] we could potentially represent a stationary policy over a longer context length with a non-stationary set of small context length policies. In effect, this becomes similar to what is achieved by the hierarchical RL policies described above. One additional subtlety to highlight in this case is that this solution is also limited by the mixing properties of the tracking policy parameters, so it would also be necessary to tune this approach to move through parameter space as fast as possible.

We will make sure to add this additional detail into the discussion section of the final draft where possible.

[1] Sutton, Richard S., Doina Precup, and Satinder Singh. "Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning." Artificial intelligence 112.1-2 (1999): 181-211.

[2] Abdulhai, Marwa, et al. "Context-specific representation abstraction for deep option learning." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 6. 2022.

[3] Pham, Kha, et al. "Generative pseudo-inverse memory." International Conference on Learning Representations. 2022.

[4] Das, Payel, et al. "Larimar: Large Language Models with Episodic Memory Control." Forty-first International Conference on Machine Learning. 2024.

[5] Munkhdalai, Tsendsuren, Manaal Faruqui, and Siddharth Gopal. "Leave no context behind: Efficient infinite context transformers with infini-attention." arXiv preprint arXiv:2404.07143 (2024).

[6] Gu, Albert, and Tri Dao. "Mamba: Linear-time sequence modeling with selective state spaces." arXiv preprint arXiv:2312.00752 (2023).

[7] Dao, Tri, and Albert Gu. "Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality." arXiv preprint arXiv:2405.21060 (2024).

[8] Samsami, Mohammad Reza, et al. "Mastering Memory Tasks with World Models." The Twelfth International Conference on Learning Representations. 2024.

[9] Sutton, Richard S., Anna Koop, and David Silver. "On the role of tracking in stationary environments." Proceedings of the 24th international conference on Machine learning. 2007.

Thank you for engaging with the review. I believe adding the discussion on architectural changes to the paper is essential. I think that space could be better used through subfigures so that Figure 5 and Figure 8 could be placed side by side, for example. I will stick to my original score.

Thank you for taking the time to review our paper. We are sorry to see that you are so negative about the value of our contributions to the community. We believe that there are some key points of confusion that may have led you to this perspective that we will attempt to address below. We will also reference other reviews when helpful to contrast with other perspectives on our paper.

Our contribution: After reading through your summary of our contributions, we would like to clarify a potential confusion about the novelty of our results. Our result in Theorem 1 does indeed provide a tighter bound on a prior result, but this is only an intermediate result of our paper necessary for proving Theorem 2, which is our main contribution. Theorem 2 is entirely novel. We are not aware of any paper from the prior literature that has even mentioned the fact that the context length of the interaction history sent to a policy would have an impact on its mixing time. When the reviewer writes “I merely wonder how this direct observation needs a (tighter) upper bound,” the answer is that the tighter bound of Theorem 1 is essential for being able to prove the novel result of Theorem 2.

Trivial observation: This comment seems at the heart of your criticisms of our paper. As such, we will attempt to break down your argument piece by piece to provide you with clarification on why this may be much harder to show than you realize. The first aspect of your argument “As the context length is increased, we increase dimensionality of the problem” requires some immediate clarification. Often in RL when we talk about “the dimensionality of the problem,” we are talking about the size of the environment. However, increasing the context length sent to a policy has no direct impact on the environment. Indeed, prior work at this conference [1] has established that as environments are scaled up, their mixing time also increases. We must reiterate though that the environment is not scaled up when the context length is increased, so this result is not at all related to our theoretical contribution. The reviewer also mentions that increasing the context length “increases the cardinality, so the reviewer doesn't find this result of any significance.” The cardinality that is being increased here is the set size of the possible interaction histories $h^{(k)}_t$. But we do not see how the reviewer jumps from the fact that this set size is increasing to the fact that the mixing time is going up. Notice that this $\epsilon$-mixing time is defined in terms of states and not observations, so it is not obvious that an input that does not explicitly include the state being sent to a policy will impact the $\epsilon$-mixing time. We know that the reviewer mentioned not looking through the appendix, but the proofs of Theorem 1 and 2 are not direct results of cardinality arguments, rather they have to do with the underlying causal structure of the Markov chain induced by the policy in the environment. If the reviewer has a better idea of how to show this result in a trivial way that goes beyond a vague intuition, we would kindly request that they spell it out in more detail. As suggested by reviewer hXkG, we will provide proof sketches to aid comprehension in the main text of the final draft.

Bound Tightness: As other reviewers also suggested, in the final draft we will add an analysis of bound tightness to section 2.3 for the problems highlighted in Figure 1. In every case $\beta=0.1$. In the irrelevant variables example, $g=1$ for policies that only condition on $x$, and $g=2$ for policies that condition on both $x$ and $y$. As a result, the bound should be 10 times tighter for the set of policies that only condition on $x$ than the set of policies that condition on both $x$ and $y$. In practice the maximum $\epsilon$-return mixing time is 7.6 times smaller. In the independent subtasks example, $g=2$ for policies that always condition on $x$, $y$, and $z$. Meanwhile, $g=1$ for policies that focus on the relevant variable $x$ or $y$ depending on the value of $z$. So the bound should once again be 10 times tighter, but the maximum $\epsilon$-return mixing time is 3.6 times smaller in this case. One reason that we believe these bounds are not as tight as possible for this experiment has to do with using the $\epsilon$-return mixing time that is not sensitive to state changes that don’t have an impact on the reward. In these examples, we adopted a simple sparse reward where many states get a reward of 0. For the final draft we will also include a variant of the experiment where the reward is set to be different at each state such that the Markov chain over states must fully mix for the $\epsilon$-return mixing time to also mix. We expect that this setting will verify these bounds to be even significantly tighter than what we have measured here in practice.

Adding Knowledge to the Field: We should note that reviewer FWjm also felt that the result in Theorem 2 was intuitive, but thought it was still a contribution to provide the formal analysis and that it was interesting to link context lengths with mixing times. Reviewer LbpG also felt that the contribution was significant. Likewise, reviewer hXkG felt that the contribution had a high degree of significance and that the paper’s biggest strength was its potential influence on subsequent work because its insights are timely. Moreover, reviewer aEyh praised our new angle at an important and interesting problem, remarking that the “community will benefit from this work being available to them.”

Insights from Evaluation: Again we should note that reviewer FWjm called our evaluation convincing and reviewer LbpG felt the experiments were comprehensive.

[1] Riemer, M., Raparthy, S.C., Cases, I., Subbaraj, G., Puelma Touzel, M. and Rish, I. “Continual learning in environments with polynomial mixing times.” Advances in Neural Information Processing Systems, 2022.

We wanted to begin by thanking you for your thoughtful review of our paper. We really appreciate your praise of the implications of our theoretical findings, the evaluation of these findings, and the writing quality of our paper. We also found your intuitive explanation of our findings to be quite insightful. We really like the way you put it and will be sure to reference this kind of explanation in the final draft.

Confusion Regarding Figure 9: Thank you for pointing out to us how confusing this was in our submission. What wasn’t clearly articulated in our description from lines 316 to 317 was that this experiment was really motivated as a response to a particular potential criticism of our analysis in section 4. One could potentially argue that while a larger context length is needed to fit the set of behavior policies than each had individually, this is simply “overfitting” to the training data and not useful in achieving downstream performance. Our intention in Figure 9 is to provide a concrete counter example to refute this argument. What we believe must have made this even more confusing is that our main point in Figure 9 could only be understood by reading the in-text descriptions of the training accuracy at each context length value. In the final draft, we will update the label to include the training accuracy corresponding to each value of $k$. Figure 9 then chiefly shows that the models with the best generalization have 100% training accuracy. You are also right that another trend highlighted in Figure 9 is that $k$ values that are unnecessarily large seem more prone to overfitting, which isn’t very surprising. We believe these points are interesting to highlight, but also acknowledge that they are only indirectly connected to mixing times through the findings of our paper and simply serve as supporting evidence for the need for growing the context length when building foundation models.

Practical Impact: Thank you for mentioning your confusion about the relevance of high mixing times and our analysis in practice. We believe the settings of greatest relevance to our work are those related to continual or multi-task environments where agents are evaluated as generalists over a number of skills rather than just solving a single narrow task. As such, we believe that focus on the difficulties presented by high mixing times is timely in the age of foundation models. As mentioned at the end of section 3.1, our analysis will not have relevance in problems where there are few state variables that each impact every observation. However, composite tasks that test a number of sub-skills naturally tend to have many total state variables with relatively few impacting each observation. So, for example, simple Atari domains such as Pong and Breakout will not suffer from high mixing times, but i.e. continual learning over multiple Atari games including Pong and Breakout will as a result of the sparsity of causal impact of variables across games. Another example would be open world environments that feature a number of natural sub-tasks and sub-regions such as RPGs like the Pokémon series of games or the Legend of Zelda games. Moreover, broadly speaking AI assistant tasks that include providing help on a number of topics rather than just one should also suffer from issues with high mixing times. We will provide more detail along these lines in the final draft. In the submitted draft, we wanted to prioritize focusing on our novel results, but it probably would help readers to contextualize our analysis more deeply with recent prior work on this topic such as [1]. In this paper it was shown why continual learning tasks with multiple subtasks have high mixing times and in-depth experiments on mixing times were conducted for the Atari games. It was found that the common setting in the literature results in practical $\epsilon$-return mixing times on the order of 10 billion time steps even when only considering 6 Atari games. [1] also argues theoretically how high mixing times are a primary driver of poor performance and training instability on continual learning tasks. In light of these prior results in the literature and the complexity of analyzing large scale and long horizon games, we opted for smaller scale experiments in our paper to allow for greater control and more interpretable insights.

[1] Riemer, M., Raparthy, S.C., Cases, I., Subbaraj, G., Puelma Touzel, M. and Rish, I. “Continual learning in environments with polynomial mixing times.” Advances in Neural Information Processing Systems, 2022.

Thank you for your question. Intuitively, what we meant was $\rho(\pi, s_0, m) := E_\pi[\frac{1}{m} \sum_{t=1}^m r_t | s_0]$. Maybe it would have been clearer if we used the term reward rather than return?

The $\epsilon$-return mixing time was first proposed in [1] with the authors defining an analogous term to $\rho(\pi,s_0,m)$ in their different notation using definition 4 as well as equations 3 and 5 to accomplish this (see https://www.cis.upenn.edu/~mkearns/papers/KearnsSinghE3.pdf). Their definition is more formal than what we provided above. They begin by defining what they call a $T$ path in the MDP i.e. a particular $T$-step path within the MDP. $T$ here is analogous to what we call $m$ in our paper. Then they define the average undiscounted return per step along that $T$ path in equation 3. This allows them to define a term analogous to $\rho(\pi,s_0,m)$ in equation 5, which is the expected average undiscounted return per step where the expectation is taken over the likelihood that a particular $T$ path is executed by the policy $\pi$ from the starting state $s_0$.

We appreciate you raising the potential confusion regarding $\rho(\pi, s_0, m)$ to our attention and will definitely include a definition in the final draft of our paper. We were hoping to ask your opinion on which of these two ways of writing it you feel would be most appropriate. The approach from [1] is definitely more formal and descriptive of how it is measured in practice. On the other hand, we also worry about bogging the readers down in notation like the notion of paths through the MDP, which could distract readers from our main contributions.

[1] Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, 49(2):209–232, 2002.