Non-ergodicity in reinforcement learning: robustness via ergodic transformations

We thank the reviewer for the positive evaluation of our contributions and for acknowledging the “fresh perspective” our paper provides.

Problem description. We have thoroughly revised the problem setting section and think that now it is clearer how ergodicity connects to RL and, especially, what is the relation between ergodicity of rewards and returns.

Variance function. We follow the standard definition of the variance function. For instance, from https://en.wikipedia.org/wiki/Variance_function: a smooth function that depicts the variance of a random quantity as a function of its mean. We have now added this definition to the paper.

Contribution. The algorithm we propose in this paper is a first step toward resolving an issue that will require much further study to resolve completely. As we show in the paper, state-of-the-art RL methods already fail for a very simple example. This indicates that for non-ergodic environments if we care about the long-term performance of agents, the expected value might not be the best optimization objective. We then propose a transformation that resolves the problem in the simple example. We further demonstrate that it extends to more challenging problem settings. REINFORCE is a Monte-Carlo-based algorithm. As such, it collects a reward trajectory and uses this to update its weights. Thus, we receive a reward trajectory in every episode, can learn a transformation, transform returns, and optimize based on transformed return increments. Thus, in Monte-Carlo-type algorithms, our transformation can already be used. Clearly, an extension to an incremental transformation would be important to apply it more broadly.

Experiments. In the reacher example, we also receive rewards in the beginning, even though they are low. This is apparently enough to get at least a rough idea of the dynamics, and the transformation can provide a better optimization objective than the standard expected value.

Figure 1. We followed your suggestion and now show the red and blue lines as dashed lines to distinguish them more clearly from the others.

Thank you for critically reviewing our paper and acknowledging the importance of the problem we address.

Problem description. We have thoroughly revised the problem setting section to define the concept of ergodicity more clearly. We are here using an subscript $k$ on the time $t$ to clarify that we are considering discrete time steps and to distinguish it from the continuous-time analysis we do when comparing our contributions to risk-sensitive reinforcement learning.

Connections to related work. The main contribution of this paper is raising the question of ergodicity of reward functions in RL and how it impacts the use of the expected value as an optimization objective, as well as proposing a first approach toward resolving the problem. Other approaches that we are aware of consider non-ergodicity of MDPs but do not make the connection to the divergence between expected rewards and long-term rewards in such settings. Majeed and Hutter prove that the Q-learning algorithm still converges under non-ergodic dynamics. In the coin-toss game, the PPO algorithm also converges. And it does converge toward the policy that yields the maximum expected return. However, this policy yields a return of 0 in the long run with probability 1. Convergence itself does not necessarily help if the optimization objective is the problem.

Risk-sensitive RL. As we discuss in Section 5, for a specific class of reward functions (logarithmic), the risk-sensitive transformation is an ergodicity transformation. For such settings, the risk-sensitive transformation does exactly what we propose to do in this paper. This is not the case for other classes of reward functions - which is intuitive: a fixed transformation should only work well for a class of reward functions and not for all potential classes one could think of. We used the risk-sensitive transformation in the coin-toss game, whose dynamics are exponential, i.e., opposite from what the risk-sensitive transformation would need. In this case, the transformation fails.

We thank the reviewer for emphasizing the potential of our contributions. In this paper, we identify a problem that so far seems unaddressed and even unnoticed in reinforcement learning. Through an intuitive example, we show the implications of neglecting non-ergodicity has for state-of-the-art RL algorithms. We then develop a Monte Carlo algorithm that can solve the problem. We further provide theoretical foundations for the area of risk-sensitive RL. Overall, this is a significant set of contributions. Especially the presentation of the paper has been positively recognized by other reviewers.

We thank the reviewer for acknowledging the novelty and potential of our approach.

Ergodicity notions. In the RL literature, ergodicity is typically defined as the existence of a finite $N$ such that any state in the Markov chain can be reached from any other state in at most $N$ steps. We could now also understand the coin-toss game as a Markov chain, where the different states in the chain would represent the “wealth” of the agent. As long as we consider finite episode lengths, a finite path exists from any starting state to any other state in the chain. Nevertheless, in the limit, the agent will end up in an absorbing state (wealth equal to zero) with probability one. Thus, in the limit, due to the existence of an absorbing state, the game would also be non-ergodic from the MDP perspective. On the other hand, a non-ergodic MDP, which, for instance, has an absorbing state in which we end up with non-zero probability, should, in general, also be non-ergodic from the reward perspective. This is because, in the infinite time limit, we will end up in the absorbing state with probability 1. A case where the two definitions would not coincide would be if we define the reward dynamics themselves to follow a geometric Brownian motion while the agent moves in a grid world in which all states can be reached or if we have a grid world with absorbing state where all states, including the absorbing one, give the same reward. However, typically, ergodicity of the MDP should imply ergodicity of the reward function and vice versa.

Notation. We agree that the notation has not been clear enough in the submitted version, and we have thoroughly revised it, also defining more clearly what we mean by ergodicity and how exactly it relates to RL. The reward typically depends on the current state and action. I.e., we have $r(a(t_k), s(t_k))$. We abbreviate this for conciseness as $r(t_k)$, as we now define in the paper.

Expectation. Given a stochastic environment, such as in the coin-toss game, a policy induces a stochastic process. The expected return then gives us a measure of how good this policy is. So conventionally, in RL, we would maximize over policies to find the one with the highest expected return. In that sense, we take the expected value over trajectories induced by a certain policy.

Action space. In Section 2.1, the action space is the discrete decision of playing or not playing the game. Since not playing it results in no change in wealth, in Figure 1, we show the dynamics if one decides to play the game.

Variance-stabilizing transform. The problem that this work attempts to solve is how to estimate a function that transforms a given time-series into one with ergodic increments. There is no established measure of how ergodic a time-series is, so instead, we take the approach of using a proxy metric, that is a metric that is easier to measure and still results in a transformed time series with ergodic increments. This motivates our choice of the variance-stabilizing transform as (assuming the incremental mean has no underlying trend) if the incremental variance of a random process is constant, then it will have ergodic increments. Of course, there is a class of random processes that have ergodic increments but varying incremental variance. A consequence of our proxy measure approach is that we cannot make any inferences on these processes.

Ito process. Equation (4) assumes that the reward function is an Ito process. This is a very general type of stochastic processes, as the two functions $f$ and $g$ can be nonlinear or even stochastic. It is also used more as an analysis tool. We state for which underlying Ito process the risk-sensitive transformation would be an ergodicity transformation and find that we can get valuable insights from this perspective.

Experiments. In the experiments, we see indeed that the improvements for the cart-pole are only modest. This implies that either the reward function is ergodic or that the difference between the time average and expected value is relatively small so it does not show too clearly in the experiments. For the reacher, on the other hand, we see a clear improvement.

We thank the reviewer for the overall positive evaluation of our paper and for acknowledging our core contribution as “intriguing and well-founded.”

Notation. The variable $t_k$ in our paper indeed represents the time step. We here added the indice $k$ to clearly distinguish it from the $t$ in Section 5, where we consider a continuous-time setting. Figure 4 shows the return for the cart-pole and reacher experiments at $t_k=T$ over the number of episodes. The parameter $T$ has also in the problem setting been defined as the duration of an episode.

Different distributions. We focus our analysis on one particular example for which we know that the rewards are non-ergodic and show that state-of-the-art reinforcement learning algorithms cannot solve it - despite the simple dynamics. The fact that even such a simple example can pose severe challenges for established methods should be a good reason to re-evaluate the usage of the expectation operator for highly complex environments where RL is usually applied. In Section 6, we discuss in more detail for which types of reward functions our ideas are most important. Apart from non-ergodic stochastic processes, we particularly highlight environments where we have an absorbing barrier. We can often find such settings in safe learning settings where reaching forbidden states, e.g., a robot crashing into an obstacle, automatically ends the episode. A risky policy, for which there is a non-zero probability of reaching the forbidden state when rolled out many times for a short duration, might now, on average, yield a high reward, as it only sometimes crashes. However, if we let the same policy run for a long time, we will almost surely eventually reach the forbidden state. Thus, also here time average and expected value do not coincide, and, for the sake of robustness, we might want to go for optimizing the time average.

Cart-pole example. In the cart-pole environment, the differences between the runs are only modest. This suggests that the cart-pole environment is either ergodic or that the non-ergodicity here plays a less significant role. For a non-ergodic process, time average and expected value are different, but they may still be close to each other. For the reacher, this apparently does not hold. The difference between testing and training is because we change the link length, as we also mention in the corresponding section.

Benefits of our method. The ergodicity transformation guarantees that we focus on maximizing the long-term growth rate of the return. Given an ergodic reward function, this is identical to the expected growth rate. Thus, given an ergodic reward function, using or not using the transformation makes no difference. Given a non-ergodic reward function, this does not hold any longer. Then, it depends on whether we care more about the long-term performance or the performance averaged over many trials. In the former case, the ergodicity transformation is beneficial.

We thank the author for highlighting the “totally novel perspective” that our paper might bring to most of the ICLR audience. This is indeed where we see a major contribution of this work: posing the question of non-ergodicity in reward functions and what could then be alternatives to relying on the maximization of expected rewards.

Application of risk-sensitive transformation. The risk-sensitive transformation we discuss in the paper has been applied in various works, for instance, Prashanth et al. 2022, Noorani et al. 2022, and Fei et al. 2021. As this transformation is not a contribution of our paper, we did not provide a successful example ourselves. Instead, we wanted to show that the risk-sensitive transformation is an ergodicity transformation given a specific form of reward function. However, when the reward dynamics are very different from this form, as in the coin-toss game, such fixed transformations fail. Therefore, a more generic approach, such as the transformation we propose, is required.

Discounted rewards. Using discounted rewards does not pose an issue, and for the REINFORCE examples, we also used a discount factor, with which the transformation works equally well. As we point out in the conclusions, the ergodicity perspective can also motivate or rather explain certain choices of discount factors and how they decrease over time. Here, we focused on the relationship between (non-)ergodicity and the expectation operator. However, examining more thoroughly which insights this perspective can bring to the choice of discount factor will clearly be a topic for further research.

Infinite length of trajectories. When choosing a policy that optimizes the expected value, we choose a policy that would be optimal if we would roll it out infinitely often, which, in practice, we can never do. Similarly, when optimizing the time average, the policy we choose would be optimal if we roll out the policy once but for infinite time. Also this, we cannot do in practice. Thus, in both cases, what we optimize differs from what we do in practice. The question is which one is closer: Are we, in the end, interested in what happens on average when we try the policy many times or when we try it once but for a long time? Depending on the answer, we should choose our optimization objective. We are also not arguing to abandon the expected value completely. In a swarm robotics setting, the average performance over all agents in the swarm might be what we care about - then optimizing the expected value would be a good choice.

Dynamics. Exponential dynamics are nice to consider in this setting since a widely used stochastic process exhibits such dynamics (geometric Brownian motion), and we can find closed-form solutions. The logarithmic dynamics come from a transformation widely used in risk-sensitive reinforcement learning. Nevertheless, for other dynamics, such transformations can be found as well. In the paper of Peters and Adamou from 2018, the authors also investigated square-root dynamics, for which a transformation can be found in a similar way.

Challenges. We list some challenges in the conclusions of the paper. Our current transformation requires a trajectory from which it can learn the transformation. This limits us to Monte-Carlo-type approaches. Extending this to an incremental transformation and then integrating this into the RL algorithm we would see as a challenging but essential next step.