Finding good policies in average-reward Markov Decision Processes without prior knowledge

Summary

The goal of the paper is to learn near-optimal policies in average reward MDPs without prior knowledge of complexity parameters, contrasting extensive prior work which requires knowledge of the values complexity parameters. They rule out the possibility of easily removing this knowledge requirement through estimation of the optimal bias span, but they show that the diameter can be estimated, and use it to give an algorithm in the generative model setting. In the online setting, they again show a negative result for achieving a span-based complexity, but build on the ideas from the generative setting to give a diameter-based complexity bound. They also propose a stopping rule and give some preliminary analysis of its performance.

Strengths

The problem of learning near-optimal policies in average reward MDPs without knowledge of complexity parameters is a fundamental and important problem, and this paper makes a number of small but important steps towards either achieving this goal or demonstrating its difficulty. I therefore am confident that this work will prove to be significant, in the sense that it will lead to future work which build off of its attempts. I think the presentation is mostly very clear and does a good job motivating the different settings and ideas.

Weaknesses

Algorithm 1 is not very novel, since it combines two ingredients from prior work: an optimal algorithm when knowledge of the optimal bias span is known, and a diameter estimation algorithm. The value of including section 6.2 (the value iteration-inspired stopping rule) is not clear to me, since the algorithm is only given a proof-of-concept analysis for the generative model setting (not the motivating online setting), and furthermore it involves seemingly foreign complexity parameters and does not improve upon the other introduced methods.

Questions

Line 110: In weakly communicating MDPs there is guaranteed to be a policy with optimal average reward which is unichain, however this policy might not be any of the higher-order notions of optimality (ex. bias optimal or Blackwell optimal). Also/therefore note that multiple policies with optimal gain may not have the same bias. Thus I think a more careful definition of the optimal bias span is needed here. Also I don't understand why the optimal policy is assumed to be unique; this is clearly not true in many situations (especially in average reward settings, there may be multiple ways to reach the same optimal recurrent class) and would greatly limit the applicability of the results. It doesn't seem like this assumption is needed for anything except potentially convenience in definitions, so I think it should be removed. This is very nitpicky, but I find it a bit weird that some bounds in Table 1 do not have a listed dependence on $\log(1/\delta)$ (ex. [27], which apparently does actually depend on $\log(1/\delta)$). Anyways, why include the dependence on $\log(1/\delta)$ for the other results if the $\tilde{O}$ notation is meant to hide log factors? Theorem 1 (impossibility of estimating $H$) uses unknown rewards, but the previously described setting assumes known mean rewards. Is it possible to get this result to work with known rewards? (One can try replacing the unknown reward state with a sub-MDP with unknown dynamics, but the part which is unclear to me is how adding this sub-MDP would affect the bias span) The formatting for the display for Algorithm 1 should be fixed

Rating

6

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

There are no significant limitations which require addressing

Summary

This paper studies the problem of learning a good policy in averaged-reward MDP with finite diameter. Given previous work on the problem assuming knowledge on the optimal bias span $H$, the authors try to remove the prior knowledge and propose diameter-dependent sample complexity without any prior knowledge. In the meantime, the authors present several observations about the hardness to reach better sample complexity bounds.

Strengths

I appreciate the efforts to study the sample complexity bounds without prior knowledge. However, the current result seems incremental and insufficient for an acceptance in my opinion.

Weaknesses

The major concern is due to limited contribution. Two possible directions to improve this work: (1) Is $H$-dependent sample complexity reachable without prior-knowledge (even allowing worse dependence on $1/\epsilon$)? It might be hard to estimate $H$ precisely according to your observations, but that does not means a lower bound. (2) It seems the exact $D$ factor in the online case could be removed by some efficient reward-free exploration algorithms. One could assume an approximate transition model to help conduct reward-free exploration, where the target is to solve the following problem $\min_{\pi_b}\max_{\pi}\sum_{s,a}\frac{d_{\pi,T}(s,a)}{d_{\pi_b,T}(s,a)}$ ($d_{\pi,T}(s,a)$ is the occupancy distribution following $\pi$ in $T$ steps). I think the following papers might help solve the problem efficiently. Minimax-optimal reward-agnostic exploration in reinforcement learning, Li et.al., 2024; Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies, Zhang et. al., 2022

Questions

Please find my questions in the comments above.

Rating

4

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

Yes.

Summary

This paper addresses average-reward Markov Decision Processes (MDPs). In the context of the generative model, existing literature presents an $\epsilon$-optimal policy with a sample complexity of $O(SAD/\epsilon^2)$. However, this approach requires prior knowledge of an upper bound on the optimal bias span $H$. This paper initially demonstrates that accurately estimating $H$ can have arbitrarily large complexity. Subsequently, it introduces the Diameter Free Exploration (DFE) algorithm for communicating MDPs, which operates without any prior knowledge about the MDP and achieves near-optimal sample complexity for small $\epsilon$. In the online setting, the authors establish a lower bound suggesting that achieving a sample complexity polynomial in $H$ is infeasible. Furthermore, they propose an online algorithm that attains a sample complexity of $O(SAD^2/\epsilon^2)$. They also propose a data-dependent stopping rule that they believe could reduce sample complexity in the online setting.

Strengths

This paper presents a complete procedure, DFE, that achieves near-optimal sample complexity for small $\epsilon$ without any prior knowledge of $H$ for average-reward MDP. This approach fills a gap in the existing literature. The finding that accurately estimating $H$ can have arbitrarily large complexity is new and interesting. This paper also presents a new finding that achieving a sample complexity polynomial in $H$ in the online setting is infeasible, setting theoretical boundaries for future research. The paper is technically sound, demonstrating rigor in the development and justification of its claims. The presentation quality of this paper is good. The authors did a great literature review on average-reward MDPs.

Weaknesses

The main concern with this paper is the limited novelty and contribution of the proposed solutions. The paper's claim regarding the necessity of knowing $H$ in the algorithm from [27] is somewhat misleading. The referenced paper explicitly mentions that only an upper bound for $H$ is required, not precise knowledge of $H$. The technique of using an upper bound of $D$ to estimate $H$, as presented in this work, is not original. Reference [25] previously introduced this idea, diminishing the perceived innovation of the current paper’s methodology. Additionally, Algorithm 2, designed to estimate $D$, closely resembles Algorithm 4 in [21], suggesting a lack of substantial differentiation in their algorithm design. The main algorithm, Diameter Free Exploration (DFE), seems to be a straightforward combination of algorithms in [21] and [27]. The primary theoretical contribution, Theorem 2, appears to be direct. The theorem’s proof does not seem to require substantial intellectual effort, suggesting that similar results could be easily derived by others familiar with the cited works. In the online setting, the situation is similar. The online-DFE primarily integrates existing algorithms with minimal modification, and the theoretical insights it offers do not extend far beyond established results. This recombination of known techniques without substantial new insights significantly diminishes the paper's novelty and impact. Theorem 3 in this paper is also very similar to Theorem 9 in [5]. While the authors propose a data-dependent stopping rule that they believe could reduce sample complexity in the online setting, they defer its exploration to future work. While postponing this analysis is understandable, it cannot be recognized as a substantial contribution within the current paper.

Questions

Regarding the development of DFE and online-DFE, and Theorems 2 and 4: Is it accurate to say that anyone familiar with [20], [21], and [27] could readily replicate these results? Specifically, were there unique challenges or complexities that are not immediately apparent but critical to the contributions of this paper? Could the authors clarify which algorithms and theorems they consider to be the main technical contributions of this paper?

Rating

4

Confidence

3

Soundness

4

Presentation

3

Contribution

2

Limitations

The authors adequately addressed the limitations in the conclusion.

Summary

The problem of identifying near optimal policies with high probability, either in the generative, or in the online setting, is considered when the state-action space is finite, and the criteria to compare policies is how much reward they collect on the average in the long term ("PAC setting"). Algorithms are compared based on their sample complexity: the number of interactions they need before they return with a near-optimal policy. The main question is whether knowledge of the span of the optimal value function allows for a reduced sample complexity. Some partial answers are obtained: For the generative setting, it is shown that estimating the span itself is not tractable. Next, the more moderate goal of designing an algorithm that adapts to the diameter is achieved. For the online setting it is shown that with or without the knowledge of H, the problem is intractable. Finally, sound algorithms are designed that control sample complexity in terms of the (possibly unknown) diameter. The paper also explains the difficulty of reducing the PAC problem to cumulative regret minimization.

Strengths

Novel results, new ideas, especially with the lower bounds.

Weaknesses

It was known that one can estimate the diameter; hence algorithms that adapt to the diameter are not that surprising. The PAC setting is a bit artificial. Results for the PAC setting are more interesting if they mimic the results of the other settings (fixed, known or unknown budget, simple regret, or cumulative regret); and the results in this paper just underline how unnatural the PAC setting is (the algorithm needs to know how well it does; this is nice to have, but less essential than doing well.) Since there is no box to present my summary opinion, I note it here that the above does not mean that there is no reason to study the PAC setting (ie I consider the above a really minor point). In fact, I find the question of whether there is a real difference between the PAC and the other settings an interesting and important question. Overall, I think the paper makes important and interesting contributions.

Questions

n.a.

Rating

8

Confidence

3

Soundness

4

Presentation

4

Contribution

4

Limitations

n.a.

Rebuttal read

I confirm I read the rebuttal and the other reviews. I still maintain this is a fine paper investigating a delicate issue in a thoughtful manner.