Sample Efficient Reinforcement Learning in Mixed Systems through Augmented Samples and Its Applications to Queueing Networks

Summary

This paper focuses on a specific class of Markov Decision Processes (MDPs) in which a state can be decomposed into a stochastic component and a pseudo-stochastic component. The transition dynamics of stochastic states depend solely on the current stochastic state and the action taken, while the transition dynamics of pseudo-stochastic states are determined deterministically by the current state, the next stochastic state, and the action. Such MDPs are suitable for modeling applications like queueing systems. The authors initially consider a scenario with finite state spaces and batch reinforcement learning. Given a set of independent and identically distributed (i.i.d.) transition and reward data, they propose a data augmentation algorithm that generates m new virtual samples from each data point. This is achieved by replacing the pseudo-stochastic components with newly sampled ones. Subsequently, they propose the fitted Q iteration with an augmented dataset. Under certain coverage assumptions for stochastic states and with n initial samples, they establish an error bound on the Q function, which scales as 1/\sqrt{n} + 1/\sqrt{m}. The authors extend their results to scenarios with an infinite pseudo-stochastic state space, along with additional assumptions. Simulations are conducted to demonstrate the benefits of the proposed algorithm.

Strengths

Using reinforcement learning to determine optimal policies for systems with large state spaces is a well-known challenge. However, this paper presents a valuable and intuitive framework that effectively captures the inherent structure of environments, specifically queueing systems, through the introduction of pseudo-stochastic states. This innovative modeling approach is commendable. The concept of utilizing fixed transition functions to generate new data points is novel and has practical relevance for systems influenced by limited stochastic inputs. The theoretical results provided in the paper are sound and contribute to the overall strength of the work.

Weaknesses

In Section 2.1, the authors provide an example where the pseudo-stochastic state space is not finite, which goes beyond the scope of the model as indicated by the assumption of a finite state space in line 148. Although the authors later extend their results, it remains unclear how this example aligns with Assumption 1. Building upon point 1, Assumption 1 poses challenges in designing the function class F for the Q function. It seems difficult to define a class where the value of an atypical state under any function within the class is consistently close to the optimal Q value. The authors need to provide better justification for why this property can be easily achieved. One approach could be to establish a broad enough function class that satisfies Assumption 1 for a simple queueing system. Justifying the reasonableness of Assumption 1 is crucial, especially considering the paper's claim that the theory and method are applicable to queueing systems with unbounded state spaces. The simulation section lacks sufficient explanation and some of the plots appear unreasonable. Further details and clarification are needed to address these issues. There are several typos that need to be corrected throughout the paper.

Questions

In line 93, the authors claim "far less memory space." Could you provide a quantification, such as the complexity mentioned in line 91? In the simulations, how is the reward function determined? How are the state sampling distributions \beta_k set? Additionally, what is the number of virtual samples used? Regarding Figures 2 and 3, how is an episode defined in the context of the simulations? In Figure 3 (a, b, c), it appears that the performance of DQN-ASG does not show improvement after training with episodes. Furthermore, why is the performance in episode 0, where the algorithm should not have learned anything yet, already better than other algorithms? The same question applies to Figure 4 in the appendix. In lines 24 and 25, from "time-consuming" to the period before "In this paper," the text does not form a complete sentence. In line 56, the last "and" is unnecessary. In line 222, please change "satisfies" to "satisfying."

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

N/A

Summary

The paper introduces a novel setting called mixed systems, in which environments comprise both stochastic and deterministic transitions. This leads to two types of states: stochastic states and pseudo-stochastic states. Stochastic states follow a stochastic transition kernel, while pseudo-stochastic states have deterministic transitions given the stochastic states/transitions. Such systems are common in real-world reinforcement learning (RL) applications such as data centers, ride-sharing systems, and communication networks. Existing RL approaches can suffer from sample inefficiency due to the curse of dimensionality. The paper proposes an augmented sample generator (ASG) to improve sample efficiency. ASG augments transitions by retaining stochastic states while sampling new pseudo-stochastic states. The paper provides a motivating example of a wireless downlink network, where stochastic states are the number of data packets arriving and the number of packets that can be transmitted at each time step. The pseudo-stochastic state is the length of the queue, which can be computed deterministically given the stochastic states. The authors offer a convergence guarantee in the form of an optimality gap, connecting the learned value and optimal value with the number of real samples and augmented samples per real sample. Experiments are conducted on a criss-cross network and the motivating example. The results demonstrate that combining ASG with Q-learning or policy gradient-type algorithms significantly improves performance.

Strengths

1. The paper presents a new setting that is widely observed in real applications. 2. A highly suitable algorithm (ASG) is proposed for this setting. 3. The effectiveness of ASG is demonstrated through solid theoretical proof and several experiments.

Weaknesses

The main weakness of the paper is that the difference between the new mixed systems setting and existing MDPs with exogenous inputs is not entirely clear. Although the analysis in Line 133 is sound, the environments used in this paper can be modeled with MDPs with exogenous inputs. For example, in the wireless downlink network, stochastic state is independent of actions taken. Seems that all environments used can be viewed as MDPs with exogenous inputs, and also a special case of mixed systems. However, the new setting is valuable, and more real-world application examples that can only be modeled with mixed systems are desirable. **If the authors address this issue, I recommend strongly accepting the paper**. A minor weakness is that the algorithm assumes access to the reward function $R$ and pseudo-stochastic state transition function $g$, potentially limiting its scope. However, this assumption seems reasonable in most examples mentioned.

Questions

1. In Sections 4.1 and 4.2, the system seems to be defined on a continuous time span. It is unclear how continuous time is discretized. I suggest adding details about this issue to the main text or supplementary material. 2. Regarding the wireless downlink network example in Section 2.1, let's consider a situation where the real pseudo-stochastic state has queue lengths of {0, 0, 10}, and a good policy would take action 3 to schedule mobile 3 at this time step. ASG could augment a pseudo-stochastic state as {10, 0, 0}, and in this case, the real action 3 taken seems inappropriate. Although this augmented data still follows the transition function g, it is information less to the policy learning. How will such augmented data affect policy learning and the convergence result?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

2 fair

Limitations

The paper does not extensively discuss limitations or potential negative societal impacts of the work. No further limitations need to be addressed.

Summary

This paper consider the sample efficiency of RL in a setting involving "mixed systems" where the state space is factored into a stochastic component and another much larger component that is deterministic when conditioned on the stochastic component. The authors develop an algorithm for this setting relying on generating relevant synthetic states that have not been encountered before. This approach when applied to fitted q-learning is able to show sample efficiency bounds for which it is not necessary that the data includes all pseudo-stochastic states. The authors also demonstrate the practical utility of their approach in application to the deep function approximation settings based on queuing networks.

Strengths

- The paper is well written and makes a focused contribution. - Not only is significant theoretical analysis provided, but also it is shown that this theory makes a meaningful impact for deep function approximation. - While the empirical domains are not very complex, they do represent real-world use cases, which makes up for this deficiency in my mind.

Weaknesses

- I think the approach will make a big impact where it is applicable, but I worry that this setting is a bit niche. I don't think this is a big problem, but just am a bit less excited as a result. - It is unclear to what extent the approach can be extended to partially observable domains with more complex input spaces. - Given the similarities, I would appreciate a more clear connection with the factored MDPs literature.

Questions

1. How realistic is it that the factorization of stochastic states and pseudo-stochastic states is provided to you? Can the cost of identifying these be bounded? 2. Can you talk to the connection between your setting and work on factored MDPs, including existing sample efficiency bounds in that setting? To what degree are you using novel ideas in the bound and approach derivation and to what degree are the insights different from that literature? 3. Do you think that any of the insights of this paper can be useful in partially observable versions of mixed systems, or is it restricted to fully observable settings?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

2 fair

Limitations

The authors do a good job for the most part of discussing assumptions and limitations. I agree that the assumption for the case of an infinite number of pseudo-stochastic states seems mild. Looking at appendix A, the data coverage and completeness assumptions also seem mild, although I think at least more intuition about this should be provided in the main text. One thing I think should be further highlighted and discussed though is that not only do these components of the state space need to exist but they also need to be provided to the user. In my mind, this knowledge about the state space is relatively hard to come by and limits the areas of application. Maybe taking inspiration from the literature on factored MDPs, the authors can account for the cost of the discovery process as well.

Follow up

Since the discussion period starts, we just wanted to check in and ask if the rebuttal clarified and answered the questions raised in your review. Please don't hesitate to let us know if you have any other questions/comments. We would be very happy to engage further if there are additional questions!

Response to Rebuttal

Thank you for your response to my questions. I really appreciate your clarification regarding the connection to factored MDPs and POMDPs. I have increased my score as this cleared up some confusion of mine.

Thanks for your reply.

The authors have provided clear and satisfactory responses to most of my inquiries. As a result, I am inclined to raise my score for this paper. However, a lingering concern remains regarding my second question, specifically pertaining to the wireless downlink network example in Section 2.1. In the example I presented, taking action 3 on the augment pseudo-stochastic state {10, 0, 0} seems technically valid and aligned with the transition functions. Nevertheless, it appears that opting for action 3 could be suboptimal, potentially rendering this augment pseudo-stochastic state ineffective for policy learning. Although this concern seems to have minimal impact given the positive experimental results, I would greatly appreciate it if the authors could address and clarify this question in greater detail, preferably by incorporating it into the main body of the paper.