Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor

Summary

The paper introduces the Blackwell discount factor MDPs. The authors show that when the discount factor is larger than the Blackwell discount factor $\gamma_{bw}$, all discount-optimal policies become Blackwell- and average-optimal, and derive a general upper bound on $\gamma_{bw}$. The authors claim to provide the first reduction from average and Blackwell optimality to discounted optimality via polynomial-time algorithms. I am not much familiar with the literature regarding Blackwell optimality criterion and thus might not fully understand the significant of the results. I would be happy that the authors would highlight for significant of results in compression to the known results in for discounted value criterion and averaged value criterion.

Strengths

1) The assumptions and contributions are clearly stated. 2) It seems that the presented results improve the known results in the study of Blackwell optimality criterion, remove commonly used assumptions and provide efficient algorithms. 3) The application of algebraic techniques to RL might be useful in other settings.

Weaknesses

1) No concrete application or motivation for the work is given. 2) It is unclear to me whether the new definition of Blackwell optimality via the Blackwell discount factor proposed in the paper is better/ outperform/ more useable than the discounted value criterion in standard RL applications. 3) The authors claim throughout the paper that previous literature repeatedly mentioned the discussed problem as important, but not clearly mentioned why. 4) The focus of the paper is mainly about previous works (and their limitations), instead of the new approach (they get to it only in page 6 out of 9!). More elaborated proof sketches would benefit the reader.

Questions

1) May you please provide concrete motivation for the use in Blackwell optimality criterion and/or a concrete application? 2) Ergodicity and aperiodicity properties are standard assumption in RL even in simple planning task. It is unclear to me how can you remove them and why it is important. In most application the assumptions are reasonable.

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

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

N/A

Summary

This paper studied the a Blackwell optimal policy can be obtained from an average-optimal policy by introducing the Blackwell discount factor $\gamma_{bw}$. The author further showed that the discount factor can be upper bounded by the bit-size of an MDP instance.

Strengths

1. The paper is well written and organized. The insights behind the main results are well presented. 2. The introducing of the Blackwell discount factor is interesting, it may lead to efficient algorithms in future studies. 3. An upper bound for $\gamma_{bw}$ is provided.

Weaknesses

1. Providing the upper bound of $\gamma_{bw}$ is not enough, still we don’t have a efficient algorithm for finding the Blackwell policy. Also I am afraid for calculating it needs have sufficient information of the MDP structure. 2. Proposition 4.3 is only for the deterministic transitions with $S=2, A=2.$ 3. The $ \eta$ in Theorem is quite close to zero, which means the upper bound for $\gamma_{bw}$ is almost 1. 4. No simulation results are provided, it is better the show the advantage of the proposed approach with even some simple simulations.

Questions

1. I don’t agree with the authors that they criticize on the existing definition of the Blackwell optimality. The definition looks good to me, we just don’t have an efficient algorithm yet. What if the MDP is unichain or ergodic (different as your example 3.5), does proposition 3.4 still hold? As far as I know, the weakly communicating assumption or the ergodic assumption, is in fact known to be necessary for learning infinite-horizon MDPs with low regret. 2. what is m in your theorem 4.4? 3. Proposition 4.3: \eta >0 → 1>\eta>0

Rating

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

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

3 good

Limitations

More discussions on the limitations of your approach should be included. Also it is better to make more comparisons between the two discounted factors when there are more assumptions on the MDP.

Summary

The paper studies how to reduce the computation of Blackwell-optimal policies to that of discount-optimal policies. The authors introduce the notion of "Blackwell discount factor", a value $\gamma_{bw} \in [0,1)$ s.t. any discount-optimal policy for $\gamma > \gamma_{bw}$ is also Blackwell optimal. They show that $\gamma_{bw}$ always exists for finite MDPs and upper bound it as a function of the size of the MDP. Finally, they extend these results to robust MDPs.

Strengths

1. The paper studies a relevant problem, that of computing Blackwell optimal policies, which hasn't received much research attention so far (eg, as compared to other popular optimality criteria) 2. The contribution is significant and, to my knowledge, novel. Being able to reduce the computation of Blackwell optimal policies to discounted MDPs is absolutely relevant given the theoretical understanding and efficient algorithms that we currently have for the latter setting 3. The paper is extremely well written. Despite the complexity of the studied topic (which is also not very well known in the RL community), the authors did a very nice job in providing the necessary basics and intuitively discussing all formal results, while providing comprehensive proof sketches. Related works are also discussed with sufficient detail.

Weaknesses

1. While it is nice to have an upper bound on $\gamma_{bw}$ that depends only on quantities known by the learner, the quantity $\eta(M)$ is exponentially small in the size of the MDP (eg in the number of states). This essentially means that, while we can solve a discounted MDP with $\gamma = 1-\eta(M)$ to compute a Blackwell optimal policy, we need to use a discount factor which is extremely close to 1 even for MDPs of moderate size. In practice, such a large value of $\gamma$ may simply make the learning process extremely inefficient. It is thus natural to wonder how conservative the proposed bound is. For instance, do the authors believe that there exist MDPs with a "simple structure" in which $\gamma_{bw}$ is way smaller than the stated bound? 2. There is no numerical simulation. It would have been nice to see some experiments comparing (eg in terms of run-time) existing algorithms for computing Blackwell optimal policies to a method for solving discount MDPs with the (upper bound on the) Blackwell discount factor

Questions

See above.

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

4 excellent

Contribution

3 good

Limitations

Limitations have been discussed. No potential negative societal impact

Summary

The paper proposed a new concept called Blackwell discount factor $\gamma_{bw}$, which enjoys good properties: any policy that is $\gamma_{bw}$-discount-optimal will be Blackwell optimal as well. If $\gamma_{bw}$ is known, then one can reduce the problem of find average-optimal policy to finding discount-optimal policies, which is practically easier. The authors provide theoretical justifications for Blackwell discount factor and a proper instance-dependent upper bound. In the end, they extend the results to Robust MDP setting, where the definitions and results continue to hold.

Strengths

The paper tackles a significant shortcoming in the previous literature on Blackwell optimality: the current definition does not allow us to find Blackwell optimal policy in a naive way that is to choose a large enough $\gamma$ and simply find its discount optimal policy. The paper has a clear and strong motivation to study the problem with a minor question I will mention in the Weakness section. The theoretical results are clearly delivered and significant. Especially some impossible results in Proposition 3.4 and Theorem 3.6 are intriguing and it reveals something fundamental about the Blackwell optimality.

Weaknesses

Certain writings and motivation may be taken care: 1. Line 5: computing average-optimal policies requires only the weakly-communication assumption (instead of unichain or ergodicity), which is a reasonable assumption as weakly-communication is necessary for a unique optimal average rewards. 2. Line 43-61: There exists many value iteration algorithm for average-reward setting. I don't fully understand the motivation to find the optimal average-optimal policy through finding discounted-optimal policies. The well-known [UCRL2](https://proceedings.neurips.cc/paper_files/paper/2008/file/e4a6222cdb5b34375400904f03d8e6a5-Paper.pdf) calls value iteration as a sub-routine. 3. Saying the classical definition of Blackwell optimality has shortcomings can be confusing, because the paper does not have a new definition for Blackwell optimality. Instead, it proposes a new concept named Blackwell discount factor. 4. I am not fully convinced that Blackwell discount factor is the only discount factor of interest. In some circumstances, we may want to find the Blackwell optimal policy that is $\gamma$-discount-optimal for as small as possible $\gamma$. 5. I don't see a strong connection between Blackwell optimality and Robust MDP. It is nice to see that similar results continue to hold for Robust MDP. However, the two topics seem orthogonal to me. Before reading Section 4.2, I was expecting to see results on how Blackwell optimality improves robustness, since Blackwell optimality in general sense is one type of robustness w.r.t. the change of discount factors. Minor comments: 1. Line 247: the authors mentioned “in the next proposition”, while it is a Theorem that follows. 2. Theorem 4.5, Theorem 4.6 should be stated as a Lemma.

Questions

1. Is $\gamma_{bw} = \max_{\pi} \gamma(\pi)$? Intuitively, this makes sense as if $\gamma_{bw} < \gamma(\pi')$, then $\pi'$ is not $\gamma_{bw}$-discount-optimal, which violates the definition. If this is true, then can I understand the paper as finding the smallest $\gamma$ such that all Blackwell optimal policies are simultaneously optimal on this $\gamma$? 2. Is it NP-Hard to verify weakly-communicating assumption?

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

The authors mentioned approximate Blackwell optimality and robust Blackwell discount factor for other types of uncertainty sets. No societal impacts that need to be addressed.

Summary

This paper defines the Blackwell discount factor: when the discount factor is larger than this factor, discount-optimal policies become Blackwell and average-optimal. An analytical solution for such factor is also derived. The results are also extended to the setting of sa-rectangular RMDPs.

Strengths

Motivated by the original definition of Blackwell optimality, the authors propose the Blackwell discount factor, via which we can solve for the optimal policy of an average-reward MDP by solving a corresponding discounted-reward one, where the restrictive assumptions in average-reward setting is bypassed. This should be an exciting result. The writing is clear and the contents are well organized.

Weaknesses

I only have some minor comments. Please see my questions below.

Questions

Line 177: It should be "we use the notation...". Line 319: It is not clear to me what "coarseness" is and how Proposition 4.3 shows this dependence.

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

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

Please see the questions above.

Summary

This paper studies a new class of objective for MDPs. Instead of aiming to find the policy which maximizes the long-term average reward, the authors propose a new approach to find a Blackwell optimal policy. A Blackwell optimal policy also maximizes the average reward, but Blackwell optimality has not been studied much in the literature due to the intractability. In this paper, the authors show that there exists a ‘Blackwell discount factor’ such that any policy which is discount optimal for this specific choice of discount factor is also Blackwell optimal and average reward optimal. However, finding this Blackwell discount factor is quite challenging, although the authors provide a sufficient condition for it, providing an upper bound on the Blackwell discount factor, and showing that any policy which is optimal wrt this upper bound on the discount factor is Blackwell optimal. However, this upper bound depends on properties of the MDP which are may not be known in RL. The authors also provide an extension to robust MDPs.

Strengths

The notion of Blackwell optimality is interesting and indeed not studied by the RL community, so it is nice to see it being brought to attention. It is also nice that this provides a method for finding an average-optimal policy in a known MDP without assumptions on the MDP, and it is pleasing that there is an extension to robust MDPs. The paper is reasonably well written and organised.

Weaknesses

It seems that Blackwell optimality has been considered in MDPs before, so the main contribution seems to be defining this Blackwell discount factor and showing solving an MDP with that discount factor leads to an average-optimal policy. From the discussion of the literature, it sounds like the existence of the Blackwell discount factor was folklore so it is nice to see it proven. However, the Blackwell discount factor itself seems difficult to find and the proposed upper bound also depends on quantities such as the maximum bit size of the MDP which I imagine is typically not known. However, there was only limited discussion of the proposed bound so I found it somewhat difficult to interpret. The bound on the discount factor also seems to scale with 1-1/(4^S)^S, so as S gets bigger this will approach 1 very quickly (indeed when I plotted it on my laptop, for S=4, it was rounded to 1). Therefore, I am concerned that for most reasonably sized MDPs, we will need to find an optimal policy with a discount factor arbitrarily close to 1 which will still be challenging and may require more assumptions, so I am not completely sure of the benefit of this approach. Lastly, it is not clear how to translate this approach to an RL setting where we do not know the MDP. There was a bit of discussion about this, but not sufficient to understand how to actually use it in RL. There is an attempt to generalise to robust MDPs where we only know a set of transition functions, but I did not think sufficient details were provided to fully understand the usefulness of this result. I also wonder whether this work could be better suited to another venue.

Questions

Can more details of calculating the bit-size of an MDP be given? In particular, it would be nice to see an example of the bit-size of an MDP (e.g. riverswim or another classical example) be given? Can this also be translated into the bound on the discount factor? It would also be good to see a plot of the bound on the discount factor with size of the state space to see when it leads to bounds that are essentially 1. It may also be good to have a comparison in terms of computation time/number of iterations of this method and other methods, even if there are different assumptions. More generally, it would be good to have the benefits of the proposed method clearly demonstrated. Can the results for robust MDPs be used in the setting where we define confidence sets using data?

Rating

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

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

2 fair

Limitations

Limitations (e.g. what to do when we don’t know the MDP) are discussed briefly but could be discussed in more detail.

Acknowledgement

I thank the authors for their response. After going through all reviews and rebuttals, I still believe that the paper provides a significant contribution, though with some limitations. I will thus keep my initial view.