Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space

Summary

This paper focuses on an online learning setting for Markov Decision Processes (MDPs) with a countably infinite number of states. It adopts a Bayesian learning perspective, assuming that the parameters of the MDP follow a prior distribution over a known parameter space. The paper proposes a Thompson-sampling-like approach to solve the MDP in an online fashion. This approach assumes access to an optimal policy oracle, where the parameters of the MDP are provided as inputs, and it also relies on specific assumptions about the features of the parameter space.

Strengths

The model investigated in this paper exhibits a high degree of generality, and the results presented contribute significantly to the field of theoretical reinforcement learning by offering near-optimal algorithms for MDPs without a bounded state space. The inherent complexity of the problem necessitates intricate proofs, and although I haven't examined the complete proof in detail, I have confidence in the correctness of the underlying intuitions. The proof combines Lyapunov analysis with the proof presented in [38] for Bayesian learning in an MDP with a bounded state space, thus offering a potentially valuable contribution for future research. Additionally, the simulations conducted in the paper, which demonstrate the scaling of the algorithm's regret, are appreciated for providing empirical evidence supporting the algorithm's performance.

Weaknesses

The results of the paper rely on a set of assumptions that may be difficult to verify. Of particular concern is Assumption 3, which assumes stability of the optimal algorithm under one set of parameters for the MDP, even when considering another set of parameters. Establishing this property for more general systems can be challenging and requires careful calibration of the parameter space and policy space. The algorithm presented in the paper is heavily dependent on access to an oracle capable of solving the optimal policy, which itself is a complex problem for general queueing systems. This reliance on an oracle can limit the practical applicability of the algorithm. The algorithm necessitates returning to state 0 (line 14) at the end of each episode. This requirement could result in an exponential dependence on the maximum queue length, potentially rendering the algorithm less relevant for practical implementation. As a result, the claim of practicality made in line 345 may not be adequately supported. In relation to the previous point, the paper obscures many constants within the theoretical results. These constants, associated with the system's dimension and ergodicity, could play a crucial role in determining practical performance and should be given more attention and consideration.

Questions

Is there a heuristic for designing the parameter space and policy space to ensure that Assumption 3 holds for a queueing system? What would happen to the algorithm if this assumption fails? It would be beneficial to test the algorithm in a more general system, such as the ones described in [41, 52]. How crucial is the requirement for an optimal policy oracle? Would the analysis still hold true if the policy space is restricted to, for example, the MaxWeight policy? It would be highly valuable if the results were presented in a form such as "the total queue lengths of this algorithm minus that of the MaxWeight policy is less than or equal to \sqrt{T}". This would also eliminate the need for the optimal oracle. Could you discuss the dependence of the regret on the system size? Why does the dependence on T for the regret hold more significance than these constants? Please maintain consistency by using either "queueing" or "queuing" throughout the paper, but not both. In line 122, after "ergodicity)", there should be a period.

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

3 good

Contribution

3 good

Limitations

N/A

Summary

The authors study Bayesian learning of the problem of optimal control of a family of discrete-time countable state-space MDPs governed by an unknown parameter $\theta$ from a general parameter space $\Theta$ with each MDP evolving on a common countably-infinite state space $X$ and finite action space $A$. As the setting is Bayesian, they assume that the model is governed by an unknown parameter $\theta_\star \in \Theta $ generated from a fixed and known prior distribution. The learning goal: Bayesian regret minimization where the value function is the infinite-horizon average cost, and the regret is measured with respect to best policy in $\Pi$. They prove a $\sqrt{TA}$ regret bound, up to poly-logarithmic factors, but the dependency in the complexity of the function class is unclear to me. Disclaimer: I am not much familiar with this area of RL literature and hence might not understand the results correctly. Also, I could not fully verify the correctness of the presented results. I gave that assessment as the paper was very hard to follow for an unfamiliar reader.

Strengths

1. I think the results are a nice contribution to the Bayesian RL community. 2. The two examples presented contribute to the richness of the paper. 3. The presented bounds seem reasonable. 4. The adaption of Thompson sampling to countable state spaces might be useful in other RL settings.

Weaknesses

1. Abstract is quite long and parts of it seems like copy-paste of the introduction. 2. Writing requires improvement: (1) lightening the contribution compared to existing literature, (2) notation is hard to follow and makes proof reading hard, (3) complexity of $\Pi$ or the dimension $d$ should appear in the presented bounds, even if the dependency on them is logarithmic, those parameters are not negligible. 3. Need to mention the dependency in complexity of the function class is in the regret bound. Is it logarithmic for finite $\Pi$? Is the regret dependent on the covering number? I would be happy if the authors could clarify that point.

Questions

See weakness.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

3 good

Limitations

N/A.

Summary

This paper present an adaptation of TSDE to parametric MDPs with unbounded state space. The regret is sqrt{T} which is good but that is under strong ergodic assumptions and lower order terms can harm the behavior of the algorithm for small values of T.

Strengths

- The paper is sound technically. (I quickly checked the proofs) - The problem of learning unbounded MDP is a natural and important question to address.

Weaknesses

1. The strong conditions (especially Ass 4) are not necessary and sufficient conditions for existence of an optimal policy, nor for the existence of a solution of the Bellman equation. 2. The queueing examples are not really convincing: The optimal service rates can be computed efficiently by just estimating the arrival rate and solving the optimal control problem for the expected sojourn time. Also, numerically, the growing rate of the regret gets worse as the arrival rate increases.

Questions

1. The assumption on the unicity of the optimal policy is not related with all the other assumptions and is not discussed. This is actually a strong assumption restricting the class of MDPs that can be learned. This deserves some discussion why it is needed here. 2. The authors should discuss the practical aspect of their approach. In particular, can one check whether all the assumptions are satisfied while the MDP is unknown? 3. The Q-learning approach seems more natural than a model based approach under unbounded space spaces, where only the visited states are used for learning. Several papers have already taken this option successfully and are not discussed here (see for example "Stable reinforcement learning with unbounded state space" by D Shah, Q Xie, Z Xu )

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

3 good

Contribution

3 good

Limitations

I cannot see any limitations

Summary

The authors consider the average reward Markov decision process framework with countable state spaces. The considered objective is to perform closed-loop optimal control for a family of MDPs parameterized in a compact space; this is a particularly interesting setting as the cost function is not assumed to be bounded. The authors propose a Thompson Sampling based algorithm and analyze its regret under suitable assumptions. They are able to show a finite time $\sqrt{|\mathcal{A}| T}$ bayesian regret bound. The authors also show the practical significance of their algorithm by an empirical application to queuing models.

Strengths

- This paper is very relevant to the community as it opens the way towards studying RL in continuous spaces without the assumptions of bounded reward functions. Therefore tightening the connection of reinforcement learning theory and optimal control. - Although certain assumptions are somehow stringent, it is nice that the paper is able to convert an infinite horizon setting to a somewhat episodic setting. The latter usually allow for simpler analyses. - The application to a queuing model is also appreciated, a nice change from the standard RL benchmarks. - I would like to clarify that I did not go through the theoretical proofs and can therefore not comment on their correctness apart from the general intuition that such results should be possible given appropriate assumptions on stability and dynamics.

Weaknesses

- The assumptions seem somewhat stringent. For example, the finite support of transitions can be challenged even in the specific example of queuing models when large amounts of arrivals are possible. More importantly, assumption 3 seems quite limiting, can the authors elaborate on what this implies for stability? I am not very knowledgeable in optimal control but it seems that you are assuming stability of all policies? - The paper is sometimes very dense and not straightforward to follow. For example, lines 173 to 192 requires prior knowledge of several papers and definitions, e.g. Poisson equation’s link to the problem at hand/ forcing function and other similar passages in the text. I would advise the authors to add the relevant definitions and Lemmas at least in the appendix to make the paper self contained. - The paper fails to cite many RL works in the continuous spaces setting. Namely, the entire line of function approximation in RL, for example: 1) “Frequentist Regret Bounds for Randomized Least-Squares Value Iteration” by Zanette et al. which provides a algorithm based on Thompson Sampling as well, and many other works (see references therein) in the model-free paradigm 2) “Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planning” which also provides similar algorithms for MDPs that seem to include the queuing models presented here, see references therein for model-based approaches to RL in continuous spaces.

Questions

- In line 203, where is $\pi_{\theta_k}^*$ defined? How is this implemented in the examples? - From your understanding of your assumptions, is the stability ensured by default? Or does Thompson sampling just ensure it by some magic in the proof? If the latter, and since you have a bound on the maximum $\ell_\infty$ norm of the states, is it not more straightforward to use existing RL algorithms? I guess what I’m asking is how necessary the Lyapunov-type analysis is in this case? - Why aren’t there comparisons with other RL algorithms in the experiments? especially since you implement PPO in the second model for your experiment, isn’t it possible to compare directly against it and other deep RL methods?

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

2 fair

Contribution

3 good

Limitations

The proposed work and algorithms is theoretical and does direct societal impacts. The possible theoretical limitations are detailed to some extent in the paper and to be addressed in future work.