Revisiting Familiar Places in an Infinite World: Continuing RL in Unbounded State Spaces

Thank you to the reviewer for their comments and questions. Thank you for acknowledging that addressing these problems is important if we want to make progress towards making RL more applicable to real-world settings.

Weaknesses

Re: cited work

Thank you for pointing out this work. We will include it in the related work sections. The work you cite is actually a deep RL version of the work by [1] that we already cite in our paper. Our comments in the related work section for [1] also apply to this new work you mention: “they assume that a stable policy is given and use it as a starting point for learning an optimal policy. We make no such assumption and try to learn a stable policy directly from a random policy”. We would expect methods that have access to a stable policy to perform competitively, but the main point is that we cannot always rely on access to a stable policy, and in this work, we explore the setting without access to this fixed stable policy.

Questions

Re: exploration vs. stability

Thanks for the question. In the class of problems we consider (see our global response), we actually want the agent to explore only in states with low norms since those correspond to low-cost states. If the agent explores in states with high norms, it incurs a high-cost penalty. STOP still encourages exploration (by inheriting PPO’s exploration strategy of sampling actions based on the logits outputted by the policy), but in low-norm/low-cost states.

Re: scheduling lambda

We set the lambda schedule as described in Section 4.2. This schedule was taken from [2]. The schedule does not interact with the exploration parameter.

Re: unbounded in real world

We understand this point. We acknowledge this in the footnote on page 1. Moreover, in the traffic control description in Section 5.1, we say: “ In this domain, SUMO models a real-life traffic situation by imposing a cap on the number of cars per lane. However, as we will show, existing deep RL algorithms still fail despite this cap”. Thus, the challenges in the unbounded state space arise even in the bounded state space setting where the bound is high.

In general, a bounded state space with a high bound is not substantially different from an unbounded state space, especially in multi-dimensional problems. An unstable policy will diverge towards the boundary of the state space instead of towards infinity; see Figure 2 (d)-(f). In contrast, our approach can quickly learn to maintain the system in low-cost states and away from the boundary.

Re: problem-specific

Yes, we acknowledge this point. We do want to point out that a linear stability cost $\ell(s) = \|s\|$ is sufficient for achieving stability in most of our environments. We need to use the reciprocal stability cost only in a highly stochastic queue environment. Also, using a simple quadratic stability cost $\|s\|^2$ (inspired by domain knowledge from control theoretic and queueing problems) is sufficient in ALL our environments.

We can think of adjusting the cost function as introducing domain knowledge, which is common in many RL approaches for real-world tasks. In our case, and as mentioned in Section 5.2, we made the adjustment based on relative magnitude scales between the optimality and stability cost.

Re: evaluation environments.

The experiments were conducted on simulators that share properties of the real-world task. In the appendix (section B), we include a description of the real-world setting in queueing and traffic control.

[1] Bai Liu, Qiaomin Xie, and Eytan Modiano. Rl-qn: A reinforcement learning framework for optimal control of queueing systems

[2] James MacGlashan, Evan Archer, Alisa Devlic, Takuma Seno, Craig Sherstan, Peter R. Wurman, and Peter Stone. Value function decomposition for iterative design of reinforcement learning agents

Thank you for replying and your questions!

Re: cited work.

In cases where a stable policy exists, yes it can be used. However, in general, we cannot assume we have access to a stable policy. One of the main points of the paper is that while RL has been used to learn from scratch in domains like Mujoco, learning from scratch with RL in our class of domains is very challenging. We’ve shown that learning RL policies from scratch is possible without relying on access to a stable policy in our evaluated domains.

We wish to emphasize the (somewhat nuanced) point that our work is motivated by a class of real world applications but is not itself an application paper. Rather we see a large gap in the RL literature in that we lack RL methods that can solve this class of problems from scratch. On the other hand, the paper you cite is an application focused paper that seeks to enable RL in the specific application of computer systems. While the load balancing example falls into the class of problems we study, it is just one instance of this problem class.

Based on your suggestion, we have included this new experiment (see Section I in updated Appendix in main pdf) where we evaluate an on-policy policy gradient method mixed with a stable policy as done by the authors in the paper you link (see updated pdf for details). We find that STOP is able to lower the queue lengths of the system much more than the RL policy with training wheels (TW; PPO-TW).

STOP is able to learn the stabilizing and optimal actions from a destabilizing, random policy. In the case of PPO-TW, however, since the initial RL policy is poor (random) it causes the agent to diverge, which violates the safety condition often, which results in frequent deployment of the stable policy. However, this off-policy data cannot be used to update the PPO policy. Thus, the RL policy continues to remain poor since it has inadequate data to train on, which causes the agent to diverge until it violates the safety condition, at which point the stable policy is deployed again.

Two remarks based on above:

1. In our experiment, we modeled the scenario based on the paper you linked of using an on-policy policy gradient method mixed with a stable policy. As noted in that paper and in ours, an interesting future direction is to extend our ideas to other off-policy algorithms, where we can leverage many different policies for training data.
2. The dependence on a stable policy is limiting due to: 1) it may not exist and 2) it may rely on access to quantities that are unknown. In the queueing experiment above, we used a stable policy called MaxWeight [4-7] which relies on knowing some information of the transition dynamics, which can be very limiting.

Re: Evaluation environments

The real-world application of this type of setup is in data-centers, wireless communication networks, and traffic intersection control [1, 2, 3]

Thank you for the feedback! We hope we have addressed your concerns and you would consider re-evaluating your assessment.

[1] R. Srikant and Lei Ying. Communication Networks: An Optimization, Control and Stochastic Networks Perspective. 2014.

[2] Michael Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems. 2010.

[3] Ault et al. Reinforcement Learning Benchmarks for Traffic Signal Control. 2021.

[4] L Tassiulas, A Ephremides, Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks, 29th IEEE Conference on Decision and Control, 1990.

[5] AL Stolyar, Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic, The Annals of Applied Probability, 2004.

[6] ST Maguluri, R Srikant, Heavy traffic queue length behavior in a switch under the MaxWeight algorithm, Stochastic Systems, 2016.

[7] Zixian Yang, R. Srikant, Lei Ying, Learning While Scheduling in Multi-Server Systems With Unknown Statistics: MaxWeight with Discounted UCB, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, 2023.

Thank you to the reviewer for their comments and questions. We are glad that you appreciate the effort in illustrating the difficulty of this problem. It is non-intuitive, and we wanted to stress this point.

Weaknesses

Re: background on Lyapunov functions

We understand. We will include the necessary background in the Appendix.

Re: differential value function bounded.

Yes PPO is learning the differential value function. However, the differential value function is well-defined only when the policy is already stable with a bounded average cost and a well defined stationary distribution. Algorithmically, average-reward PPO and TRPO methods need to first estimate the average cost before estimating the differential values; for example, see Line 4 in Algorithm 2 of https://proceedings.mlr.press/v139/zhang21q/zhang21q.pdf

Re: description of algorithm.

We have included pseudo-code in the updated appendix (section H)

Re: average reward background.

We understand. We will include the necessary background in the Appendix.

Questions

Re: gridworld clarification

Yes, your understanding is correct. Note that in this setting, going away from the origin, even when allowed, is suboptimal at any state. It is therefore without loss of generality to only consider actions towards the origin.

Re: Assumption 3

Please see our global response.

Re: revisiting states

Please see our updated Appendix (section D) and global response.

Thanks for the reply from the authors, I now have a clearer picture of the paper.

I think reward shaping, as a well known technique, is known to stabilize and accelerate RL. In particular, potential-based reward shaping has some nice theoretical guarantee to make algorithm still converge to the optimal policy under infinite coverage assumption. I think the quadratic potential function given in Section 4.1 belongs to this family. So I do not regard this as something new or a contribution of the proposed method. Take the grid world domain as an example, though the space of the domain is infinite, it is not quite a big issue as I believe this domain could be solved via reward shaping if we simply do tabular learning (with a very large value table to update, then there is no approximation error of the neural net). I checked the paper, and I find authors also mention (in Appendix B.4) "optimize only the stability criterion was sufficient to stabilize the agent", which as I expected.

So, I acknowledge that the authors raises a very interesting problem. However, I think the motivating example is not very convincing and the technique they propose is not very significant. As a result, I will decrease my score. Still, I encourage authors to polish the paper by considering the discussions here.

Thank you for the prompt reply!

While there are only two actions available to the agent, the difficulty lies in poor credit assignment to these two actions due to high stochasticity, poor reward functions, and unbounded state spaces. While both actions move the agent towards the origin, the agent may not actually be able to move towards the goal since with some probability two things can happen (both of which can happen at the same time-step): 1) its movement can fail (stays in the same place) and 2) it may be pushed away from the goal. Thus, while both actions are "good" in the sense they will try to make the agent move towards the goal, the actual quality of an action is determined based on the environment stochasticity.

Suppose the Manhattan distance from the origin is $c$ and is large (so the agent incurs a cost of $c$). Consider the agent is in a given fixed state and is deciding between the two actions.

1. Suppose the agent takes action $a_1$ and reduces the distance to the goal by at most 1 (since it can move only one step towards the goal and environment stochasticity can push the agent away by two steps). Thus the new cost incurred is $c'_1 = c - 1$.

2. if the agent takes $a_2$ and it increases the distance by at most 1 (for the similar reason as before), the new cost incurred is $c'_2 = c + 1$.

If $c$ is large, then the costs incurred in both these situations is $\approx c$ (since $c >> 1$). At that point, the agent finds it difficult to distinguish between the quality of these two actions since it incurs the similar cost for taking either action. The inability to distinguish between good and bad actions results in divergence. We refer you to Section 3 and Section C in the Appendix as well.

Of course, if the true values for the policy were actually learned, the agent could distinguish between long-term good and bad actions. However, to get the true values the agent needs many samples of the above transition due to the high stochasticity. Our paper is showing that in our setting optimizing the optimality cost functions and unbounded state spaces (see Section 3) in the reset-free and highly stochastic setting makes convergence to the true values challenging, making it difficult for the agent to determine good/bad actions, which makes the agent diverge.

To mitigate this challenge, our paper is proposing the agent first optimize a stability cost (and then optimality) instead of directly optimizing the optimality cost since the former can be more informative to the agent.

Hopefully this helps clarify things!

Regarding the comment on simply reward shaping can "solve the gridworld domain": any type of reward shaping is not necessarily sufficient to yield good performance (as we have shown in Section 3, Appendix F and G, and in our response to other reviewers). Our work is showing that a specific type of reward shaping that encourages the Markov chain to be positive ergodic (stochastically stable) does lead to good performance. While the stability cost appears similar to the potential-based shaping, the stability cost is indeed novel for reasons we mentioned in the above response.

Thanks for the reply!

In my opinion, the case of $\gamma=1$ is not hard to verify. $f(s,s')=\phi(s')-\phi(s)$. Consider original $G=\frac{1}{T}\sum_{t=0}^T r_t$. The one with reward shaping is $G^\phi=\frac{1}{T}\sum_{t=0}^T(r_t + f(s_t, s_{t+1}))=\frac{1}{T}(\sum_{t=0}^T r_t + \sum_{t=0}^T\phi(s_{t+1}) - \sum_{t=0}^T \phi(s_t))=\frac{1}{T}(\sum_{t=0}^T r_t + \sum_{t=0}^T\phi(s_{t})-\phi(s_0) - \sum_{t=0}^T \phi(s_t))=\frac{1}{T}\sum_{t=0}^Tr_t - \frac{1}{T}\phi(s_0)=G - \frac{1}{T}\phi(s_0)$. This will not alter the original problem.

Thank you for your comment.

While there are parallels between our stability cost and potential-based shaping in terms of form (as we also briefly remark in the paper when we introduce the stability cost), we want to make the following remarks on how potential-based shaping [1] is distinct from our stability cost:

1. Stabilizing the system:
   1. The original potential-based shaping reward does not draw any connections to the notion of stochastic stability [2,3] (see below for meaning). Nor are we aware of any work that does draw this connection. Our stability cost has deep connections to the notion of stochastic stability in that if an agent optimizes our stability cost, it will learn a long-term stabilizing behavior.
   2. Using any potential-based reward shaping does not necessarily mean it will stochastically stabilize the system. While there may be many “valid” potential functions (as per the original paper), it does not mean that those reward shaping techniques will stabilize the system. In our work, we analyze a specific type of cost that does indeed stochastically stabilize the system.
2. Discounted vs. undiscounted:
   1. Potential-based shaping’s preservation of the optimal policy was specifically for the discounted return setting (note that in the conclusion section of [1], the authors say the following about setting $\gamma=1$: “theorem may no longer guarantee optimality in this case”). We are specifically concerned with the long-term undiscounted setting where we focus on the average-reward.
   2. Given that introducing a discount factor introduces an effective horizon, using a potential-based reward shaping technique will not account for the true infinite horizon/long-term behavior of the agent. That is, techniques of accelerating convergence in the discounted case does not guarantee to achieve stochastic stability in the average reward setting.
   3. A discounted optimal policy may not even be stable in the average setting [4]. This stability issue lies at the heart of stochastic network control and queueing theory, and at the heart of our contribution.
   4. Extending the discounted return potential-based reward shaping to the undiscounted average reward setting is an interesting future direction, but is beyond the scope of this work as it is not our focus.

Stochastic stability [2, 3] refers to keeping the Markov chain positive ergodic (or informally, the agent does not diverge).

We hope that we have explained that while the stability cost has a simple formulation and similar formulation to potential-based shaping, it is indeed novel and significant as it sheds light on these deeper notions of stochastic stability for true long-term behavior that have largely been overlooked in the literature.

[1] Policy invariance under reward transformations: Theory and application to reward shaping. Ng et al. 1999.

[2] Stable Reinforcement Learning with Unbounded State Space. Shah et al. 2020.

[3] Queueing Network Controls via Deep Reinforcement Learning. Dai and Gluzman. 2021.

[4] J. Michael Harrison, (1975) Dynamic Scheduling of a Multiclass Queue: Discount Optimality. Operations Research 23(2):270-282.

Makes sense and thank you for your reply! Your verification also confirms that our approach is indeed sound.

However, we would still stress our main point, and we hope you can re-assess your evaluation based on it: that while the stability cost has relations to the potential-based shaping, the original potential-based shaping reward does not draw any connections to the notion of stochastic stability. Nor are we aware of any work that does draw this connection. Our approach to reward shaping (our stability cost) has deep connections to the notion of stochastic stability in that if an agent optimizes our stability cost, it will learn a long-term stochastic stabilizing behavior.

Thank you to the reviewer for their comments and questions. Thank you for appreciating how we conducted our empirical analysis.

Weakness

Re: Specific tasks

Please see our global response. A key part of our paper’s message is that such testbeds are not accurately representing challenges found in some real world RL domains.

Re: suggested reward functions.

In Section 3, we show that with such bounded reward functions the agent still diverges. In the updated Appendix (section F), we also include the performance of an RL agent using the suggested reward functions and show that the agent still diverges.

Part of our message is that designing reward functions for this class of problems is difficult. Common techniques of bounding and normalizing (such as in Section 3 and the suggested reward functions in the review) are not easily applicable in this setting. Thus, we need to resort to other techniques to get RL agents to perform well in these settings.

We also emphasize that in many stochastic control problems, the original cost function is tied to a specific performance metric. For example, in queueing, minimizing the average queue length is equivalent to minimizing system latency. Changing the cost function will in general change the optimal policy (i.e., the optimal policy of the new MDP no longer minimizes latency). Our reward shaping approach has the property that the optimal policy remains unchanged, since the average stability cost $\lim_{T\to\infty} (1/T) \sum_{t=1}^T \mathbb{E}[g(s_{t-1}, s_t)]$ is 0 for any stable policy (and hence for the optimal policy as well); see Proposition 2.

Re: motivation for Assumption 1-3.

Please see our global response and we will improve the motivation provided in Section 1 in the camera ready.

Re: other domains.

Please see our global response.

Re: visiting states.

Please see our global response and updated Appendix (section D)

Thank you for responding and updating your score! We appreciate it. We are glad you agree that our goal of trying to make RL work on real-world tasks is valuable.

We would like to point out that our paper is making a similar argument to yours: that prior, intuitive techniques and methods (such as vanilla PPO, normalization, bounding, clipping, resetting) that are typically successful in MuJoCo and Atari may be limited to those MuJoCo and Atari tasks only, and that they do not generalize to our class of real-world inspired RL tasks. This research experience taught us that finding a set of universally-successful techniques is indeed challenging, and that we may need to innovate new techniques depending on the types of problems.

Thank you to the reviewer for their comments and questions. We appreciate that you liked the soundness of our empirical section.

Weaknesses

Re: visiting states and divergence comment.

The state transformations do not solve the extrapolation burden. They only mitigate it. For example, suppose in the 2-queue setting, we have queue lengths [100, 200] and the RL agent has learned the optimal actions for this state. Now if the agent observes queue lengths [2000, 3000], which are very far from [100, 200], it will have a difficult time determining the optimal actions since it has to perform extreme generalization, which neural networks are bad at performing [1]. However, if we use a symlog transformation, as done in the paper, then the agent has learned optimal actions for symlog([100, 200]) = [4.6, 5.2], and can then locally generalize [1] to symlog([2000, 3000]) = [6.9, 7.6], which is significantly closer to the states that the agent was trained on.

Please see our updated Appendix (section D and E) and global response. In Section E, we show that when states are transformed using symlog, the agent observes the transformed states a higher fraction of the time compared to observing the original states.

Re: theoretical result

The theoretical results prove the soundness of our proposed method.

1. Proposition 2 shows that if an agent optimizes the stability cost, it is indeed stable i.e. it will incur bounded cost, which means it will visit states with bounded norm.
2. Proposition 1 shows that the stability cost can be optimized by policy gradient methods, as it has a well-defined gradient even when the current policy is unstable.

This should be contrasted with optimizing the optimality cost alone (without the stability cost). When initialized from a random policy (which is likely to be unstable), it will not have a finite cost or policy gradient, so the agent cannot even start running a policy gradient method.

Re: experiment section

Thanks for the suggestion. We do include the evaluation metrics and environment descriptions in the Appendix (section B), but we will improve this presentation.

Questions

Re: color coding.

Sure, we can do this for the camera ready.

Re: stability as constraint

We agree that our approach bears similarity to a Lagrangian formulation. Empirically, we observe that using a fixed lambda, even when chosen by hyperparameter sweeping, still leads to divergence. In the updated Appendix (section G), we hyperparameter sweep over different lambda and use your proposed formulation ($c(s_t) + \lambda g(s_{t-1}, s_t)$; note that the constraint is added instead of subtracted when learning) and show that the agent diverges. We note that if we combine your technique with the bounded cost/reward suggestion from reviewer Nors, the unbounded nature of the state will make the optimality reward close to 0, which will effectively make the agent optimize the stability cost/reward only, which is essentially our STOP agent without the optimality component.

Treating and updating lambda as a Lagrangian multiplier is an interesting idea. Note that unlike usual constrained problems where the objective and constraint are competing, in our problem stability (the constraint) is a necessary first step to optimality (the objective). If the current policy is not yet stable, the first term in the Lagragian formulation $c(s_t) + \lambda g(s_{t-1}, s_t)$ will be diverging and hence dominating the objective. It is therefore crucial to first achieve stability and maintain stability, as done in STOP. Also, ensuring stability requires a constraint of the form $\lim_{T\to\infty} (1/T) \sum_{t=1}^T \mathbb{E}[g(s_{t-1}, s_{t})] = 0$, which is a hard, equality, average-cost constraint, making it challenging to directly apply existing constrained RL methods.

Re: use of cost instead of reward.

As mentioned in Section 2, these terms are from the control-theoretic perspective. Given our applications (queueing, traffic control) are typically researched from the control-theoretic perspective, we stuck to that terminology.

Re: multi-step

This is an interesting suggestion, and is definitely something we will consider in future work. We expect that performance would be problem-specific, and as is typical with multi-step methods, will depend on the hyperparameter $\lambda$

Re: dynamically setting annealing schedule

This is another very interesting direction. Our main point of the work is to show that an agent should first pursue stability and then optimality. To get this point across, we resorted to a fixed schedule used by [2]. Dynamically setting the weights is in itself a difficult research problem, but we agree a starting point would be to explore methods that consider state uncertainty.

I have read other discussions. I decided to maintain my score.

I have read other reviews as well as authors' responses. I decided to maintain my current score.