Achieving Tractable Minimax Optimal Regret in Average Reward MDPs

Summary

The paper proposes the first tractable algorithm that achieves minimax optimal regret for average reward tabular MDPs. The algorithm does not require prior information on the span of the optimal bias function.

Strengths

The paper proposes the first tractable algorithm that achieves minimax optimal regret for average reward tabular MDPs.

Weaknesses

See questions.

Questions

1. The minimax lower bound in [4] is sqrt{DSAT}. Because H=span(h^*) <= D, I wonder why sqrt{HSAT} is even achievable by the algorithm developed in the paper. 2. The authors cited [14, 25] for the lower bound sqrt{HSAT}, but I can not find this result/theorem in these two papers with a rigorous proof. In fact, [14] mentioned it is an open problem whether the “actual” lower bound depends on diameter D or the bias span H. Please provide a proper reference if the actual lower bound depends on H. 3. As shown in Figure 2, PMEVI behaves almost the same with its EVI counterparts when no prior information on bias is given. This does not illustrate the advantage of PMEVI compared with UCRL2 or KLUCRL, even though the regret of the algorithm in this paper is claimed to be better. 4. In Figure 2 (to the right), PMEVI is run with bias information c, but it is compared with UCLR2 which does not use c. This is not fair comparison. If PMEVI is given bias information, then it should be compared with other algorithms such as SCAL or UCB-AVG which require bias information for implementation. 5. Computing max_u beta_t(s,a,u) may not be tractable in general. Algorithm 5 provides a way to bound/approximate this quantity. I wonder what is the intuition? I also can not find the proof that it is indeed a bound that does not impact the regret efficiency. 6. The regret proof in Section 4 does not highlight how the key components projection and mitigation in the algorithm impact the regret. In particular, it is not clear from the proof sketch where these components are used, and how the beta-mitigated extended bellman operator is applied to achieve the minimax optimal regret.

Rating

4

Confidence

3

Soundness

2

Presentation

3

Contribution

2

Limitations

I do not find the discussions of limitations in the main body of the paper.

Summary

The authors propose a novel algorithm for weakly communicating Markov Decision Processes (MDPs) with an average-reward objective. This algorithm, at the same time, is a) tractable since it does not rely on the exact solution to a high-dimensional non-convex optimization problem as prior work, and b) achieves minimax optimal regret up to logarithmic factors.

Strengths

- First tractable algorithm that achieves minimax optimal regret bound; - The algorithm does not require any prior knowledge of the span of optimal bias function; - The algorithm does not require any reduction to a discounted setting and works directly in the average-reward setting.

Weaknesses

- The algorithm requires solving the linear programs for each doubling epoch, which is tractable but non-generalizable beyond the tabular setting; - The large second-order term is dominated by the main asymptotic optimal term if $T > S^{20}$. This effect of a large second-order term is also observable during the experimental section.

Questions

- Discussion in Section 3.3 is a little bit misleading since it is formulated in terms of arbitrary vector u and may think that, afterward, the union bound over possible u should be applied to write down a bound of type $\max_{u} \beta_{t}(s,a,u)$ (and thus inducing additional $\sqrt{S}$ factor due to equivalent with purely $\ell_1$-confidence regions), whereas you need to do it only for $u = h^\star$. I would suggest rewriting this discussion a little bit to avoid the confusion I experienced during the first reading of the text. - Appendix C6. It's not clear what (2k) means in the equation after line 796. I have the same question about (3k) and (4k) after line 816 and 825. - Additionally, I would appreciate the additional discussion on the difference between regret minimization and best policy identification settings for average-reward MDPs, especially in a glance at existing concurrent work Tuynman et al. 2024. Tuynman, A., Degenne, R., & Kaufmann, E. (2024). Finding good policies in average-reward Markov Decision Processes without prior knowledge. arXiv preprint arXiv:2405.17108.

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

4

Limitations

The paper is of a theoretical nature and thus does not have any direct impact.

Summary

This paper studies learning in average reward MDPs, and presents the first minimax optimal algorithm (in terms of $sp(h^*)$) which is computationally tractable, and also simultaneously the first which does not require prior knowledge of $sp(h^*)$.

Strengths

The main theorem resolves a longstanding open problem which has been the subject of extensive research effort. Removal of knowledge of $sp(h^*)$ is a challenging problem in many settings beyond the one considered in this paper, and thus I hope that this work might lead to progress on this issue in other areas.

Weaknesses

The algorithm is rather complicated and has many components. The presentation also does not make it easy to determine the key ingredients of this method. While it is interesting that this method may incorporate different confidence regions, I wonder if it might be more clear to present things in less generality. It is nice that experiments are included, but if anything they seem to contradict the claim that the method achieves minimax regret without prior knowledge of $sp(h^*)$ (due to the left plot in Figure 2). Since the bias estimation subroutine seems to be a key ingredient, it would be much better if an experiment was included where this subroutine was making a nontrivial contribution (by my understanding, in the left plot the bias estimation routine is not doing anything since it hasn't been given enough time, and in the right plot, it is not doing anything since much better prior information has been given to the algorithm).

Questions

Why is the main theorem stated with the parameter $c$? It seems like the best choice is always $c=sp(h^*)$? (And if $c \gg sp(h^*)$, then the theorem is not giving the minimax optimal regret.) Does the theorem hold for all $c$ simultaneously or is this parameter used somewhere that I didn't notice? The main theorem mentions a confidence region system for communicating MDPs with a diameter-dependent computational complexity, but since the paper is for weakly communicating MDPs which generally have infinite diameter, I think a different system would be a better choice? Can the author(s) comment on the complexity when the diameter is infinite? Many times notation like $h^*(\mathcal{M})$ is used, but is this well-defined? There can be multiple solutions to the Bellman optimality equation. The paper https://arxiv.org/pdf/1905.12425 claims to achieve the optimal diameter-based $\sqrt{DSAT}$ regret, maybe it should be added to the related work. In the display below line 785, the number of commutes between $S_t$ and $S_{t+1}$ is lower bounded by the number of transitions between these states. A similar bound is used under line 830. Does this suggest that the bias difference estimator could actually be formulated using only direct transitions between pairs of states? Line 397: $h^*$ should be $g^*$? Line 404: Some character I believe meant to be $S$ was used

Rating

7

Confidence

3

Soundness

3

Presentation

2

Contribution

4

Limitations

No major limitations

Summary

The paper shows that by replacing the extended value iteration in optimistic methods, like UCRL2, it is possible to obtain regret that scales optimally with the number of states, actions, the time horizon and the span of the optimal value function, instead of the diameter, despite not knowing the diameter, assuming weakly communicating MDPs. In addition, a novel analysis is presented that also gives a polynomial bound on the compute cost of the algorithm. The new extended value iteration method is designed based on new ideas to refine the set of plausible MDPs considered in a given step: For this, an inequality is provided that relates the deviation of the values assigned to two states to observable quantities; creating a new set of constraints on the MDPs considered.

Strengths

A major breakthrough if the proof holds up. Interesting insight.

Weaknesses

The presentation is not great; the paper feels rushed, the paper is full of (minor) grammatical and typographical errors (starting with the abstract: "encounter suffer"). While I did not go through the whole proof, there are many minor problems that are apparent: The paper is not very careful in tracking error events. For example, \tilde{beta} is sometimes appearing in a condition, but it is also constructed by the algorithm, perhaps things work out, but details are definitely missing. The experimental results are unconvincing: Experiments that show scaling the optimal span would have been more convincing. The presented experiments do not help at all.

Questions

Are you sure you tracked all the error events correctly? (E.g. in Lemma 13, Lemma 3 is used, which needs $\tilde{g}\ge g^*$, but the proof of Lemma 13 does not mention why this would hold and exactly what value of $\tilde{g}$ is used here.) One of the confusing aspects of the presentation of the insight was that on page 5, where the mitigation is explained, beta_t(s,a,u) is used and then a maximum over u is taken; while it is not explained whether beta_t(s,a,u) bounds the deviation that is a function of u for all u (needs a covering?). I guess this covering is not needed, but then why can we take the max as suggested in this paragraph (lines 155-161).

Rating

7

Confidence

3

Soundness

3

Presentation

2

Contribution

4

Limitations

n.a.

acknowledgement of rebuttal

The rebuttal is fine; I wish I could read a polished version of the paper before it gets published. However, I am optimistically assuming for now that the presentation issues will be smoothened out and the result will still hold.