Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor
Authors: Julien Grand-Clément
Marek Petrik
Venue: NeurIPS 2023 poster (2023)
Keywords: Markov Decision Process
Blackwell optimality
average optimality
robust optimization

Abstract: We introduce the Blackwell discount factor for Markov Decision Processes (MDPs). Classical objectives for MDPs include discounted, average, and Blackwell optimality. Many existing approaches to computing average-optimal policies solve for discount-optimal policies with a discount factor close to $1$, but they only work under strong or hard-to-verify assumptions on the MDP structure  such as unichain or ergodicity. We are the first to highlight the shortcomings of the classical definition of Blackwell optimality, which does not lead to simple algorithms for computing Blackwell-optimal policies and overlooks the pathological behaviors of optimal policies as regards the discount factors. To resolve this issue, in this paper, we show that when the discount factor is larger than  the Blackwell discount factor $\gamma_{\sf bw}$, all discount-optimal policies become Blackwell- and average-optimal, and we derive a general upper bound on $\gamma_{\sf bw}$. Our upper bound on $\gamma_{\sf bw}$, parametrized by the bit-size of the rewards and transition probabilities of the MDP instance, provides the first reduction from average and Blackwell optimality to discounted optimality, without any assumptions, along with new polynomial-time algorithms. Our work brings new ideas from polynomials and algebraic numbers to the analysis of MDPs. Our results also apply to robust MDPs, enabling the first algorithms to compute robust Blackwell-optimal policies.

Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor
Julien Grand-Clément ISOM Department HEC Paris grand-clement cranddcleement@hc... fr
Marek Petrik
Department of Computer Science University of New Hampshire mpetrikêcs unh edu
Abstract
We introduce the Blackwell discount factor for Markov Decision Processes (MDPs). Classical objectives for MDPs include discounted, average, and Blackwell opti- mality. Many existing approaches to computing average-optimal policies solve for discount- policies with a discount factor close to 1, but they only work under strong or hard-to-verify assumptions such unichain ergodicity. We high- light the shortcomings of the classical definition Blackwell optimality, which does not lead to simple algorithms for computing Blackwell-optimal policies and overlooks the pathological behaviors of optimal value functions with respect to the discount factors. To resolve this issue, show that when the discount factor is larger than the Blackwell discount factor Tow, all discount-optimal policies become Blackwell- and average-optimal, and derive general upper bound on Tow- Our upper bound on 7ow: parametrized by the bit-size of the rewards and transition probabilities of the MDP instance, provides the first reduction from average and Blackwell optimality to discounted optimality, without any assumptions, along with new polynomial-time and algebraic numbers to the analysis of MDPs. Our results also apply to robust MDPs, enabling the first algorithms to compute robust Blackwell-optinal policies.
algorithms. Our work brings new ideas from polynomials
Introduction
Markov Decision Processes (MDPs) provide a widely-used framework for modeling sequential (finite) MDP, the decision maker repeatedly interacts with an environment characterized by finite set of states and finite set of available actions. The decision maker follows a policy that prescribes an action a state at every period. instantaneous reward is obtained at every period, depending the current state-action pair, and the system transitions to the next state at the next period. MDPs provide the underlying model for the applications of reinforcement learning (RL), ranging from healthcare (Gottesman et al., 2019) to game solving (Mnih et al., 2013) and finance (Deng et al., 2016).
decision-making problems (Puterman, 2014).
There are several optimality criteria that measure a decision maker's 's performance in an MDP. In discounted optimality, the decision maker optimizes the discounted return, defined as the sum of the instantaneous rewards over the infinite horizon, where future rewards are discounted with a discount factor 7 E [0, 1). average optimality, the decision maker optimizes the average return, defined as the average of the instantaneous rewards obtained over the infinite horizon. The average return ignores any return gathered in finite time, i.c., it does not reflect the transient performance of a policy and it only focuses on the steady-state behavior. The most selective optimality criterion in MDPs is Blackwell optimality (Puterman, 2014). A policy is Blackwellooptimll if it optimizes the discounted return simultancously for all discount factors sufficiently close to 1. Since discount factor close
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

to 1 can be interpreted as preference for rewards obtained in later periods. Blackwell-optimal policies are also average-optimal. However, average-opiimal policies need not be Blackwell-optimal. Blackwell optimality can be useful criterion in environments with no natural, or known, discount factor, Also, any algorithm that computes a Blackwell-optimal policy also immediately computes an average-optimal policy. This is one of the reasons why better understanding the Blackwell optimality criterion is mentioned as " "one of the pressing questions in RL" in the list of open research problems from a recent survey on RL for average reward optimality (Dewanto et al., 2020).
Average-optimal policies can be computed via linear programming (section 9.3, (Puterman, 2014)). However, virtually all of the recent algorithms for computing average-opting policies require strong assumptions on the underlying Markov chains associated with the policies in the MDP instance, such as ergodicity (Wang, 2017). the unichain and aperiodicity properties (Schneckenreither, 2020), weakly communicating MDPs (Wang et al., 2022), or assumptions on the mixing time associated with any deterministic policies (Jin and Sidford, 2020, 2021). These assumptions are motivated by technical considerations (e.g., ensuring that the average reward uniform across all states) and can be restrictive in practice (Puterman, 2014) and NP-hard to verify, such unichain (Tsitsiklis, 2007). Existing methods for computing Blackwell-optimal policies rely on linear programming over the field of power series including negative coefficients (Hordijk et al., 1985), or an algorithm based on a nested sequence of optimality equations (O' Sullivan and Veinott Jr. 2017) which requires to solve multiple linear programs sequentially. These algorithms are complex, difficult to implement, and have no complexity guarantees or known implementations.
In summary, existing algorithms for average optimality require restrictive assumptions, and algorithms for Blackwell-opimmality are very complex. This in stark contrast with the vast literature on solving discounted MDPs, where general and well-understood methods exist, including value iteration, policy iteration, and linear programming (chapter 6, (Puterman, 2014)). This is the starting point of this paper, which aims to develop new algorithms for computing average-optimal and Blackwell-optimal policies through a reduction to discounted MDPs. We make the following three main contributions.
1) A new definition of Blackwell optimality via the Blackwell discount factor "bw E [0, 1). Our first main contribution is to highlight that the standard definition of Blackwell optimality cannot be used to compute Blackwell-optimal policies with simple algorithms. Standard definitions have focused on necessary condition for Blackwell optimal policies to be discount optimal. However, we show that this condition needs to be revised when one seeks to compute a Blackwell- opttimal policy. We do so by highlighting the potential pathological behaviors of the value functions: a Saackwell-optime policy may be optimal on an arbitrary number of arbitrary disjoint intervals, and other non- -lackwlllllll optimal policies may also be discount-optimal for some discount factors very close to 1. Demonstrating this issue is important because previous literature has repeatedly overlooked it. To address this issue, we introduce and show the existence of a discount factor "Tow such that discount optimality for y > Yow is sufficient for Blackwell optimality. Knowing the discount factor "bw is vital because it enables one to compute Blackwell- and average-optimal policies simply by solving a discounted MDP with y (Tow 1). for which there exist well-studied, simple, and efficient algorithms.
2) Upper-bound the Blackwell discount factor. As our second main contribution, we provide strict upper bound on "bo given an MDP instance. We show that an upper bound must depend on r and P. and we compute bound that is parametrized by the number of states and the number of bits required to represent the MDP instance. Solving discounted MDP with a discount factor larger or equal than our strict upper bound returns a glackwell-optimas policy. Crucially, our strict upper bound the underlying struciure of the MDP, which is a significant improvement
requires no assumptions on existing literature. Interestingly, the construction of our upper bound relies on novel techniques for analyzing MDPs. We interpret "/bw [0. 1) the root of a polynomial equation p(7) = 0 in 7 show p(1) = 0, and use a lower bound sep(p) on the distance between any two roots of a polynomial p. known the separation of algebraic numbers. This shows that 7bw < 1 sep(p). where sep(p) depends on the MDP instance. Since Blackwell optimality implies average optimality, we also obtain the first reduction from average optimality to discounted optimality, without any assumption on the MDP structure. Our upper bound on 7bw is itself of polynomial size in the bit-size of the MDP data. Combining this bound with interior-point methods for solving discounted MDPs, we obtain new weakly-polynomin time algorithms for computing Blackwell-optima. and average-optimal policies.
3) Blackwell discount factor for robust MDPs We consider the case of robust reinforcement learning where the transition probabilities are unknown and, instead, belong to an uncertainty set. As our
2

---

third main contribution, we show that the robust Blackwell discount factor "bw. exists for popular models of uncertainty, such as sa-rectan robust MDPs with polyhedral uncertainty (Goyal and Grand-Clément 2023b, Iyengar, 2005). For this setting, we generalize our upper bound on "bw for MDPs to an upper bound on "/w,r for robust MDPs. Since robust MDPs with discounted optimality can be solved via value iteration and policy iteration, we provide the very first algorithms to compute Blackwell-optimal policies for robust MDPs.
We conclude this section with discussion on related works. Several papers study the reduction of average optimality policy to discounted optimality under strong assumptions. Early attempts include (Ross, 1968), assuming that all transition probabilities are lower bounded by e >> 0. Recent extensions assume bounded times of first returns (Akian and Gaubert, 2013, Huang, 2016), or weakly-commmmicating MDPs (Wang et al., 2022). Note that checking that an MDP instance is weakly-communicatin can be done in polynomial assumption (Tsitsiklis, 2007). The case of deterministic MDPs is treated in (Friedmann, 2011 1, Perotto and Vercouter, 2018, Zwick and Paterson, 1996). Other reductions require assumptions on the mixing times of the Markov chains induced by deterministic policies (Jin and Sidford, 2021). (Boone and Gaujal, 2022) propose a sampling algorithm to learn a Blackwell-optimal policy, in special case in which it reduces to bias optimality. Under the condition that the robust MDP is unichain and that there is a unique average optimal policy. (Wang et al., 2023) show the existence of Blackwell policies for sa-rectangular robust MDPs, which is connected to the existence results in (Tewari and Bartlett, 2007) and (Goyal and Grand-Clén Clément, 2023b) for polyhedral uncertainty. In contrast to the existing literature, one of the core strengths of our results is that we do not need any structural assumption on the Markov chains of the underlying MDP to obtain our reduction from Blackwell optimality and average optimality to discounted optimality.
(Kallenherg, 2002), in contrast to the unichain
2 Preliminaries on MDPs
An MDP instance is characterized by tuple M = (S,A. P), where is finite set of states and A is finite set of actions. The instantancous rewards are denoted by r E RSSA and the transition probabilities are denoted by P E (A(S))&xA where A(S) is the simplex over S. At any time period i, the decision maker is in a state 8; E S, chooses an action de E A, obtains an instantaneous reward Ta E R, and transitions to state S I with probability Pata E [0. A deterministic stationary policy π S - A assigns an action to each state. Importantly, there exists an optimal deterministic stationary policy for all the criteria considered in this paper (discounted, Blackwell, and average optimality) (Puterman, 2014), so we simply refer to them as policies and denote them IT induces vector of expected instantaneous reward r, E RRS, defined
as IT A A policy as I' n.s = (s), V 8 E S, as well as a Markov chain over S, evolving via a transition matrix Pa E SxS defined as Pr.as! = (ax(s)s', V s, s' E S. We also write To max{|rsal as E S x A}.
Given a discount factor y E 1) and a policy E 11, the value function D. E R represents the discounted value obtained starting from each state: vT,,. E - 7'r We start with discounted optimality, the most popular optimality criterion in RI. Definition 2.1. Given 7 [0, 1), policy π E II is --disoount-optimal if v.,.. 2 o v n' I E S. We call IT; C IT the set of y-disccunt-oppimall policies.
30 s S
The discount factor 7 E [0, 1) represents the preference for current rewards compared to future rewards. The difficulty of choosing the discount factor y is well recognized in RL (Tang et al., 2021). In some applications. is reasonable to choose values of y close to e.g., in finance (Deng et al., 2016), in healthcare (Garcia et al., 2021, Neumann et al., 2016) or in game solving (Brockman et al., 2016). In other applications, y merely treated as a parameter introduced for algorithmic purposes, e.g., controlling the variance of the policy gradient estimates (Baxter and Bartlett, 2001), or ensuring convergence of algorithms. A discount-optimal policy can be computed efficiently with value iteration, policy iteration, and linear programming (Puterman, 2014). Notably, these algorithms do not require any assumptions on the MDP instance M.
Another fundamental optimality criterion is average optimality, where the average reward 9 e RS
of a policy π E II is g limp T41
P
Ei= aec
80 = s . 8 S. This limit always
3

---

. exists for stationary policies (Puterman, 2014). A policy π is average-optimal gf 2g" e II. Average optimality has been extensively studied in the RL literature, as alleviates the introduction of potentially artificial discount factor. Classical algorithms include relative value iteration (Dong et al., 2019, Yang et al., 2016), and gradient-based methods (Bhatnagar et al., 2007, Iwaki and Asada, 2019). We refer to (Dewanto et al., 2020) for a survey on average optimality in RL.
Several technical complications arise from considering average optimality instead of discounted optimality. First, the average reward g" of a policy is not a continuous function of the policy (e.g.. chapter 4. (Feinberg and Shwartz, 2012)). This can make gradient- a small change in the policy may result in drastic changes in the average reward. Additionally, the Bellman operator associated with the average optimality criterion is not a contraction and may have multiple fixed points. These complications can be circumvented by assuming structural properties on the MDP instance, such as bounded times of first returns and weakly-communicttin MDPs (Akian and Gaubert, 2013, Wang et al., 2022). Some of these assumptions may be hard to verify in simulation environment where only samples are available, or NP-hard to verify even when the MDP instance is fully known, is the case for the unichain assumption (Tsitsiklis, 2007). One of our goals in this paper is to provide a method to compute average-optimal policies via solving discounted MDPs, without any restrictive structural assumptions on the MDP instance. We will do so via the notion of Blackwell optimality.
methods inefficient, since
3 Classical theory of Blackwell optimality
In this section, we describe the classical definition of Blackwell optimality in MDPs and summarize its main limitations. We first give this definition of a Blackwell-optimal policy and outline the proof of its existence. This proof will serve as building block of our main result in Section 4. We then highlight the main limitations of the existing definition of Blackwell optimality.
Existing definition and algorithms. We start with the following classical definition.
Definition 3.1. A policy π is Blackwell-optimall if there exists y [0, 1), such that h E I1 Vn e (7s 1). We call Ul the set of Blackwell-optimal policies.
In short, Blackwell-optimal policy is 7-discount-optimal for all discount factors y sufficiently close to (Blackwell, 1962). This notion has become popular in the field of reinforcement learning, mainly due to its connection to average optimality (Dewanto and Gallagher, 2021). Blackwell optimality bridges the gap between the different optimality criteria: is defined in terms of discounted optimality, yet, crucially. Blackwell-opting Therefore, any advances in computing Blackwell-optimall policies transfer to advances in computing average-optimal policies. A Blackwell-optimal policy is guaranteed to exist for finite MDPs.
policies are average-optimal (theorem 10.1.5, (Puterman, 2014)).
Theorem 3.2 (elaackwell, 1962)). When |S| < +oo, ||| < +oo, there exists at least one Blackwell- optimal policy: 11 * 0.
We highlight the proof of Theorem 3.2 based section 10.1.1 in (Puterman, 2014). Summarizing this proof is important because it is not well-known and serves as a building block for our results.
Step 1. Let म. T' II, s S. Through this paper use the notation $. for 6 ".. : 1 v5,,. We first show that ox has finitely many zeros in [0, 1). This is consequence of the next lemma.
Lemma 3.3. For x E II and s E S, 7 + ve is rational function on [0, 1), i.e., it is the ratio of two polynomials.
Lemma 3.3 follows from the Bellman equation for the value function :²: v.' T 7 P.. There- fore, ox is the unique solution to the equation Ax = b, for b = rx and A = I - 7 Lemma 3.3 then follows directly from Cramer's 's rule for the solution of a system of linear equations: since A is invertible, then Ax = b has a unique solution T, which satisfies x, = det(A.)) (ee(,A), V s E S, with det(-) the determinant of matrix and A, the matrix formed by replacing the s-th column of A by the vector A consequence of Lemma 3.3 is that the function 6_.=' is a rational function, and therefore its zeros are the zeros of a polynomial. This shows that ".. either identically equal to or it has only has finitely many roots in [0, 1).

---

Step 2. We now conclude the proof of Theorem 3.2. Let n E II, E S. If o5 is not identically
equal to O, let 7(T, nT' ,s,s) E [0, 1) be its the largest zero of og. in [o, 1): 7(T, n', .) max e
[0, 1) 00 ug. 0}. We let (TT, n², 8) Of क. is identically equal in [0, 1). We now let
max y(,, ,s)) E,
(3.1)
We have 5 < 1 since there is a finite number of (stationary, deterministic) policies and |S] < +00. Let π be y-discoumt-optimal for a certain > 7. We have, for any s E S, U,,, 2 u V n' E 11. By definition of 7, the map o cannot change a sign on [7, 1) (because it cannot be equal to 0), for any policy r' E and any state & E S, i.e. we have us 2 u..... V n' E 11, E (v, 1). This shows that π remains 7/ ddsccount-optiall for all 7 > 7.. and, therefore, π is Blackwell-optimal.
Remark 3.4. At this point, the reader may wonder if some Blackwell optimal policies are "better" than others, e.g., for instance, if we can find Blackwell optimal policy that is y-discount optimal for Y as small as possible. Interestingly. all Blackwell optimal policies are 7-discount optimal (or not) for the same discount factors. This follows from the key property that the value functions of Blackwell optimal policies coincide for all y E (0, 1) at all states 8 S. Indeed, these value functions must coincide on an entire interval close enough to 1, and they are rational functions. Hence, if they are equal for an infinite number of discount factors, they are equal on the entire interval (0, 1).
To the best of our knowledge, there are only two existing algorithms to compute Blackwell ooptial policy. The first algorithm (Hordijk et al., 1985) formulates MDPs with varying discount factors as linear programs (LPs) over the field of power series with potentially negative coefficients, known as Laurent series. The simplex method for solving LPs over power series explores [0, 1) and computes the subintervals of [0, 1) where an optimal policy can be chosen constant (as a function of y). It returns a Blackwell-optine
policy in a finite number of operations, but there are no complexity guarantees for this algorithm. The second algorithm is based on n n-discount optimality, described with a set of ([S)+ + 1) neeseed equations indexed by n = -1... [S] - that need to be solved sequentially by solving three LPs at each stage (O' Sullivan and Veinott Jr. 2017). This gives polynomial- time algorithm for computing Blackwell-optimal policies, requiring solving 3(S + 1) linear programs of dimension O ((S))- A simpler description is in section 10.3.4 in (Puterman, 2014), but only finite convergence is proved. We are not aware of any available implementations of these algorithms.
Limitations of existing approaches. We now highlight the shortcomings of the existing definition of Blackwell optimality. In particular, we demonstrate that the current approach is insufficient to reduce Blackwell optimality to discount optimality, we show that it does not lead to simple algorithms, and we show that it completely overlooks the potential pathological behaviors of the value functions.
First, Definition 3.1 leads to methods that are significantly more involved than solving discounted MDPs. The two existing algorithms for computing Blackwell-optimal policies handle complex objects, e.g., the simplex algorithm over the field of power series and nested optimality equations with multiple subproblems that need to be solved sequentially. The intricacy of both algorithms makes them difficult to implement, and these algorithms are not widely used in practice.
Second, Definition 3.1 implicitly introduces, for each Blackwell-optimmll policy Ii a discount factor (T)) E [0, 1), defined as the smallest discount factor after which π remains discount-optimal:
7x) min(y e [0,1) x E II, V y e by 1)}.
(3.2)
We now show that x(x) provides insufficient information to compute a Blackwell-optimal policy. Proposition 3.5. There exists an MDP instance M, a Blackwelloppiimal policy x E ITw and discount factors "/1, 722 [0, 1) with "n2 < (T) "12 such that:
1. the policy π is 7/ discoont-oppimal and
2. there exists n' + that is ra-discounn--ppimall and not Blackwell-optimal
Proposition 3.5 shows the naive approach of solving a diiscounted MDP for discount factor > > 7(x) does not compute Blackwellloptimas policy. That is. the policy x' in Proposition 3.5 is optimal for 72 > (TT) but is not Blackwell-optimal. It also shows that 7(T) ) is not even the smallest discount factor for which is discount-optimal. Note that we are the first to highlight this shortcoming of the classical definition of Blackwell optimality. We also note that Proposition 3.5 remains true even under the assumption that MDP instance is unichain,
prove in Appendix A.Overal, we have
5

---

shown that the discount factor 7(T), appearing in the classical definition of Blackwell optimality, cannot be exploited to compute Baackwell-otiimal policy.
The limitation outlined above calls for the definition of another discount factor that can adequately describe when does the set of discount-optimal policies equals the set of Blackwell optimal policies. We introduce this Blackwell discount factor in the next section. The proof of Proposition 3.5 is based on the following very simple example, with [ 8, |A = and deterministic transitions.
Example 3.6. We consider the MDP instance from Figure I. The decision maker starts in state o and chooses one of three actions {a1, 02 0z}; there is no choice in other states, all transitions are deterministic, and the rewards are indicated above the transition ares. The reward for an is 1 and the process transitions to the absorbing state 7, which gives a reward 0f The reward for a2 O, and the process transitions to states 1, 2, 3 before reaching the absorbing state 7. The value functions equal to uaa = r1y + T27? 1/2 r44 + rr37,, uga = 1. Choosing (21,12) = (6, -8) and (ra, (8/3,-16/9) -16/9) gives the value functions shown in Figure I figure). In particular, 22 is the parabola that is equal to at y = O, and equal to at ? E 1//4, and uga the parabola that equal to 0 at ry
and equal its maximum at 7 3/4. This shows that a is Blackwell-optine with 7(a1) 1 /2, Additionally, for 7 E [0, 1/4,, on is " discouunt-optiaal. Finally, ag is Y22 delsscountoppinnee for 7/2 3/4, but it not Blackwell opttmal.
0
F4
4
0.2
0.0
3.0
Discount factor V
Figure 1: MDP instance (left) and value functions (right) for Example 3.6.
In the next proposition, we show that the subintervals of [0. 1) where a policy is discount-optimal may be much more complex than usually alluded to in the literature. In particular, there exists a simple MDP instance with only two policies, but where Blackwell-optine policy may be discount-optimal in an arbitrary number of arbitrary disjoint subintervals of [0, 1).
Theorem 3.7. For any odd integer N E N and any sequence 0- = -o < 7/1 < ... < <N-- < TN = 1, there exists MDP instance (S,A, P) with [S| = N + 1 and |A| = 2, and two policies Tı, T2 such that Tı is the unique optimal policy on any of the intervals (72s. 7/s for = O.., (N - 1)/2
and T2 is the unique optimal policy on (121-1; 72x). for i 1,..., (N 12/2.
Theorem 3.7 shows that the algorithm that explore the entire interval of (0, 1) to compute discount- optimal policies (Hordijk et al., 1985) may visit a number of subintervals that is impractical. We present detailed proof in Appendix B. The proof relies on interpreting value functions as polynomials and using Lagrange interpolation polynomials to tune the instantaneous rewards to ensure that the value functions intersect at the given discount factors. Overall, our results in this section highlight the pitfalls of the existing approach to Blackwell optimality and the potential pathological behaviors of the value functions, even in simple MDP instances. We ameliorate this issue in the next section.
4 Introducing the Blackwell discount factor
This section introduces the notion of the Blackwell discount factor, which we use reduce Blackwell optimality and average optimality to discounted optimality. This reduction leads to algorithms to compute Blackwell-optimal and average policies that are significantly simpler than the state-of-the-ee Intuitively, we need the following condition to reduce Blackwell optimality to discounted optimality: there must exist a discount factor Tbw E [0, 1) such that any 7-discount-optimal policy for 7 > "bw is also / dooiscouutootl for any other 7 Yow. The following definition formalizes this intuition.

---

Definition 4.1. The Blackwell discount factor "bw E [0, 1) is equal to "ow inf(f E (0,1) II
bw V > E (7, 1)), where hww is the set of Blackwell-oprimal policies.
We establish the existence of a Blackwell discount factor in the next theorem.
Theorem 4.2. The Blackwell discount factor "Yow in Definition 4.1 exists in any finite MDP.
Proof. We show that there exists discount factor 7 E (0,1) such that IT. -TT V y (1; 1)- Let 5 defined as in Equation (3.1). We show V 7 E [9, 1), II; Il Let E E5, 1) and let be policy that is o/-discount-optmmal. By definition, we have "7 2 Uy V n E V s E S. Since for
y'> 7, the map 6. does not change sign on [7, 1). This shows that ι is y-discount-optimg a (5, 1). Therefore, is Blackwell optimal, and any p-discount-opimall policy is Blackwell optimal, for any 7 E (5, 1). i.e. this shows 11 C 1h The inclusion 1hn C II follows from the definition of 7: if æ is Blackwell-optimal but not discount-optimal for 7, then it must become discount-optimal for a larger y > 3, which is impossible since y is the largest discount factors where the value functions of any two stationary policies can intersect.
Difference from the existing definition. It is important to claborate on the difference between Definition 3.1 (classical definition of Blackwell optimality) and Definition 4.1 (Blackwell discount factor). While the proof for the existence of 7bw is relatively concise, the distinction between "bw and (T)) has been utterly overlooked in the literature, where it is common find statements that suggest that 7 > 7(T) implies Blackwell optimality of all discount-optimal policies, e.g. in Dewanto and Gallagher (2021), Wang et al. (2023). To the best of our knowledge, we are the first properly introduce the Blackwell discount factor "/h.. to show its sufficiency to compute Blackwell-optimal policies, to emphasize the shortcomings of the classical approach to Blackwell optimality, and to clarify the distinction between "/o and (TT). In particular, in Definition 3.1. Blackwell-optimal policy optimal for any y E (T)) 1). However, for some 7 E [,) there may be other optimal policies that are not Blackwell-optiman instance like this in Example 3.6, where 7bw 3/4 but where 7(1)) = 1/2, and 01 the only ollotnell-optimal policy. Hence in all generality, we may have ((T) < "/bw. and 7(T) * Tbw- Note that the authors in (Dewanto and Gallagher, 2021, Dewanto et al., 2020) also introduce the notation "Thw" but they use it to denote 7(T)..
as shown in Proposition 3.5. We show an MDP
Reduction to discounted optimality. If 7/w is known for a given MDP instance, is straightforward to compute a Blackwell-optimal policy, by solving a discounted MDP with 7 >> "bw- Therefore, the notion of Blackwell discount factor provides a method to reduce the criteria of Blackwell optimality and average optimality to the well-studied criterion of discounted optimality. As we have discussed before, efficient methods for solving discounted MDPs such as value iteration or linear programming have been extensively studied. These algorithms are much simpler than the two existing algorithms for computing Blackwell-optimal policies. Note that it is enough to compute an upper bound on "bw- In particular, if we are able to show that "bo < > for some ? E [0. 1), then following the definition of Town we can compute a Blackwell-opting
policy by solving a discounted MDP with a discount factor 7 7/. Therefore, in the rest of Section 4, we focus on obtaining an upper bound on Tow
4.1 Upper bound on 7bw
We now obtain an instance-dependent upper bound on Yow. i.c.. we construct a scalar (MM) E (0, 1) for each MDP instance M = (8, A, r, P). such that 7bn < n(M). Our main contribution in this section is Theorem 4.4, which gives closed-form expression for 7(M) as a function of the maximum biz-size of the data of the MDP instance M. We start by showing that it is impossible to obtain a bound on "/o that is independent of r or P.
Proposition 4.3. For any 1) > 0, there exists an MDP instance M = (S, with |S| = 2, |A| = 2 and deterministic transitions, such that Yow > 1 1-111 17.
Proof. Let
(81, 82), A = {(ar,a)) a2]. In state 81, action di transitions to 81 (with reward 0)
and action 42 transitions to 82 (with reward -1). There is no action to choose in state 82 which is
absorbing with a reward 6 > O. It is straightforward to check that 02 Blackwell optimal, with
Tbw (1+ -1, so that Tow can be chosen arbitrarily close to 1 by choosing small values for L
7

---

We show that Proposition 4.3 still holds even under the assumption that the MDP instances are in Appendix C. Proposition 4.3 shows that an cettnne-dependent bound on Thu must depend on the "coarseness" of r and P. This suggests parametrizing our upper bound by the bit-sizes of the MDP instance. MDPs with finite bit-sizes parameters are the MDP instances that can be exactly encoded in computer and practically solved by existing algorithms. We first recall the definitions pertaining to bit-size, necessary to describe the complexity of classical weakly-polynone time algorithms like interior-point methods (section 4.6 in (Ben- Tal and Nemirovski, 2001)) and the ellipsoid method (Bland et al., 1981). The bit-size of r E N is [log2 (r)J, the number of bits necessary to represent with standard binary encoding, The bit- of rational number is the sum of the bit-size of its numerator and its denominator. The maximum bit-size of an MDP instance is the maximum bitesize of any rew and Paas' for (s, a') E S x A x S. Its total bit-size is the sum of the bit-sizes of the components of r and P. For instance, in the riverswim instance, the maximum bit-size of the reward is 14, since the largest rewards are bounded by 10a in the terminal states. Our main theorem in this section provides a strict upper bound on Tew as follows.
Theorem 4.4. Let M = AS,
r. P) be an MDP instance with finite bit-size and let m E N be the maximum bit-size of the instance M. Then we have Yow < 1 - m(M), with (MM E (0, 1) defined as
n(M) = 2NN/2+2 (L + + 2 - 1,L = 2- 2-1 Too m 2|5 4
Our proof uses ideas that are new in the MDP literature, such as the separation of algebraic numbers. We provide an outline of the proof below and defer the full statement to Appendix D.
In the first step of the proof, by carefully inspecting the proof's of Theorem 3.2 and of Theorem 4.2, we note that an upper bound for "/ow is n, as defined in (3.1): 7 = max for x, T' E II and s E S, ((T, n², s) is the largest discount factor in [0, 1) for which "5." (7) = 0 when 07.-" y + V , is not identically equal to O, and 0 otherwise. Therefore, we focus on obtaining an upper bound on (TT, n', 8) for any two policies ग, n/' E II and any state 8 E S.
7TT, n'' s). where
In the second step, following Lemma 3.3, the value functions 7 ++ 7 of are rational functions, i.e. they are ratios of two polynomials. Therefore, we interpret क5 (n) = 0 as polynomial equation in y, i.e., as p(>) for certain polynomial p. With this notation, 7(T, n ,'. s) E (0,1) is root of We show that defined for 7 = We then precisely characterize the degree N and the sum I. of the absolute values of the coefficients of the polynomial p, depending on the MDP instance M.
is always a root of p. even though value functions are priori not
Theorem 4.5. The polynomial has degree N- = 2|5 - Moreover, m m has integral coefficients. The sum of the absolute values of the coefficients of m 21 is bounded by L = 2- -T2 -m2(s .45))
In the third step. we lower-bound the distance between any two distinct roots of p. To do this, we rely on the following separation bounds of algebraic numbers.
Theorem 4.6 ((Rump, 1979)). Let p be polynomial of degree N with integer coefficients. Let L be the sum of the absolute values of its coefficients. The distance between any two distinct roots of is strictly larger than > 0, with 1) = 2N- 2.-NN NN/2+2 1L+1)
Recall that 7(m, n;, ,) and are two always roots of p. with (a, .'s) < 1. Combining Theorem 4.5 with Theorem 4.6, we conclude that (TT, x., < <1-)(M) for ((M) > 0 defined as in Theorem 4.4.
Therefore, 7 < TMM,, and 7ow 1- 11-7 (M). This concludes our proof of Theorem 4.4.
Discussion. Using Theorem 4.4, we obtain the first reduction from Blackwell optimality to dis- counted optimality: solving discounted MDP with y 2 1 (MM) returns a Blackwell-optimal policy. Blackwell optimality implies average optimality, so we also obtain the first reduction from average op- timality to discounted optimality without any assumptions on the structure of the underlying Markov chains of the MDP. We also discuss the complexity results for computing a Blackwell-optimal policy
using our reduction. Policy iteration returns a discounted optimal policy in O (0 [IS log
iterations (Scherrer, 2013), but may be slow to converge when 7 = - (MM as Theo- rem 4.4, since v(M) may be close to O. Various algorithms exist to obtain convergence faster than O(1((1 - 7)), such as accelerated value iteration (Goyal and Grand- -léé-mnennn, 2023a) and Anderson acceleration (Zhang et al., 2020). However, note that [log2 (nM))., the bit-size of the scalar n (MM)
8

---

is polynomial in the bit-size of the MDP instance M. Since discounted MDPs can be formulated as linear programs, which can be solved polynomial- time in the input size of the MDP (Ye, 2011), we obtain a weakly-polynomia time algorithm for computing Blackwell-optimal policies. We present the proof of the following theorem in Appendix E.
Theorem 4.7. Let M (S, P) be an MDP instance with total bit-size Q(r, P) E. Then we can compute a Blackwell-optimal policy in O ((ST))A(((TPPP)) arithmetic operations.
Note that with Theorem 4.4 and Theorem 4.7. we have reduced the complex problem of computing a Blackwell optimal policy to a much simpler and well-studied problem: solving a linear program, which can be done in weakly-polynomial time. Potential improvements for our upper bound on Tbu are an important future direction: more precise separation bounds than Theorem 4.6 could be obtained for the specific polynomial p appearing in the proof of Theorem 4.4, or for specific MDP instances, e.g. ergodic or unichain MDPs. Going beyond the case of finite sets of states and actions is interesting but this may be difficult, in both cases there may not exist Blackwell optimal policy anymore (Chitashvili, 1976, Maitra, 1965).
4.2 The case of robust MDPs
In practice, the value function v.ū" may be very sensitive to the values of the transition probabilities P. To emphasize this dependence, in this section we note u...P for the value function associated with a policy и and transition probability P. defined similarly as in Section 2. Robust MDPs (RMDPs) ameliorate this issue by considering an uncertainty set U, which can be seen as a plausible region for the transition probabilities P U. We focus on the case of sa-rectangular MDPs (Iyengar, 2005), where U- = x (s.aeS x Aleaa for Usa S A(S). The worst-case value function . E R of a policy is defined u min pez u...P. Y S. In discounted RMDPs, the goal is to compute robust discounted optimal policy, defined as follows.
Definition 4.8. Given E [o, 1), policy π E II is robust - if a. 2 11, s S. We write rob the set of robust y-discount-optimal policies.
" W' E
Robust Blackwell optimality is studied in (Goyal and Cland-Clément, 2023b, Tewari and Bartlett, 2007), to address the sensitivity of the robust value functions as regards the discount factors. Its connection to average reward RMDPs is discussed in (Tewari and Bartlett, 2007, Wang et al., 2023). Definition 4.9. A policy E is robust Blackwell-optimal if there exists y E [o. 1), such that E m V n E h: 1). We call II,,, the set of robust Blackwell-optimal policies.
(Goyal and Grand-Clément, 2023b) shows the existence of a Blackwell-optimal policy for RMDPs, under the condition that 4/ is sa-tectangular and has finitely many extreme points. This is the case for popular polyhedral uncertainty sets, e.g.. when Uga is based on the l distance, for p E {1, 20) (Givan et al., 1997, Ho et al., 2018, Iyengar, 2005), for some estimated kernel pe and some radius Oss >
Usa = {p E ASS) |pp 1pp-Pal
Poalpp S Jea..
(4.1)
Definition 4.10. We define the robust Blackwell discount factor yow.r E [0, 1) as Tbw, = inf {> e 10, , -I, Vyy E 1),1
We provide a detailed proof of the existence of the robust Blackwell discount factor in Appendix F. The proof strategy is the same as for the existence of the Blackwell discount factor for MDPs. We can obtain the same upper bound on Tbw,r. by studying the values of y for which + U ,'P VT. 7.5
cancels, for any two policies ग, x' E II and any two extreme points P, P' of U. Writing M,, P') for the largest zero in [0, 1) of the function 7 + w...P w w identically equal to zero, or ((T, x², s. P, P') = O otherwise, upper bound on "bw.r for RMDPs can be computed as Ir. defined as 7, = max,,
'P' if it is not
maxp,P''ll... 7 n.. 8, P, P') with Mon the set of extreme points of U. This leads to the following theorem.
Theorem 4.11. Les M = AS, Pd) be an MDP instance with maximum bit-size m E N. Assume that U sa-rectangular, where for each (s, a) E S A, Usa constructed as in (4.1) based on & or foc distance, and with the scalars (Asa)aa of maximum bit-size m. Then Tbn S 1 - n(M), with m(M) defined as in Theorem 4.4 with m² 2m instead of m.
9

---

Based on Theorem 4.11, we obtain the first reduction from robust Blackwell optimality to robust discounted optimality. Since discounted RMDPs can be solved with value iteration or policy iteration, we provide the first algorithms to compute a robust Blackwell-optimal policy for RMDPs with sa-rectangular uncertainty, when the uncertainty set based on the & or the lo distance. Note that there is no known convex (or linear) formulation for RMDPs (Grand-Clément and Petrik, 2022), so we are not able to provide a complexity statement akin to Theorem 4.7.
Conclusion
We highlight the shortcomings of the existing approach to Blackwell optimality and we introduce the Blackwell discount factor to ameliorate this issue. We provide an upper bound for MDPs and RMDPs in all generality, parametrized by the bit-sizes of the instances. Any progress in solving discounted MDPs, one of the most active research directions in RL, can be combined with our results to obtain algorithms for computing average- and Blackwell-optimal policies. Our work also opens new research avenues for MDPs and RMDPs: the proof techniques for our bound on Thw and Tow,r; based the separation of algebraic numbers, instances or different optimality criteria, such as bias optimality or n-discount optimality. The notion of approximate Blackwell optimality well the existence of the robust Blackwell discount factor for other uncertainty sets, e.g., s-rectangular or non-polyhedral sa-rectangular uncertainty sets, or for distributionally robust MDPs, also interesting directions research.
novel and they could be tightened for specific
Funding. J. Grand-Clééent is supported by the Agence Nationale de la Recherche [Grant 11- LABX-0047] and by Hi! Paris. M. Petrik's work supported, in part, by NSF grants 2144601 and 1815275.
References
M. Akian and S. Gaubert. Policy iteration for perfect information stochastic mean payoff games with bounded first return times is strongly polynomial. arXiv preprint arXiv:1310.4990 2013.
M. Akian, S. Gaubert, J. Theory of Computing Systems, 63(5):1089-1130, 2019.
Heand-Clément, and J. Guillaud. The operator approach to entropy games.
J. Baxter and P. L. Bartlett. Infinite-horizon policy-gradient estimation. Journal of Artificial Intelli- gence Research, 15:319-350, 2001.
B. Behzadian, M. Petrik, and C. P. Ho. Fast algorithms for consttaidd s-rectangular robust MDPs. Advances in Neural Information Processing Systems, 34, 2021.
A. Ben-Tal and A. Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM, 2001.
S. Bhatnagar, M. Ghavamzadeh, M. Lee, and R. S. Sutton. Incremental natural actor-critic algorithms. Advances in neural information processing systems, 20, 2007.
D. Blackwell. Discrete dynamic programming. The Annals of Mathematical Statistics, pages 719-726, 1962.
R. G. Bland, D. Goldfarb, and M. Todd. The ellipsoid method: survey. Operations research, 29 (6):1039-1091, 1981.
V. Boone and B. Gaujal. Identification Blackwell policies for deterministic MDPs. 23ème congrès annuel de la Société Française de Recherche Opérationnelle d' A'dde à la Décision, 2022.
G. Brockman, V. Cheung, L.. Pettersson, Schneider, Schulman, J. Tang, and W. Zaremba. OpenAl gym. arXiv preprint 1xXi:1600.005440 2016.
10

---

R. Y. Chitashvili. A controlled finite markov chain with an arbitrary set of decisions. Theory of Probability & Its Applications. 20(())839-844 847, 1976.
E. Delage and S. Mannor. Percentile optimization for Markov decision processes with parameter uncertainty, Operations research, 58(1):203-213, 2010.
Y. Deng, F. Bao, Y. Kong, Z. Ren, and Q. Dai. Deep direct reinforcement learning for financial signal representation and trading. IEEE transactions on neural networks and learning systems, 28(3): 653-664, 2016.
V. Dewanto and M. Gallagher. Examining average and discounted reward optimality criteria in reinforcement learning. arXiv preprint arXiv:2107. (0ti::2077.013360 348, 2021.
V. Dewanto, G. Dunn, A. Eshragh, M. Gallagher, and F. Roosta. Average-reward model-free rein- forcement learning: systematic review and literature mapping. arXiv preprint arXiv:2010.08920. 2020.
K. Dong, Y. Wang, X. Chen, and L. Wang. Q-learning with UCB exploration is sample efficient for infinite-horizon MDP. arXiv preprint arXiv: 10011999011111 2019.
E. Feinberg and A. Shwartz. Handbook of Markov decision processes: methods and applications, volume 40. Springer Science & Business Media, 2012.
O. Friedmann. An exponential lower bound for the latest deterministic strategy iteration algorithms. Logical Methods in Computer Science, 7, 2011.
G. Garcia, I.. Steimle, W. Marrero, and J. B. Sussman. Interpretable policies and the price of interpretability in hypertension treatment planning. Optimization Online, pages 1-46, 2021.
R. Givan, S. Leach, and Dean. Bounded parameter Markov decision processes. In European Conference on Planning, pages 234-246 Springer, 1997.
J. Goh, M. Bayati, S. A. Zenios, S. Singh, and D. Moore. Data uncertainty in Markov chains: Application to cost-effectiveness analyses of medical innovations. Operations Research, 66(3): 697-715, 2018
O. Gottesman, F. Johansson, M. Komorowski, A. Faisal, D. Sontag, F. Doshi-Velez, and L. A. Celi. Guidelines for reinforcement learning in healthcare. Nature medicine, 25(1): 2019.
V. Goyal and J. Grand-Clément. A first-order approach to accelerated value iteration. Operations Research, 71(2):117-535, 2023a.
V. Goyal and J. Grand-Clément. Robust Markov decision processes: Beyond rectangularity. Mathe- matics of Operations Research, 48(1):203-22) 2023b.
J. Grand-Cles wrand-Clémeen and M. Petrik. On the convex formulations of robust Markov decision processes. arXiv preprint XxXiv:2209.101111 10187, 2022.
Grand-Clément, C. W. Chan, V. Goyal, and G. Escobar. Robustness of proactive intensive care unit transfer policies. Operations Research, 71(5):1653-1688, 2022.
C. Ho, M. Petrik. and W. Wiesemann. Fast Bellman updates for robust MDPs. In International Conference on Machine Learning, pages 1979-1988. PMLR, 2018.
C. P. Ho, M. Petrik, and W. Wiesemann. Partial policy iteration for -orbsttt Markov decision processes. Journal of Machine Learning Research, 22(275):1-46, 2021.
A. Hordijk, R. Dekker, and L. C. M. Kallenberg. Sensitivity-analysis in discounted Markovian decision problems. Operations-Research--ppeeee
133:113--55, 1985.
R. A. Horn and C. R. Johnson. Matrix analysis. Cambridge university press, 2012.
W. Hu, C. W. Chan, J. R. Zubizarreta, and G. J. Escobar. An examination of early transfers to the icu based on physiologic risk score. Manufacturing & Service Operations Management, 20(3): 531-549, 2018.

---

J. Huang. Complexity Estimates and Reductions to Discounting for Total and Eherage-Reward Markov Decision Processes and Stochastic Games. PhD thesis, State University of New York at Stony Brook, 2016.
R. Iwaki and M. Asada. Implicit incremental natural actor critic algorithm. Neural Networks, 109: 103-112, 2019.
G. N. Iyengar. Robust dynamic programming. Mathemaliccs of Operations Research, 30(2):257-280, 2005.
Y. Jin and A. Sidford. Efficiently solving MDPs with stochastic mirror descent. In International Conference on Machine Learning, pages 4890-4900, PMLR, 2020.
Y. Jin and A. Sidford. Towards tight bounds the sample complexity of average-reward MDPs, In International Conference on Machine Learning, pages 5055-5005 PMLR, 2021.
L. Kallenberg. Classification problems in mdps. Markov processes and controlled Markov chains, pages 151-165, 2002.
A. Maitra. Dynamic programming for countable state systems. Sankhyā: The Indian Journal of Statistics, Series A, pages 241-248, 1965.
V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Playing Atari with deep reinforcement learning. arXiv preprint arXiv: 2013.
P. J. Neumann, G. D. Sanders, L. B. Russell, J. E. Siegel, and T. G. Ganiats. Cost-effectiveness in health and medicine. Oxford University Press, 2016.
M. O' Sullivan and A. Veinott Jr. Polynomial-time computation of strong and n-present-value optimal policies in Markov decision chains. Mathematics of Operations Research, 42(3):577-598, 2017.
F. S. Perotto and L. Vercouter. Tuning the discount factor in order reach average optimality deterministic MDPs. In International Conference on Innovative Techniques and Applications of Artificial Intelligence, pages 92-105. Springer, 2018.
M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 2014.
M. Ross. Non-discounted denumerable Markovian decision models. The Annals of Mathematical Statistics, 39(2):412-423, 1968.
M. Rump. Polynomial minimum root separation. Mathematics of Computation, 33(145):327--36. 1979.
B. Scherrer. Improved and generalized upper bounds on the complexity of policy iteration. Advances in Neural Information Processing Systems, 26, 2013.
M. Schneckenreither. Average reward adjusted discounted reinforeement learning: Blackwelll optimal policies for real-world applications. arXiv preprint arXiv:2004.00857, 2020.
L. N. Steimle, D. L.. Kaufman, and B. T.. Denton. Multi-model markov decision processes. UISE Transactions, 53(10):1124-11
2021.
Y. Tang, M. Rowland, R. Munos, and M. Valko. Taylor expansion of discount factors. In International Conference on Machine Learning, pages 10130-10140, PMLR, 2021.
A. Tewari and P. L. Bartlett. Bounded parameter Markov decision processes with average reward cri- terion. In International Conference on Computational Learning Theory, pages 263-277. Springer, 2007.
N. Tsitsiklis. Np-Hardness of checking the unichain condition in average cost MDPs. Operations research letters. 35(3):319-323, 2007.
12

---

J. Wang, M. Wang, and L. F. Yang. Near sample-optimal reduction-based policy learning for average reward MDP. arXiv preprint arXiv:2212.00601, 2022.
M. Wang. Primal-dual ' learning: Sample complexity and sublinear run time for ergodic Markov decision problems. arXiv preprini 17X1v:17100061000, 2017.
Y. Wang. A. Velasquez, G. Atia, A. Prater-Bennette, and S. Zou. Robust average-reward Markov decision processes. arXiv preprint arXiv:2301.00858, 2023.
W. Wiesemann, D. Kuhn, and B. Rustem. Robust Markov decision processes. Mathematics of Operations Research, 38(1):153-183, 2013.
S. Yang, Y. Gao, B. An, Wang, and Chen. Efficient average reward reinforcement learning using constant shifting values. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Y. Ye. The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with fixed discount rate. Mathematics Operations Research, 36(4):593-60) 2011.
J. Zhang, B. O'Donoghue, and S. Boyd. Globally convergent type-I Anderson acceleration for nonsmooth fixed-point iterations. SIAM Journal on Optimization, 30(4))3170-31) 2020.
U. Zwick and M. Paterson. The complexity of mean payoff games on graphs. Theoretical Computer Science, 1583433)33,,335, 1996.
13

---

A Unichain instance for Proposition 3,5
We can extend Example 3.5 a unichain MDP as follows: we add transition from state to state O, with reward of O. We also add three intermediate states from 0 to 7 for action d1, so that it takes as many periods to reach state 7 from state for the three actions d1, d2, 03. Note that this new MDP is unichain. We represent it in Figure 3a. Additionally. for this new MDP instance,
have e = 1/(1 - 7²), 2 = (T1" + r24 same expressions as in Example 3.5, up to the common denominator (1 --)= Therefore, we have proved that the same conclusion as Proposition 3.4 holds for unichain MDPs.
7²), og = (T17 + r=y 2) /(1 --"), which are the
B Proof of Theorem 3.7
Proof. Consider the following MDP instance, represented in Figure 2a. The initial state is state where there two actions to be chosen, ai 0g. Action ai yields an instantaneous reward of I and then the decision maker transitions to the absorbing state N, where there is a reward of Otherwise, choosing action d2 yields instantaneous reward ro and takes the decision maker through deterministic sequence of states N,... N 1 with rewards "'...., PN-1, before transitioning to state N. For given 7 E [0, 1), the closed- expressions for the value functions eqt u are ey 1 and uy Et= re7'.
Note that y + u.a polynomial of degree N Using Lagrange interpolation polynomials (section 0.9.11. (Horn and Johnson, 2012)), we can find coefficients To, ..., FNN- such that y + en1 is equal to for all N 1 discount factors "I... YN-1 and equal to 0.9 To 0. The value function eg resulting from this construction is highlighted in Figure 2b for N = 5 and
(70, 71, 72, Ys, Ya. 7s) = (0, 0.2, 0.4, 0.6, 0.8, 1.0). Let us note y H eq - .22.. Our choice of the rewards ensures that is polynomial of degree N - 1, with ((0) > 0, and g(7) = 0 for Y E (7,,... -N Because 7 + 9(>) is a polynomial of degree N with N different real roots, it changes signs at every root. This shows that r ua u is positive on (70.7)) negative on (71, 72). then positive on (72, Ys). etc.. Action is optimal on (7 7x) = (7N-1, because N is odd. This concludes the proof of Theorem 3.7.
V
a
0
N
1.00
Value functions
a2
ro
0.96
0.94
1
r1
NN-1
0.90
0.0
0.2
0.4
0.6
0.8
1.0
Y
(a)
(b)
Figure 2: MDP instance for proof of Theorem 3.7 (Figure 2a) and the value functions for N
(Figure 2b).
C Weakly-communicating instances for Proposition 4.3
Consider the MDP instance from the proof of Proposition 4.3. We now add deterministic transition from state 82 state 81, with reward of for action dn and reward of for action d2. The new MDP instance is represented in Figure 3b.
14

---

a
$
2
a2
0
9
a
d
2
3
f4
4
S
(a) Unichain instance for Proposition 3.5 (b) Weakly-communicating instance for Proposition 4.3
Figure MDP instances to generalize Proposition 4.3 and Proposition 3.5.
First, this MDP instance is weakly commumictti since {s,, $2 is strongly connected under policy d2- In this new MDP instance, we still have v = 0 but og = (-1 + e1)((1 - -)). Hence d2 is
Blackwell optimal when 2 1/c. By choosing c larger than and + 1, we obtain "/ow -> This shows that extend Proposition 4.3 to weakly-communicating MDPs.
D Proof of Theorem 4.4
In this appendix. provide the proof for Theorem 4.4. As noted in Section 4.1, to bound "bw enough to obtain an upper bound on 7(T,, x', for any n, E II and E S such that 7(T, n', s). Since m is the
+ U V is not identically equal to O, since "/ow S maxa, maximum bit-size of the input data, we can write, for any (s, (5,a,8) E S x A x S, Psas' Tssas' / for neass E 'laas' m, and r.a Osa/ /m, Igall S Too- Examples of MDPs with finite bit-sizes include any real instances used for applications where the transition probabilities are estimated as empirical frequencies from some data, c.g. examining patients' transfers in hospitals in (Hu et al., 2018) and GGrand-Clément et al., 2022), MDPs for hypertension treatment (Garcia et al., 2021). diabetes management (Steimle et al., 2021) and cancer detection (Goh al., 2018), as well as the machine maintenance studied in (Wiesemann et al., 2013) and (Delage and Mannor, 2010). We now proceed proving Theorem 4.4.
Step 1.
We start by studying in more detail the properties of the value functions. The following lemma follows directly from Cramer's rule, as explained in Section 3.
Lemma D.1. We have
det (M (7, T))
27 det (I PPp)
(D.1)
with M (7, 8, v) the matrix formed by replacing the s-th column of - - Px by the vector rx-
From Lemma D.I, we have
n(7, 8, x) 7.s
d(7, T)
for n(7, π) = det (M R)) and d( T) = det (I PP))) We choose the letter n for nomina- for and the letter for denominator.
Note that - n17, 8, т) is polynomial of degree at most |S] - while + d(y, is polynomial of degree most |
We have, by definition,
n(y,8,T)) n(7, S,
d(y,T)
d(7, T²)
(,T,s T') s,)7,,
d(p, π )))((i
15

---

Therefore, 17 U. = 0 0 y E [0, 1) implies that 7 is root of the following polynomial equation
y:
p(7) = 0.
(D.2)
for p the polynomial defined as
ply) = s, nln, 8, s')d( x).
(D.3)
Step We now study the properties of the polynomial p. Note that it straightforward that p is
polynomial of degree N = 2|S] 1. We first study the properties of the polynomial + d(T, 7). We have the following lemma.
Lemma D.2. We have
d(7,T) 0, vy (0,
and d(1, = EIT.
Proof of Lemma D.2. This lemma follows from the relation between the determinant of matrix and its eigenvalues, through the characteristic polynomial:
d(7, = det (I yPa)
II (1->A)mM, XESp(P+)
with OxA the algebraic multiplicity of the (potentially complex) eigenvalue À in the spectrum Sp( Px) of P.- Since Px is the transition matrix of Markov chain, we know that the modulus of any eigenvalue À of P, is smaller or equal to 1. This shows that d( T) > 0, 7 E [0, 1), V π E IT. To show d(L, π) 0, we simply note that 1 Sp(Px) since P, the transition matrix of Markov chain.
From Lemma D.2 and the definition of p as in (D.3), it straightforward that p(1) 0.
Lemma D.3. 1 is a root of p.
We now bound the sum of the absolute values of the coefficients of We have the following theorem. Theorem D.A. The polynomial m2 p has integral coefficients, potentially negative. The sum of the absolute values of the coefficients of m| pp bounded by
= 8| -m 2|S| 4|8
Theorem D.4 is based the following three propositions. We note C the binomial coefficient defined as C% fl/k!(e k.).
Propusition D.5. For any E II, the function 7 + d(T,7) )) a polynomial of degree (). Moreover, Y + m (1 7)) is a polynomial with integral coefficients (potentially negative), and the absolute value of its coefficient of degree le is bounded by m Cls)
Therefore, the of the absolute values of the coefficients of m| -d(x,)) is upper bounded by
La = !S |SI.25 2|8)
Proposition D.6. For any policy x II and any state E S, the function 7 + n(758, is polynomial degree - Moreover, 7 m nl(, s, is polynomial with integral coefficients (potentially negative), and the absolute value of its coefficient of degree k is bounded by ml SI Txx Ck -
Therefore, the sum of the absolute values of the coefficients of + ml -n(7, n,(7,,,)) is upper bounded by
I, m S|-11 (5| 1 Noo 111
Proposition D.7. Let = Σ X Q Ex= b, Then PQ Entm xx Ck Enjettz a.by. Additionally, suppose that En= lasl S L.r, En 1byl Lqq Then
m
Σ
loll S LpLQ-
16

---

Combining Proposition D.5, Proposition D.6 and Proposition D.7 with the definition of the polynomial p in (D.3) yields Theorem D.4.
To conclude Step 2 of our proof, let us prove Proposition D.5 and Proposition D.6. Proposition D.7 simply follows from the multiplication rule for polynomials.
Proof of Proposition D.5. By definition,
|
d(n, σ) - det (1-7P=) Σ as (7Px),
k=0
where M ag (M) is the (|S) - k) coefficient of the characteristic polynomial of matrix M. By defimition, (MM is the sum of all the principal minors of size & of M (section 0.7.1, (Hom and Johnson, 2012)). This first shows that ag (TPx) = = ok (P*), and therefore, that
|S|
d(), Σ
au (P*).
We will show that
0& (+)) S Cts) vk=
Let be a principal minor of P. of size k. By definition, g is the determinant of a submatrix M of size & of Px, obtained by deleting rows and columns with the same indices: g = dct(M). For any matrix square M, always have det (M) det(M)). Now Hadamard's inequality shows that (et(M)) s IL= [M 1ll,. with Col((M) T) the i-th column of M T, and therefore we have de S IL (M Ill Note that the columns of M have f--nomm smaller than since P, is a stochastic matrix, and M a submatrix P.. Therefore, S 1. Because there are C possible principal minors of size k of Pa. we have 0g (Px) < C/ V k 1,...,
Of course, we may have a (Px) $ Z. However, for any principal minor g = det(M) of P., we have, by definition the determinant,
(et(M)
Σ s()) II M oEG
Macss
==1
where E(or) the signature of the permutation and 6 is the symmetric group, i.e., the group of all permutations of {1. k.. This shows, by definition m as the maximum bit-size of the input data, that m det(M) E Z. and therefore that m ax (Px) E Z and that m/ aa (Px) S m SS (
(() O
Proof of Proposition D.6. Using Laplace cofactor expansions (section 0.3.1, (Horn and Johnson, 2012)), we have that niv, 8, π) is equal to
C-1 (eri det -onn-ddtttt-- (U-
(D.4)
S'ES
where (I (I- is the matrix obtained from Px by removing the s-th column
and the s'-th row.
Note that + del (I->Pa)s is a polynomial of degree |S| - 1 in 7. Similarly as for the proof of Proposition D.5, m 51 n( s, т) is polynomial of degree |S| 1 with integral coefficients.
Let us consider 1 (s the matrix of dimension (IS) - 1) (|S) - 1), obtained by removing the s-th column and the s'tth row from the identity matrix of dimension |S), and let us call E, the matrix of dimension (|S) - 1) x ([S] - 1). where all rows are except the s-th row, equal to e...
Then del (1- (I==P3)ss(e)sscce)) is equal
del (0
E. E.)
17

---

and therefore is equal to
det ((sss)) + E. - (1 -..)
We notice that (1st.at + E matrix whose rows are exactly the rows of the identity matrix of 1R|5111, up to a certain permutation a E -|s1-1. Let P E (((()-))(((1111 the permutation matrix defined as Pú
if a i and 0 otherwise. Then for any matrix M, we have det M)
det(P=) (et(M) =(o) de)(MM, with e(a) the signature of the permutation Since we always
have E(O) E {-1, 1,, this shows that det ( ((I-)Pa)s(())>aa
is equal to
det (I
((7P7)8((67x0011) +Ex))
The map + det (I-
( (1-((rRass(eexxsik + Exr)) is eequulll to
IS|-1
Σ on ((P3))s(o)xxs116) - Es/ K=
where similarly as for the proof of Proposition D.5, ag (M) is the k-th coefficient of the characteristic polynomial of matrix M, i.e., as (M) is equal the of all the principal minors of M of dimension x k. Let
M (7 ((Px)s(())x8S(() Eg
Note that the entries of each row is smaller or equal to Note that M differs from (7 ()(P))s(s(/xxss only the coefficient of index (s, s'). Using Hadamard's s inequality, we find that that
is substochastic matrix, i..., it has negateie entries and the sum of
(x S 2. ms a& (M) E N. We conclude by combining Equation (D.5) with Equation (D.4).
(D.5)
Step We now lower bound the distance between any two roots of p by scalar v) 7)>> Since we know that for 7(T, n², 8) E [0,1) 1) and 1 are two roots of P, this will show that ((T, a'.)) <
Our proof is based on the following theorem.
Theorem D.8 (Rump, 1979)). Let p be a polynomial of degree N with integer coefficients, possibly with multiple roots. Let L be the of the absolute values of its coefficients. Then the distance between any two distinct roots of p is strictly larger
2N (L 11
Recall that both 7(T,,', 8) E (0,1) 1) and 1 are roots of the polynomial p. Therefore, we can combine Theorem D.8 with Thcorem D.4 to obtain 7(m, T s) < (M), with
(MM 2NN/2+2 (L + 1)
with
N 2|8] -
T- 2-2-- |SS Fox m 2|5] 11
This concludes the proof Theorem 4.4.
Remark D.9. Note that (Akian et al., 2019) use Theorem D.8 to obtain a lower bound on the average rewards of any different policies, in the setting of two-player stochastic games.
Remark D.10. Theorem in (Rump. 1979) provides a separation bound in the case where the polynomial has complex coefficients. Unfortunately, the separation bound from Theorem 1 in (Rump, 1979) not directly usable here, because depends on the discriminant D(p) of the polynomial p, a quantity that is hard to lower-bound (in all generality). We decide to use the bound from Theorem 3 in (Rump, 1979) because does not depend on D(p) but directly on the & -ormm of p and of the degree of p. which can be computed in closed-fore and can be bounded as in Proposition D.6 and Proposition D.5.
18

---

E Proof of Theorem 4.7
Proof of Theorem 4.7. Following table 4 in (Ye, 2011), we know that interior-poing methods for the linear programming formulation of MDPs return optimal policy in O [AS (Q(r, P)))))
arithmetic operations, with Qr, P. 7) equal to the total bit-size of the MDP instance, i.c., the sum of the bit-sizes of all instantaneous rewards, transition probabilities, and the discount factor. By choosing (MM) and noticing that log(n(MM)
O (og(r))()> + |S| log(m)) we see that interior-poing methods for the linear programming formulation of MDPs return an optimal policy in O (|5) 2 (Q(r, P))). where Qr, P) is the total bit-size of MDP instance.
O (IS) log(m))
F Proof of Section 4.2
Proof of the existence of Yow.r- Let
max " n, E El
T(,, n S.PPP"),
-=',P' if is not identically P') (PP)i is the largest zero of the function 7 + u U7 equal to zero, or 7(T, x' s, P') of U.. We will show that II; ) = otherwise. Recall that Mext is the (finite) set of extreme points ww V y %. Let be robust discount-optimal policy for some %. We will prove that ı is Blackwell-opting policy. Since is robust 7-discount-optimal we have
where (T,, s,, s,
7.8 o V EI..
By definition e minpeu 02 v E S. From (lyengar, 2005). we know that the arg min in min u is attained an extreme point of U. Therefore, by definition of 7. the function 7. + 7,88 u 24 cannot be equal to 0 on (Tr, 1), and therefore it does not change sign, since it is continuous function. This shows that for all 7 > Tr. we have
21
14 n' IIS.
This shows the existence of the robust Blackwell discount factor 'ow, and that 7ow.r < Pr.
Proof of Theorem 4.11. We start by showing the following lemma.
Lemma F.1. Let M M= Ar, PO) be an MDP instance with maximum bit-size m E N. Assume that is sa-rectangular, where for each (s,a) E A, Usa is constructed as (4.1), with the scalars ((Kaa) of maximum bit-size
Then the maximum bit-size complexity to describe the transition probabilities associated with the extreme points Usa is m' for p and 2m' for p =1
Proof of Lemma F.l. In the proof of this lemma, we use the fact that the worst-case kernel P* of policy can be chosen the arg min of the optimization problem minpel4.0s) P uz74 where w. the worst-case value function of æ. particular, let R.S.
The case = cc. this case, there exists sorting solution to millpeu, p To for any (s, a) e and any v E R by sorting v, see for instance proposition in (Givan et al., 1997), or appendix C in (Behzadian et al., 2021). 1). In particular, let (s, a) E S x A and define the permutation of S such that fo(1) I ... S (o(()))> and define the smaller integer in f1.... } such that
(Goh et al., 2018), equation (9)
|S| Σ
po Poao(ss)) + asa)
po Poao(s') -ssa) 1.
19

---

Then solution to minpell.a p'v s' > i, and
v is Par(s))
Ph sag(s) + asa if s' < i, Po(e) = -Po saa((s)) asa if
Σ
Po(i)
Pa(s))
s'ES(()
This closed-form shows that for any vector v E R a solution minpeu... p v can be found as a vector with rational entries with denominator of at most m.
The p 1. In this case, formulated as a linear program. Therefore, there exists an optimal basic feasible solution p which has the following form lemma 5.4 and lemma 5.5 in (Ho al., 2021). There exist J1, E S such that ji + j2 and for each E I = S {2:
show that the optimization problem minpel4,. p v can be
= 0 or = sat
Pj
P safi
and
Pie
pu saj2
Then, in order for p E Uoa we need the following equalities
to hold
Pir + Pia =1 Σn
iEI
(pj pagh)
(Ponja
-Pia) asa
Σ
Ip:
p0
IEI
Combining the equalities above yields that
2p
Ussa
Σ
Ppi
P
Phoji
Saja
iEI
1
Σ
Pi-
iEI
Because the right-hand side of the equation above is of rational numbers with denominator of at most m, Pý is also rational with denominator at most 2m. Using an analogous argument for Pia- we get that there exists an optimal solution that is rational with denominator of at most 2m.
Theorem 4. then follows by applying Theorem 4.4 with on the MDP instance (S, A. r. P') with p' an extreme point of 2. Lemma F.1 exactly deseribes the maximum bit-size of any transition P for (s, a, s') E S x A x S in the case of sa-rectangular uncertainty set based on & disittance or -x-distance as in (4. 1). This concludes the proof of Theorem 4.
20


Reviews:
[{"review_id": "dDbb5xfeZs", "reviewer": "Reviewer_uLuR", "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.", "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? \nIt 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. \nIt 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. \nCan the results for robust MDPs be used in the setting where we define confidence sets using data?\n", "limitations": "Limitations (e.g. what to do when we don’t know the MDP) are discussed briefly but could be discussed in more detail.\n\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "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. \nLastly, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for your review and suggestions. We answer your remarks and questions below.\n\n*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.*\n\nWe agree that the immediate practical utility of our bounds is limited. However, we believe that this result can serve as an important foundation for future theoretical and practical implications. As you observe, our upper bound on $\\gamma_{\\sf bw}$ is close to one, but the number $1 -\\gamma_{\\sf bw}$ has a number of bits that is polynomial in the size of the MDP. Theorem 4.7 then shows that the Blackwell optimal policy can be computed in polynomial time using an LP solver. Moreover, we introduce new techniques for bounding the Blackwell optimality, which can be used in the future to further refine the upper bound on the Blackwell discount factor.\n\n*I also wonder whether this work could be better suited to another venue.*\n\nWe believe this is relevant to NeurIPS, particularly because the notion of Blackwell optimality in MDPs and robust MDPs has received increased attention in the reinforcement learning community (such as Dewanto et al. (2020) and (2021), Jin et al. (2021), Tang et al. (2021), Yang et al. (2016)). Our results help to rigorously establish a fact that has been used implicitly (without proofs) in recent work. If you still think that it is not a good fit, we would appreciate suggestions for an alternative venue.\n\n*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?*\n\nThank you, that is a great suggestion. We agree that an example would make the results more approachable. For example, the bit-size for riverswim would be about 14 because the number is the largest bit-size is the reward 10,000 in the terminal state. We will add such an example in the revision. \n\n*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*\n\nWe agree that plotting the discount factor as a function of an MDP parameter would be interesting. We will add such a plot in the final version of the paper. \n\n*Can the results for robust MDPs be used in the setting where we define confidence sets using data?*\n\nThat is an interesting question. Yes, the results also apply to any MDP or robust MDP regardless of how this MDP is constructed. In fact, our Theorem 4.11, which bounds the Blackwell discount factor for robust MDPs is specifically for uncertainty sets based on $\\ell_{1}$ or $\\ell_{\\infty}$ balls. These distances are used to construct uncertainty based on some data, see section 6.2.3 in [1] for healthcare applications and section 6 in [2] for methodology. \n\n\n[1] Grand-Clement, Julien, Chan, Carri W., Goyal, Vineet, et al. Robustness of Proactive Intensive Care Unit Transfer Policies. Operations Research, 2022.\n\n[2] Behzadian, Bahram, Russel, Reazul Hasan, Petrik, Marek, et al. Optimizing percentile criterion using robust MDPs. AISTATS 2021.\n"}, {"review_id": "HI6lUtswZE", "reviewer": "Reviewer_mmfD", "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.", "questions": "Line 177: It should be \"we use the notation...\".\n\nLine 319: It is not clear to me what \"coarseness\" is and how Proposition 4.3 shows this dependence.", "limitations": "Please see the questions above.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank you for your time reviewing the paper. \n\n*As regards coarseness and Proposition 4.3:* Our goal is to obtain an upper bound on the Blackwell discount factor $\\gamma_{\\sf bw}$ for a large class of MDP instance. Proposition 4.3 shows that without any condition on the rewards $\\boldsymbol{r}$ and the transition probabilities $\\boldsymbol{P}$, we may have $\\gamma_{\\sf bw}$ as close to $1$ as we want by letting the instantaneous reward approaching $0$ (see the proof of Proposition 4.3). Inspecting the proof of Proposition 4.3, we note that $\\gamma_{\\sf bw} \\rightarrow 1$ when the minimum difference between two instantaneous rewards (called $\\epsilon$ in the proof) approaches $0$. Therefore, we study the class of MDP instance with bit-size bounded by $m \\in \\mathbb{N}$, for which there is a lower bound on the minimum difference between two instantaneous rewards, i.e., for which $\\epsilon \\geq \\frac{1}{m}$. This is what we refer to as ``coarseness''. For this class of MDP instance, we can prove a uniform upper bound on $\\gamma_{\\sf bw}$, as shown in Theorem 4.4.\n\nWe would also like to note that during this rebuttal, we have noticed that we can extend Proposition 3.4 (shortcomings of the existing definition of Blackwell optimality) and Proposition 4.3 to the case of weakly-communicating MDPs. This strengthens our contributions by showing that the shortcomings of previous work that we identify in our paper also occur under the most common structural assumptions. \n\n*Extending Proposition 3.4/Example 3.5 to unichain/ergodic MDPs:* We can extend Example 3.5 to a unichain MDP as follows: we add a transition from state $7$ to state $0$, with a reward of $0$. We also add three intermediate states from $0$ to $7$ for action $a_{1}$, so that it takes as many periods to reach state $7$ from state $0$ for the three action s$a_{1},a_{2},a_{3}$. Note that this new MDP is unichain. We refer to Figure 1 in the PDF attached to our response common to all reviewers.\n\n\nAdditionally, for this new MDP instance, we have $v_{\\gamma}^{a_{1}} = 1/(1-\\gamma^5), v_{\\gamma}^{a_{2}} = (r_{1}\\gamma + r_{2}\\gamma^2)/(1-\\gamma^5), v_{\\gamma}^{a_{3}} = (r_{4}\\gamma + r_{5}\\gamma^2)/(1-\\gamma^5)$, which are exactly the same expression as for Example 3.5, up to the common denominator $(1-\\gamma^5)^{-1}$. Therefore, we have proved that the same conclusion as Proposition 3.4 holds for unichain MDPs. We thank you for raising this interesting point; we will use the additional page available for our final version to mention this new result.\n\n*Extending Proposition 4.3 to weakly-communicating MDPs:*\nFor this, we can add a deterministic transition from state $s_2$ to state $s_1$, with a reward of $0$ for action $a_{1}$ and a reward of $\\epsilon$ for action $a_{2}$. We refer to Figure 2 in the PDF attached to our response common to all reviewers.\n\n First, the MDP instance is weakly-communicating since $\\{s_{1},s_{2}\\}$ is strongly connected under policy $a_{2}$. In this new MDP instance, we still have $v_{\\gamma}^{a_{1}} = 0$ but $v_{\\gamma}^{a_{2}} = (-1+\\epsilon \\gamma)/(1-\\gamma)$. Hence $a_2$ is Blackwell optimal when $\\gamma \\geq 1/\\epsilon$. By choosing $\\epsilon$ larger than $1$ and $\\epsilon \\rightarrow 1$, we obtain $\\gamma_{\\sf bw} \\rightarrow 1$. This shows that we can extend Proposition 4.3 to unichain MDPs. We thank you for raising this interesting point; we will add this new result in the final version of our paper.\n\n### Conclusion.\n\nWe hope that our responses convince you of the completeness and significance of our paper and lead to an increased score."}, {"review_id": "sXW1eAnmOJ", "reviewer": "Reviewer_MXst", "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.", "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$?\n2. Is it NP-Hard to verify weakly-communicating assumption?", "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.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\nThe 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. \n", "weaknesses": "Certain writings and motivation may be taken care:\n1. 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.\n2. 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.\n3. 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. \n4. 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$. \n5. 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.\n\nMinor comments:\n1. Line 247: the authors mentioned “in the next proposition”, while it is a Theorem that follows.\n2. Theorem 4.5, Theorem 4.6 should be stated as a Lemma.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your time reviewing the paper and for your constructive comments. We will answer your questions and remarks below.\n\n### Writing and motivations.\n\n*Points 1-2-3*. We will make these two points more explicit in our final version. Thanks for the clarification.\n\n*Point 4*. Thanks for raising this interesting point. One key property of Blackwell optimal policies (that we did not highlight in the paper) is that *their value functions coincide for all $\\gamma \\in (0,1)$ for all states $s$*. This is because their value functions must coincide on an entire interval close enough to $1$, for instance, for $\\gamma \\in (\\gamma_{\\sf bw},1)$. Since the value functions are rational functions (ratios of polynomials), if they are equal for an infinite number of discount factors, then they are equal on the entire interval $(0,1)$. Therefore, all Blackwell optimal policies are $\\gamma$-discount optimal (or not) for the same set of discount factors. We will add this discussion in the revised version of our manuscript.\n\n*Point 5. Connection with robust MDPs.* We have worked to extend our results on Blackwell optimality to the case of robust MDPs for mostly two reasons. First, from a practical standpoint, this allows us to (partially) address the situation where the data of the MDP instance (rewards and/or transition probabilities) is only partially known. Second, from a methodological standpoint, there has been some recent interest in studying average optimality for the case of robust MDPs [1,2]. Since Blackwell optimality bridges the gap between discounted optimality and average optimality for *nominal* MDPs, we believe that a better understanding of Blackwell optimality for *robust* MDPs is a first step toward new insights for the case of average optimality in robust MDPs as well.\n\n[1] Wang, Yue et al. Robust average-reward Markov decision processes. AAAI 2023.\n\n[2] Wang, Yue et al. Model-Free Robust Average-Reward Reinforcement Learning. ICML 2023.\n\n### Questions.\n\n1. It is *not* the case that $\\gamma_{\\sf bw} = \\max_{\\pi} \\gamma(\\pi)$. This is discussed in the paragraph line 282 - 296 (specifically, line 292-294): in Example 3.5, we have $\\gamma_{\\sf bw} = 3/4$, but there is a single Blackwell optimal policy $a_{1}$ and $\\gamma(a_{1}) = 1/2$. This discrepancy is what makes introducing the notion of the Blackwell discount factor one of our important contributions. \n\n2. Verifying that a nominal MDP is weakly communicating can be done in polynomial time; see Algorithm 4 and Theorem 3.5 in [3]. The unichain property is NP-hard to verify for nominal MDPs; see [4]. We are not aware of any algorithm for verifying the weakly-communicating property for robust MDPs. We will make this clearer in our manuscript. \n\n[3] Kallenberg, L. C. M. Classification problems in MDPs. Markov processes and controlled Markov chains, 2002, p. 151-165.\n\n[4] J. N. Tsitsiklis. NP-Hardness of checking the unichain condition in average cost MDPs. Operations research letters, 35(3):319–323, 2007.\n\n### Conclusion.\n\nWe hope that our responses convince you of the completeness and significance of our paper and lead to an increased score."}, {"review_id": "7UXuEFecNx", "reviewer": "Reviewer_LSPb", "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.", "questions": "See above.", "limitations": "Limitations have been discussed. No potential negative societal impact", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "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)\n2. 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\n3. 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?\n2. 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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank you for your detailed comments. We will answer your questions below.\n\n*Q1 - conservativeness of our bound on $\\gamma_{\\sf bw}$.* You are correct that our bound on $\\gamma_{\\sf bw}$ may be loose. In particular, it relies on Theorem 4.6 (separation between the different roots of a polynomial), which may not be tight for the specific polynomials related to the value functions of the MDP instance. Even though the current approach results in a weakly-polynomial time algorithm, improving this bound is certainly an important future direction. We also note that Proposition 4.3 shows that $\\gamma_{\\sf bw}$ may be very close to $1$ even in some extremely simple MDP instances (two actions, one absorbing state, one non-absorbing state, deterministic transitions). Also, we can extend Proposition 3.4 (which shows the shortcoming of the existing definition of Blackwell optimality) to the case of unichain MDPs. This can be done as follows.\n\n*Extending Proposition 3.4/Example 3.5 to unichain/ergodic MDPs:* We can extend Example 3.5 to a unichain MDP as follows: we add a transition from state $7$ to state $0$, with a reward of $0$. We also add three intermediate states from $0$ to $7$ for action $a_{1}$, so that it takes as many periods to reach state $7$ from state $0$ for the three action s$a_{1},a_{2},a_{3}$. Note that this new MDP is unichain. We refer to Figure 1 in the PDF attached to our response common to all reviewers.\n \nAdditionally, for this new MDP instance, we have $v_{\\gamma}^{a_{1}} = 1/(1-\\gamma^5), v_{\\gamma}^{a_{2}} = (r_{1}\\gamma + r_{2}\\gamma^2)/(1-\\gamma^5), v_{\\gamma}^{a_{3}} = (r_{4}\\gamma + r_{5}\\gamma^2)/(1-\\gamma^5)$, which are exactly the same expression as for Example 3.5, up to the common denominator $(1-\\gamma^5)^{-1}$. Therefore, we have proved that the conclusion of Proposition 3.4 holds for unichain MDPs. We thank you for raising this interesting point; we will use the additional page available for our final version to mention this new result.\n\nWe are also able to extend Proposition 4.3 to weakly-communicating MDPs. We refer to our response to reviewer mmfD for the exact computations and to Figure 2 in the PDF attached to our response common to all reviewers. We will add these new results in our revised manuscript. \n\n*Q2. Experimental validation.*\n\nWe see our primary contribution as a better theoretical understanding of Blackwell optimality in (nominal MDPs and robust MDPs. We are the first to highlight the notion of the Blackwell discount factors as a more refined tool to obtain Blackwell optimal and average optimal policies, whereas many papers before us were incorrect about when Blackwell optimal policies are optimal or not (see the discussion lines 282-296). We are also the first to show that we can use tools from polynomial analysis to study Blackwell optimality. Finally, our paper is the first to provide a very simple algorithm to compute Blackwell/average optimal policies (through discounted MDPs), even though the notion of Blackwell optimality has been around since the 1960s (see the last paragraph before section 3.2). We leave obtaining a more refined and implementable upper bound as future work. \n\nWe conclude this remark by noting that most of the recent and notable works in this area do not focus directly on the implementation of the proposed algorithms, e.g. [1,2,3,4,5]. We see our work as a first step toward advancing the methodology and the understanding of an understudied optimality criterion (Blackwell optimality).\n\n[1] Wang, Jinghan, Wang, Mengdi, et Yang, Lin F. Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP. arXiv preprint arXiv:2212.00603, 2022.\n\n[2] Jin, Yujia et Sidford, Aaron. Efficiently solving MDPs with stochastic mirror descent. ICML 2020.\n\n[4] Wang, Mengdi. Primal-Dual $\\pi $ Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems.arXiv preprint arXiv:1710.06100, 2017.\n\n[5] Chen, Yichen et Wang, Mengdi. Stochastic primal-dual methods and sample complexity of reinforcement learning. arXiv preprint arXiv:1612.02516, 2016.\n\n### Conclusion. \nWe thank you for your detailed questions. We are looking forward to hearing your new thoughts, and we hope that we have answered your questions and concerns and that you will consider increasing your score."}, {"review_id": "vCXQ839ZkK", "reviewer": "Reviewer_ePug", "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.", "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.\n2. what is m in your theorem 4.4? \n3. Proposition 4.3: \\eta >0 → 1>\\eta>0", "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.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well written and organized.  The insights behind the main results are well presented.\n2. The introducing of the Blackwell discount factor is interesting, it may lead to efficient algorithms in future studies.\n3. 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.\n2. Proposition 4.3 is only for the deterministic transitions with $S=2, A=2.$\n3. The $ \\eta$ in Theorem is quite close to zero, which means the upper bound for $\\gamma_{bw}$ is almost 1. \n4. No simulation results are provided, it is better the show the advantage of the proposed approach with even some simple simulations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for your review. We first answer the weaknesses.\n\n1. Note that our bound on $\\gamma_{\\sf bw}$ leads to a *polynomial* algorithm; we refer to Theorem 4.7 for the complexity statement. Polynomial-time complexity is commonly understood as {\\em tractable} empirical performances. Our bound requires the knowledge of the number of states and actions, and the *maximum bit-size* of the MDP. This bit size is simply determined by (a) an upper bound of the rewards and (b) by the distance of positive transition probabilities to 0. The term (a) can be estimated since we only need an upper bound. The term (b) can be estimated when we build the transition probabilities as the empirical frequencies of the observed transitions from historical data, i.e., as $P_{sas'} = n_{sas'}/n_{sa}$ with $n_{sas'}$ the number of observation of the transition $s,a$ to the next state $s'$ and $n_{sa}$ the number of observation the state-action pair $s,a$.\n\n2. We wrote Proposition 4.3 with the simplest MDP instance. We can add fictitious states/actions and non-deterministic transitions to this instance to show that the same conclusion holds with more states/actions/complicated transitions. We can also extend Proposition 4.3 to weakly-communicating MDPs. For this, we add a deterministic transition from $s_2$ to $s_1$, with a reward of $0$ for $a_{1}$ and a reward of $\\epsilon$ for $a_{2}$ (see Figure 2 in the PDF attached to our response common to all reviewers). This MDP is weakly-communicating: $\\{s_{1},s_{2}\\}$ is strongly connected for $a_{2}$. We have $v_{\\gamma}^{a_{1}} = 0, v_{\\gamma}^{a_{2}} = (-1+\\epsilon \\gamma)/(1-\\gamma)$. Thus $a_2$ is Blackwell optimal for $\\gamma \\geq 1/\\epsilon$. With $\\epsilon \\geq 1, \\epsilon \\rightarrow 1$, we have $\\gamma_{\\sf bw} \\rightarrow 1$. This extends Proposition 4.3 to unichain MDPs. We thank you for raising this interesting point, we will add this new result.\n\n3. *The $\\eta$ in Theorem is close to zero.*\n\nAssuming that you are referring to Theorem 4.4, we agree that the bound on $\\gamma_{bw}$ is close to 1, which complicates the practical use of this result. However, we would like to clarify that $1-\\gamma_{bw}$ is sufficiently large to have a polynomial sized representation. This fact is used to construct a polynomial-time algorithm in Theorem 4.7.\n\n4. *Experimental validation.*\n\nWe see our primary contribution as a better understanding of Blackwell optimality in nominal/robust MDPs. We are the first to highlight the notion of the Blackwell discount factors as a more refined tool to obtain Blackwell optimal and average optimal policies, whereas many papers before us were incorrect about when Blackwell optimal policies are optimal or not (see the discussion lines 282-296). We are also the first to show that we can use tools from polynomial analysis to study Blackwell optimality. Crucially, our paper is the first to provide a very simple algorithm to compute Blackwell/average optimal policies (through discounted MDPs), even though this notion has been around since the 1960s (see the last paragraph before section 3.2). We leave obtaining a more refined upper bound as future work. We conclude by noting that most of the recent works in this area do not focus directly on the implementation of the proposed algorithms [1,2,3,4,5]. Our work is a first step toward advancing the methodology and the understanding of an understudied optimality criterion (Blackwell optimality).\n\n[1] Wang, Wang, and Yang. Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP. \n\n[2] Jin and Sidford. Efficiently solving MDPs with stochastic mirror descent. ICML 2020.\n\n[4] Wang Primal-Dual $\\pi $ Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems. 2017\n\n[5] Chen and Wang. Stochastic primal-dual methods and sample complexity of reinforcement learning. 2016.\n\n### Questions.\n\n*Q1.* While the existing definition has been introduced for more than 60 years, there exists no public implementation of any algorithm to compute a Blackwell optimal policy; the reasons for this being that algorithms for this task are all quite involved and impractical, see lines 209. Therefore, while the definition of Blackwell optimality is important, it does not lead to efficient algorithms. This is why we see our introduction of the Blackwell discount factor as an important step toward a tractable approach to Blackwell optimality, which has been missing for more than six decades. \n\n*Extending Proposition 3.4 to unichain/ergodic MDPs:* We can extend Example 3.5 to a unichain MDP as follows: we add a transition from state $7$ to state $0$, with a reward of $0$. We also add three intermediate states from $0$ to $7$ for action $a_{1}$, so that it takes as many periods to reach state $7$ from state $0$ for the three action s$a_{1},a_{2},a_{3}$. This new MDP is unichain; see Figure 1 in the PDF attached to our response common to all reviewers.\nWe have $v_{\\gamma}^{a_{1}} = 1/(1-\\gamma^5), v_{\\gamma}^{a_{2}} = (r_{1}\\gamma + r_{2}\\gamma^2)/(1-\\gamma^5), v_{\\gamma}^{a_{3}} = (r_{4}\\gamma + r_{5}\\gamma^2)/(1-\\gamma^5)$, which are the same expressions as for Example 3.5, up to the denominator $(1-\\gamma^5)^{-1}$. Therefore, we proved Proposition 3.4 for unichain MDPs. We thank you for raising this interesting point, we will mention this new result in our final version.\n\n2. The integer $m$ is the maximum bit-size of the MDP instance, defined line 319. Intuitively it is the $\\log_2$ of the denominator in the fractional representation of the rewards $r_{sa}$ and the transitions $P_{sas'}$. More details on this are given in Appendix B. For instance, for Riverswim we have $m=14$ since the maximum reward is $10,000$.\n\n3. We will clarify that $\\eta \\in (0,1)$, thanks.\n\n### Conclusion.\nWe thank you for your detailed questions, which lead to an improved manuscript. We hope that our responses convince you of the completeness and significance of our paper and lead to an increased score.\n\n"}, {"review_id": "ZwA4OukUX0", "reviewer": "Reviewer_TMw8", "summary": "The paper introduces the Blackwell discount factor MDPs.\nThe 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. \n\nI 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. \n\n", "questions": "1)\tMay you please provide concrete motivation for the use in Blackwell optimality criterion and/or a concrete application? \n2)\tErgodicity 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.\n", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "\n1)\tThe assumptions and contributions are clearly stated.\n2)\tIt seems that the presented results improve the known results in the study of Blackwell optimality criterion, remove commonly used assumptions and provide efficient algorithms.  \n3)\tThe application of algebraic techniques to RL might be useful in other settings.\n", "weaknesses": "\n1)\tNo concrete application or motivation for the work is given.\n2)\tIt 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.\n3)\tThe authors claim throughout the paper that previous literature repeatedly mentioned the discussed problem as important, but not clearly mentioned why.\n4)\tThe 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.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your time reviewing the paper and for your constructive comments. We answer your questions and remarks below.\n\n*Motivation and applications of Blackwell optimality.* The motivation for Blackwell optimality mostly comes from some of the shortcomings of the two other return criteria. \n\n* The discounted return criterion enjoys nice tractability properties: it can be solved efficiently *without any structural assumptions on the MDP*. However, this requires choosing a value for the discount factor $\\gamma$, which may be artificial in some applications. Additionally, the optimal policies may change with the discount factors. These issues are well-documented in the RL/MDP community [1]. \n\n* For this reason, *average optimality* is getting some attention in the RL literature [2], especially since many RL applications require extremely long horizons, e.g. in game-solving (the game may end after thousands of decisions) or in healthcare (the health condition of the patient in a far horizon remains an important concern). However, average optimality suffers from its own shortcomings: (a) the vast majority of the literature requires some structural assumptions (unichain, ergodicity, weak-communication, etc.), mostly motivated from a technical standpoint; (b) the case of adversarial/robust MDP is still not very well understood for average optimality; (c) most importantly, average optimality discards {\\em any} rewards obtained in a finite horizon. So it does not distinguish between a policy $\\pi_{1}$ achieving rewards $0 + 0 + 0 + 0 + ... + 1 + 1 + ...$, where the $0$'s are repeated a $1000$ times before switching to $1$ forever, and a policy $\\pi_{2}$ achieving rewards $1 + 1 + ...$ which always obtains $1$. Clearly, $\\pi_{2}$ is a better policy, but it attains the same average reward as $\\pi_{1}$. \n\n* This very shortcoming of average optimality is addressed by Blackwell optimality. Indeed, since a Blackwell optimal policy is optimal for all discount factors close to $1$, it also takes into account the rewards obtained in finite times. Additionally, there is no need to choose a specific value of the discount factor, in contrast to discount optimality. In fact, one can show that Blackwell optimal policies are average optimal but also optimizes the {\\em bias} (i.e., the rewards obtained in the transient regime where the Markov chain converges to its stationary distribution), and higher-order terms, as explained in Section 10.2 in [3]. Still, although six decades have passed since Blackwell optimality was introduced in [4], there are still no efficient algorithms to compute a Blackwell optimal policy. As detailed in our paper, all existing algorithms are so complicated that we are not aware of any practical implementations of these ideas. We view our work as a first step toward a tractable approach to Blackwell optimality by providing an algorithm (solving discount optimal policy for $\\gamma > \\gamma_{\\sf bw}$) that is conceptually much simpler than previous methods. Our Theorem 4.7 shows that our algorithm is weakly-polynomial, matching the most widely accepted class of {\\em efficient algorithms. We would also like to emphasize that we are the first to show the shortcomings of the existing definition and to clarify some misunderstandings (see page 5, Proposition 3.4).}\n\n We will use the additional page available for the final version to clarify this and highlight the positioning of our work.\n \n [1] Y. Tang, M. Rowland, R. Munos, and M. Valko. Taylor expansion of discount factors. ICML 2021.\n\n [2] V. Dewanto, G. Dunn, A. Eshragh, M. Gallagher, and F. Roosta. Average-reward model-free reinforcement learning: a systematic review and literature mapping.\n \n [3] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 2014.\n \n [4] D. Blackwell. Discrete dynamic programming. The Annals of Mathematical Statistics, pages 719–726, 1962.\n\n*Common structural assumptions such as ergodicity/weak-communication*. Our goal is to study Blackwell optimality (and consequently average optimality) in all generality. In the course of this rebuttal, we have noticed that our Example 3.5 (shortcomings of the existing definitions of Blackwell optimality) and Proposition 4.3 (need for ``coarseness'' conditions to bound $\\gamma_{\\sf bw}$) can be extended to the case of weakly-communicating and unichain MDPs. Therefore, the issues identified in this paper still remain under some of the most common structural assumptions on the MDP instance. We refer to the PDF attached to our response common to all reviewers for the new MDP instances and to our response to Reviewer mmfD for the detailed computations.\n\n### Conclusion.\nWe thank you for your time reviewing the paper and your detailed questions, which will lead to an improved manuscript. We are looking forward to hearing back from you and we hope that our responses convince you of the completeness and significance of our paper and lead to an increased score."}]

Author rebuttal:
Dear editorial teams

We would like to thank all the reviewers for their constructive feedback. We provide our answers to all reviewers individually. 

We would like to note that we have extended Proposition 3.4 (shortcomings of existing definition of Blackwell optimality) and Proposition 4.3 (need for some ``coarseness" condition to bound the Blackwell discount factor $\gamma_{\sf bw}$) to the case of weakly-communicating MDPs. We present the detailed computations for each reviewer who mentioned it. We also attach here the PDF with the new weakly-communicating MDP instances for our proofs of Proposition 3.4 (Figure 1) and Proposition 4.3 (Figure 2).  This strengthens our contributions by showing that the shortcomings of previous work that we identify in our paper also occur under the most common structural assumptions.

We hope that our responses convince you of the completeness and significance of our paper and we are looking forward hearing back from the reviewers.





Meta-review: This work studies an optimality objective for MDPs known as a Blackwell optimal policy. Although this concept has been studied before, in this work the authors show the existence of a Blackwell discount factor such that any policy that is discount optimal for this discount factor is also Blackwell optimal. The authors also provide sufficient conditions for this factor along with an algorithm to find it using this upper bound. The reviewers agreed this work provides a meaningful addition to the field of RL. 

We would like the authors to keep in mind there was a high variability in scores among the different reviewers. Many concerns have been raised including the usefulness of the Blackwell Optimality criterion, the computational efficiency of the proposed algorithm and concerns about the utility of the bounds. It would be ideal if the authors address some of these comments in the final version of the paper.
Decision: Accept (poster)