Feasible $Q$-Learning for Average Reward Reinforcement Learning

Introduction

Reinforcement learning (RL) has achieved remarkable success in simulated environments such as beating world human champions in playing poker, chess and Go (Brown and Sandholm, 2018;Schrittwieser et al., 2020;Silver et al., 2018;Mnih et al., 2015;Schaeffer et al., 1992;Campbell et al., 2002). Such empirical successes-and the excitements generated therefromhave motivated a remarkably fruitful line of research on the sample complexity of various RL algorithms, which characterizes how many samples (from a generative model such as a simulator) are needed to obtain an ϵ-optimal policy.

Regarding sample complexity, an important setting is the discounted infinite-horizon RL, where the goal is to maximize the (infinite) sum of all future γ-discounted rewards for a given factor 0 < γ < 1. Broadly speaking, there are (at least) two main classes of methods to tackle the problem: model-based methods and model-free methods. Model-free algorithms learn to select actions without model estimation. Compared with model-based ones (Azar et al., 2013;Sidford et al., 2018b,a;Wang, 2020;Agarwal et al., 2020), they are often more computationally efficient, have less storage overhead, and are easy to generalize to RL with function approximation (Sutton and Barto, 2018;François-Lavet et al., 2018). In particular, Q-learning (Watkins and Dayan, 1992), as the prototypical model-free algorithm, has been studiedfoot_1 extensively in discounted infinite-horizon RL (Kearns and Singh, 1999;Even-Dar et al., 2003;Beck and Srikant, 2012;Wainwright, 2019a;Chen et al., 2020;Li et al., 2021).

Such remarkable research efforts notwithstanding, average-reward infinite-horizon RL remains far from being resolved: As recognized by the RL community (Sutton and Barto, 2018;Wan et al., 2021;Mahadevan, 1996;Dewanto et al., 2020), average reward RL, which provides a more natural objective for many continuing tasks, is a much more challenging problem and has remained largely under-explored. The sparsity of theoretical understanding also limits the implementation. Indeed, discount factors are often used in practical instantiations of RL algorithms, even when the final objective of interest is clearly the average undiscounted reward in the long term. This is partly due to the fact that algorithms to directly optimize average reward are much more challenging to characterize than the discounted ones. As a result, popular RL algorithms make an ad-hoc choice of a fixed discount factor that are only partially understood (Tang et al., 2021). However, many RL applications do not have a natural discount factor that can be endogenously identified.

Classical results (Blackwell, 1962;Mahadevan, 1996) connect the discounted and average reward formulations via fundamental relations between optimal value functions asymptotically, yet there is only limited finite-sample guarantees related to algorithmic transfer between the two frameworks, given the ubiquitous practice of implementing the former to solve the latter. Recent works leverage similar relations to devise algorithms that optimizes the γ-discounted reward to approximate optimal average reward for a carefully designed, fixed γ (Jin andSidford, 2020, 2021). However, these (model-based) algorithms that have finitesample guarantees all require knowing the mixing time t mix and are hence infeasible. In parallel, finite-sample guarantees for model-free methods (sometimes called R-learning, see Section 1.1) for average reward are even more scarce; the only one we know of is very recent (Zhang et al., 2021), and the algorithm therein also relies on unknown parameters as input. As such, and in light of the merits of model-free RL algorithms mentioned before, we are naturally led to the open question:

Can we design a feasible model-free averagereward RL algorithm with finite-sample guarantees for the sample complexity?

In this paper, we provide new theoretical results that highlight an important algorithmic role for the discounted formulation as a subroutine in solving several learning tasks in the average reward scenario. In contrast to the typical use of a fixed discount factor, we highlight the importance of a carefully selected schedule for progressively finer discount factors to ob-tain a solution to the average reward objective. Our high-level idea is in concordance with Hordijk and Tijms (1975) which provides an asymptotic analysis for such paradigm when planning with knowledge of the MDP; in contrast, we provide finite-sample analysis for a learning problem, which requires judiciously chosen schemes of both discount factors and learning rates to tackle random data.

Related Work

We include more detailed discussion of related work in this part, extending Section 1.2 in the main text.

Model-based average-reward RL. (Kearns and Singh, 2002) is an early work on average-reward RL that proposes a model-based learning algorithm and establishes a sample complexity bound of O( S 5 poly(A)t 5 mix ϵ 6

), where poly(A) is an unspecified polynomial of A. From an algorithmic standpoint, an important issue of the algorithm is that it requires the knowledge of both t mix and the optimal average rewardfoot_2 . More recently, several different model-based average reward RL algorithms have been proposed Wang (2017); Zhang and Xie (2023); Jin andSidford (2020, 2021), with the latter two achieving state-of-the-art sample-complexity bounds of O(

) and O( SAtmix ϵ 3

), respectively. All three algorithms rely on knowing t mix or similar quantities. Jin and Sidford (2021) further provides a lower bound of O( SAtmix ϵ 2

) for average-reward RL when t mix is known. Consequently, while having the pleasing optimal dependence on SA, a minimax optimal algorithm for average-reward RL is not yet known even under known t mix , an impractical assumption to begin with.

Model-free average-reward RL. More recently, driven by the merits of model-free algorithms, Zhang et al. (2021) provides the very first finite-sample analysis of a average reward Q-learning variant, yielding a sample complexity bound of O( SAJ 3

(1-δ) 5 ϵ 2 ), where J and δ are two unknown MDP-dependent constants that may arbitrarily depend on t mix . This pioneering bound itself is valuable in light of the difficulty in characterizing finite-sample guarantees of Q-learning algorithms for average reward RL. However, the issue is that Zhang et al. (2021) assumes J and δ are known and given, rendering the algorithm infeasible.

Feasible average-reward RL with asymptotic guarantees. The only feasible average-reward Qlearning (sometimes also called R-learning) variants that we know of are Wan et al. (2021); Abounadi et al. (2001), which attempt to directly learn the Q-values (called bias function in average-reward RL) associated with the Bellman equation for average reward MDP (discussed in more detail in Section 2). However, for both algorithms, only asymptotic consistency is established. It is largely unclear whether finite-sample sample complexity bounds can be established for Rlearning algorithms, since the underlying update is not a contraction. Remotely related is Hordijk and Tijms (1975), which shares a similar spirit as our methods for gradually adjusting discount factors to approximate average reward; however, it requires the exact knowledge of the MDP and hence solves a planning -rather than learning -problem (see the next subsection for more details), and only provide asymptotic analysis.

Other metrics for average-reward RL. Finally, we mention in passing that the literature has also studied other metrics such as regret Jaksch et al. (2010); Jin et al. (2018); Dong et al. (2019); Fruit et al. (2020); Dong et al. (2021); Wei et al. (2020), which is not the focus here. While there are online-to-batch tricks to turn regrets to sample complexity (e.g., via a randomly sample from history of policies), they can not tell which policy is ϵ-close to optimal; this deviates from our goal of designing a practically feasible algorithm and analyzing its sample complexity. Instead, we focus on algorithms with a deterministic output given data.

Our Contributions and Related Work

First, we design a feasible average-reward Q-learning algorithmic framework that requires no knowledge of any problem parameter. In contrast to the aforementioned Q-learning variants for average-reward RL Wan et al. (2021); Abounadi et al. (2001); Zhang et al. (2021) that all aim to directly learn the bias function (which determines the optimal policy; see Section 2) in the average-reward Bellman equation, our algorithmic framework uses discounted Q-learning but dynamically adjusts the discount factor towards 1 -and hence gradually enlarging the effective horizon -to yield progressively finer approximations of the average-reward setting. This idea is quite simple and intuitive; however, the challenge lies in designing the specific horizon adaptation scheme (involving the simultaneous adjustment of learning rate and discount factor; see Algorithm 1) such that the finite-sample analysis goes through. Note that unlike in the discounted setting with a fixed γ, we now have a "moving target" problem as the discount factor is constantly shifting and weaker contraction, thereby making the analysis much more difficult. On this note, an early work back to 1970s Hordijk and Tijms (1975) shares a similar idea of adjusting discount factors; however, it only provides asymptotic guarantees (and does so without any specific adaptation scheme); further, it requires the exact knowledge of the MDP and hence solves a planning problem.

Second, we offer two concrete instantiations of our framework under (distinct) judiciously chosen adaptation schemes. Using the first scheme, stopping our algorithm at any iteration T yields a policy whose average reward differs from the optimal by at most O(t mix /T 1/8 ). Under the synchronous setting we consider (see Section 2), it translates to a sample complexity bound of O(SAt 8 mix /ϵ 8 ). Furthermore, if the goal is to simply estimate the optimal average reward, then we can do so at a faster rate by our second scheme: stopping at any iteration T yields an estimation accuracy of O(t mix /T 1/foot_3 ), which translates to a sample complexity of O(SAt 5 mix /ϵ 5 ). These results also indicate that our algorithm is any time: we do not need to know T beforehand when running the algorithm 5 . To the best of our knowledge, these are the first finitesample guarantees for a feasible Q-learning algorithm. That said, we believe these bounds can be improved; and we view our results as an open invitation for further progress in feasible average-reward RL.

Additionally, although not the main focus here, we also extend our algorithmic framework to estimate the bias function in the average-reward MDP Bellman equation (Section 5). As mentioned before, existing average-reward Q-learning algorithms Wan et al. Finally, through preliminary simulations, we verify that our algorithm learns the near-optimal policy with satisfactory convergence, and performs well across MDPs with various values of mixing time without the need of any prior knowledge of the mixing time.

We consider an infinite-horizon tabular MDP M = (S, A, P, r), with finite state space S = {1, . . . , S}, finite action space A = {1, . . . , A}, transition probability P : S × A → ∆(S) (i.e., P (s ′ | s, a) is the probability of transiting to s ′ from a state-action pair (s, a) ∈ S × A), and reward function r : S × A → [0, 1] (i.e., r(s, a) is the immediate reward at state s ∈ S if action a ∈ A is taken). We let π : S → ∆(A) denote a policy, i.e., π(a | s) is the probability of taking a at state s. When π is a deterministic policy, π(s) denotes the action chosen at state s. Learning objective. Given a policy π, we define its long-term average reward as

Here E π denotes the expectation over the trajectory {(s k , a k )} k≥0 of the MDP under policy π. Under sufficient generalityfoot_4 , the standard MDP theory (Puterman, 2014) shows that for any policy π, there exists a constant J π ∈ [0, 1] such that V π (s) = J π for all s ∈ S. The long-term average reward of π initialized at any state-action pair also equals J π , that is,

a for all (s, a) ∈ S × A. We use J π ∈ [0, 1] to denote the average reward of policy π.

The optimal policy π * for average reward attains J π * = max π J π , and we denote J * = J π * . Furthermore, there exists a function q * : S ×A → R so that the following Bellman equation holds for all (s, a) ∈ S ×A:

where v * (s ′ ) = max a ′ ∈A q * (s ′ , a ′ ) for all s ′ ∈ S. The optimal policy π * is greedy w.r.t. q * , i.e., π * (s) = argmax a∈A q * (s, a) for all s ∈ S. The solution (q * , v * ) to ( 1) is unique up to a constant; one solution is

where v * and q * are called the value bias function and q-value bias function respectively (Puterman, 2014).

In this work, we will consider three tasks: (1) learning the optimal reward J * up to ϵ-accuracy, (2) learning a policy whose average reward is ϵ-close to J * , and (3) learning the bias functions q * and v * up to constants.

Mixing time and other related notions

Definition 2.1.

The mixing time t mix of an MDP is max π min t : max q∈∆(S)

where d TV (µ, ν) := 1 2 s∈S |µ(s) -ν(s)| is the total variation distance, and (P π ) t (q) is the distribution of s t induced by policy π with initial distribution s 0 ∼ q. We suppose for any policy π there exists a stationary distribution ν π ∈ ∆(S); otherwise t mix = ∞.

The notion of mixing time (3) is widely adopted in the literature of average reward MDPs (Wei et al., 2020;Jin and Sidford, 2021), and our assumption is standard inthe liteature Wang (2017); Jin and Sidford (2020). While we adopt such notion to be consistent with the literature, our analysis framework also works under other regularity conditions. Remark 2.2. Our results remain true if the mixing time (3) is replaced by the reward averaging time similar to De Farias and Van Roy (2006); Dong et al. (2021); the latter is also closely related to the notion of averaging time considered in Kearns and Singh (2002). To be specific, the reward averaging time is de-

average reward value function of π. Our results carry over to this setting with t mix replaced by τ < ∞ in the upper bound. Remark 2.3. Our framework also applies to weakly communicating MDPs (Wei et al., 2020). Define the span of the optimal γ-discounted value function as sp

is the optimal discounted value function with a scaling; the exact definition of V * γ is deferred to (4). It is argued in Wei et al. (2020) that the span is bounded by the diameter of the MDP (Lattimore and Szepesvári, 2020) for weakly-communicating MDPs. Our bound applies to MDPs with bounded spans with t mix replaced by sup γ∈(0,1) sp(γ).

3 Algorithm: Dynamic Horizon Q-Learning

We start with a brief recap on the celebrated Qlearning algorithm for discounted value functions.

Given any discount factor γ ∈ (0, 1) and any policy π, with rewards r k = r(s k , a k ), we denote the rescaled γ-discounted value function and Q-function of π as

for (s, a) ∈ S × A. For preparation, we also denote the unscaled γ-discounted value and Q-functions of π as

and the optimal ones as

The optimal policy for γ-discounted reward is de-

γ (s, a). In synchronous setting, the Q-learning algorithm for γ-discounted rewards maintains an estimate

In each iteration t, it updates all entries of the estimate at once, according to

). Here η t ∈ (0, 1] is the learning rate or the step size, and T t is the empirical Bellman operator depending on the samples collected in the t-th iteration (with proper scaling):

where s ′ ∼ P (• | s, a) is the independent sample collected for (s, a) from the generative model.

Framework of Analysis for Algorithm 1

In this section, we provide a sketch of analysis for Algorithm 1. To begin with, we denote ∆ t = Q t -Q * γt , which is the estimation error of Q t for the rescaled optimal Q-function with γ t in the t-th iteration. Our updating rule (6) in the t-th iteration admits the representation:

γt (note the rescaling of the value and Qfunctions compared to conventional notations),

The decomposition ( 9) is similar to what appears in the standard analysis of discounted Q-learning updates, such as Li et al. (2021); Wainwright (2019b); however, we note a few key technical challenges due to a dynamic discount factor and a moving target Q * γt , which require considerably more efforts and techniques to address.

(1) First, due to the dynamic discount factor γ t → 1, the contraction of ( 9) is much weaker than that with a fixed discount factor, so that the last term η t γ t P t V t-1 -P V * γt is much more difficult to control. As a result, γ t cannot converge to 1 too fast.

(2) Due to the moving target Q * γt , there is a bias (1 -

. It is large if γ t converges to 1 too quickly or if η t is too small. A similar bias occurs in η t γ t P t V t-1 -P V * γt . In light of (1) and ( 2) and the bias in Lemma 3.2 (large if γ t converges to 1 too slowly), we need a careful choice of γ t to balance different sources of bias.

(3) Similar to the discounted setting, the learning rate η t needs to balance the bias from earlier updates and variance from recent updates. Moreover, as η t is coupled with γ t in the third term, we have to admit a less aggressive learning rate due to additionally balancing the bias&variance in random update with η t and the bias from γ t .

To summarize, in sharp distinction from the discounted Q-learning, we need to address the bias due to γ t → 1 in conjunction with the statistical error in random learning update. As a result, our dynamic Qlearning algorithm typically yield slower convergence compared with the discounted counterpart.

Our analysis partially builds on the recent progress in sharp analysis for discounted Q-learning Li et al. (2021). However, we additionally tackle the bias due to γ t ̸ = γ t-1 , which leads to distinct analysis. The last term in the bracket in (9) can be further decomposed as

where

Above two inequalities use the fact that P * γt-1 is greedy w.r.t. Q * γt-1 , while π t-1 is greedy w.r.t. Q t-1 . Plugging them back into (9) leads to

where we define the switching error in the t-th iteration

Applying (11a) and (11b) recursively, we arrive at

where we define η

We now proceed to bound (12). Let β ∈ (0, 1) be a constant whose value will be specified later. Writing

where

The convergence rates for these quantities then depend on the choice of {η t } and {γ t }, which we analyze in a case-by-case fashion for all our theoretical results.

Sketch of Analysis for Theorem 3.1

As an example of our analysis, we now bound the terms δ t , ζ t and ξ t in the decomposition (13), which leads to a recursive bound on ∆ t for Theorem 3.1. To begin with, for the constant c 2 > 0 in Theorem 3.1, we set

The lemmas throughout this subsection will be under the same conditions as Theorem 3.1.

Bounding switching error. First, the dynamic discount factors leads to the switching error δ t , since the estimation targets Q * γt keeps moving. Lemma 4.1. Let T satisfy the conditions of Theorem 3.1. Then ∥δ t ∥ ∞ ≤ 2( log T T ) 2/5 for all t obeying T / log T ≤ t ≤ T .

Bounding ζ t . The second term ζ t is the cumulative estimation error up to t β = ⌊(1 -β)t⌋. It can be bounded via appropriate contraction with appropriate choices of t β . We bound its ℓ ∞ -norm as follows. The proof of Lemma 4.2 is in Appendix A.5. Lemma 4.2. Let T satisfy the conditions of Theorem 3.1. Then ∥ζ t ∥ ∞ ≤ 2

T for all T / log T ≤ t ≤ T .

Bounding ξ t . Finally, ξ t is a random error term, for which we derive a high-probability bound, adapting the sharp analysis strategies introduced in Li et al. ( 2021). The proof of Lemma 4.3 is in Appendix A.6. Lemma 4.3. For any fixed t obeying T / log T ≤ t ≤ T , it holds with probability at least 1 -δ that

A recursive bound. With the above three bounds in place, we put them together and obtain a recursive bound on ∆ t , whose detailed proof is in Appendix A.3. Proposition 4.4. Under the conditions in Theorem 3.1, with probability at least 1 -δ,

The techniques of Proposition 4.4 are related to Li et al. (2021), but controlling multiple sources of bias and variance relies on quite different ideas.

A similar lower bound is in Proposition 4.5, whose proof is essentially the same as that of Proposition 4.4 hence omitted here.

Proposition 4.5. Suppose T satisfies the conditions in Theorem 3.1. Then with probability at least 1 -δ,

holds simultaneously for all t obeying 3T 2 log T ≤ t ≤ T , where c 3 > 0 is a constant that only depends on c 1 , c 2 .

Finally, solving the recursive bounds proves Theorem 3.1; see Appendix A.1 for details.

6: end for

The distinction between this procedure and Algorithm 1 is that we use r(s, a) instead of (1-α t )r(s, a) in the update. As a result, our estimates approximate another set of dynamic targets: the unscaled discounted value functions {q * αt } and {v * αt } (c.f. ( 5)), which further approximate solutions to (1).

Lemma 5.1. There exists a constant B > 0 which only depends on the underlying MDP such that

for all state-action pairs (s, a) ∈ S × A, where J * is the optimal average reward, q * α and v * α are the unscaled optimal α-discounted Q-(value) functions, and q * and v * are the bias functions defined in (2).

The proof of Lemma 5.1 is in Appendix D.2. Thus,

where, similar to the previous case, it remains to control the estimation error to the dynamic targets.

Theorem 5.2. In Algorithm 2, we set

Then with probability at least 1 -δ, after T iterations, Algorithm 2 achieves

simultaneously for all (s, a) ∈ S ×A, where c > 0 is an absolute constant that only depends on c 1 , c 2 , B is the constant given in Lemma 5.1, q * and v * are the bias functions defined in (2). See Appendix C.1 for a sketch of analysis, and Appendix C.2 for a detailed proof.

With the bias function estimator q T , a natural idea for the task of policy learning is to take the greedy policy with respect to q T :

Its suboptimality from the true optimal reward turns out to be of the same scale as the estimation error bound of q T . We thus have its near-optimality property. The proof of Corollary 5.3 is in Appendix C.3.

Corollary 5.3. Under the same conditions of Theorem 5.2, the greedy policy π T with respect to q T obeys

Conclusions

In this paper, we provide a feasible framework for average-reward RL that, distinct from existing works, does not require any problem-dependent parameters as input. Our results highlight the algorithmic role of sequentially adjusted discounted factors, along with a carefully selected adaptation scheme, in achieving several average reward learning objectives. We provide finite-sample guarantees for three popular learning tasks. We envision this work as initial progress towards algorithmic design and theoretical understanding of feasible model-free average-reward RL, and an invitation for subsequent efforts in these aspects.

Zanette, A., Kochenderfer, M. J., and Brunskill, E. (2019). Almost horizon-free structure-aware best policy identification with a generative model. Advances in Neural Information Processing Systems, 32. Zhang, S., Zhang, Z., and Maguluri, S. T. (2021). Finite sample analysis of average-reward td learning and q-learning. Advances in Neural Information Processing Systems, 34. Zhang, Z. and Ji, X. (2019). Regret minimization for reinforcement learning by evaluating the optimal bias function. Advances in Neural Information Processing Systems, 32. Zhang, Z. and Xie, Q. (2023). Sharper model-free reinforcement learning for average-reward markov decision processes. In The Thirty Sixth Annual Conference on Learning Theory, pages 5476-5477. PMLR. Checklist 1. For all models and algorithms presented, check if you include: (a) A clear description of the mathematical setting, assumptions, algorithm, and/or model. [Yes] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Yes] (c) (Optional) Anonymized source code, with specification of all dependencies, including external libraries. [Not Applicable] 2. For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. [Yes] (b) Complete proofs of all theoretical results.

[Yes] (c) Clear explanations of any assumptions. [Yes] 3. For all figures and tables that present empirical results, check if you include:

(a) The code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL). [Not Applicable] (Explanation: we will do so when it is possible to de-anonymize the paper.) (b) All the training details (e.g., data splits, hyperparameters, how they were chosen

). [Yes] (c) A clear definition of the specific measure or statistics and error bars (e.g., with respect to the random seed after running experiments multiple times). [Yes] (d) A description of the computing infrastructure used. (e.g., type of GPUs, internal cluster, or cloud provider). [Not Applicable] 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator If your work uses existing assets. [Not Applicable] (b) The license information of the assets, if applicable. [Not Applicable] (c) New assets either in the supplemental material or as a URL, if applicable. [Not Applicable] (d) Information about consent from data providers/curators. [Not Applicable] (e) Discussion of sensible content if applicable, e.g., personally identifiable information or offensive content. [Not Applicable] 5. If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to participants and screenshots. [Not Applicable] (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. [Not Applicable] (c) The estimated hourly wage paid to participants and the total amount spent on participant compensation. [Not Applicable]

A Technical Proofs Regarding Theorem 3.1

In this section, we provide detailed proofs for results regarding Theorem 3.1. Appendix A.1 provides the detailed proof for Theorem 3.1, and the remaining subsections provide proofs for intermediate results in the analysis sketch of Section 4.

Throughout the section, the learning rates and discount factors are

and we choose the proportion

for the constant c 2 > 0 in Theorem 3.1.

A.1 Proof of Theorem 3.1 Proof of Theorem 3.1. We solve the recursive bounds in Propositions 4.4 and 4.5 to obtain the final highprobability bound. For any positive integer k, we define

A naive upper bound is u k ≤ 1 for all k. Furthermore, by ( 15) and the definition of u k , with probability at least 1 -δ, it holds simultaneously for all k ≥ 1 that

for some absolute constant c 3 > 0. If there exists some k such that

for some sufficiently large constant c 4 > 0, then

as well. By induction, the above bound holds for all j ≥ k, hence

On the other hand, suppose u j > c 4 ((log T ) -1/5 + 9t mix )

for any 1 ≤ j ≤ k. Then we know

for some constant c 6 > 0. Recursively applying this relation for 1 ≤ j < k yields

where we used the fact that u 0 ≤ 1. Hence

Now we can set 2 k ≥ log T /5, so that the above upper bound translates to

Combining the two cases above, we arrive at

with probability at least 1 -δ for T obeying the conditions of Proposition 4.4. Furthermore, since t mix ≥ 1, the above bound translates to

for some constant c > 0 that only depends on c 1 , c 2 , which completes the proof of Theorem 3.1.

A.2 Proof of Lemma 3.2

Proof of Lemma 3.2. For any discounted factor γ ∈ (0, 1), the optimal policy π * γ with respect to γ-discounted reward attains the optimal Q-function, i.e.,

Similarly, the optimal policy π * with repsect to average reward satisfies J * = J π * . Applying Lemma D.1 to π * γ and γ leads to

for any state-action pair (s, a) ∈ S × A. On the other hand, applying Lemma D.1 to π * and γ leads to

for any state-action pair (s, a) ∈ S × A. The last steps of the two equations follow from the bounded reward averaging time for π * γ and π * . Combining the two inequalities, we complete the proof of Lemma 3.2.

A.3 Proof of Proposition 4.4

Proof of Proposition 4.4. Combining Lemma 4.1, 4.2 and 4.3, for sufficiently larget T obeying the conditions of Theorem 3.1 and any fixed t within T / log T ≤ t ≤ T , it holds with probability at least 1 -δ that

where the second inequality follows from the fact that

for T so large that T / log T ≥ 300. Once (1 -β) ≥ 3/4, for any fixed t obeying 3T /(2 log T ) ≤ t ≤ T , we apply (18) with a union bound over {k : 2t 3 ≤ k ≤ t} -as a result, with probability at least 1 -δ, one has

where we define

Before proceeding to recursively bound ∆ t , we define {α

which, following Li et al. (2021), satisfies

for all t. When T is sufficiently large so that 1 -β ≥ 2/3, We decompose (19) as

We recursively apply the above relation in a manner similar to Equation 68 of Li et al. ( 2021), yet with a sequence of dynamic discount factor {γ t }:

where the third line uses η 22), and the last line uses

= 1 in ( 22). We shall further recursively apply the above relation. To begin with, we set

We define the index set

By definition of β, we have

for sufficiently small c 2 ≤ log(3/2), which implies

Recursively invoking (23), we obtain

where the second line uses

In the following, we are to bound β 1 and β 2 in (24) separately. The easier term is β 2 : noting that by definition of the discount factor {γ t }, we have γ j ≤ γ T for all 2t/3 ≤ j ≤ T , indicating

where (i) follows from the bounded magnitude ∥∆ H ∥ ∞ ≤ 1 and the fact that H h=1 P πi h is a probability transition matrix; (ii) follows from

Moving on to β 1 , its entrywise square can be upper bounded as

where (i) follows from Jensen's inequality noting that h k=1 P πi k is a probability transition matrix, (ii) follows from the Cauchy-Schwarz inequality, (iii) follows from the definition of φ t in (20), and (iv) follows from the fact that h k=1 P πi k 1 = 1 since h k=1 P πi k is a probability transition matrix. We employ the following lemma to bound the first term of ( 26), whose proof is in Appendix D.4.

Lemma A.1. Suppose T ≥ 160, then it holds for all T / log T ≤ t ≤ T that

Invoking Lemma A.1, we obtain an upper bound

Recalling (24), by the upper bound (25) on |β 2 | and (28) on |β 1 |, for any fixed t such that 3T /(2 log T ) ≤ t ≤ T ,

holds with probability at least 1 -δ.

We now further take a union bound for (29) over {t : 3T /(2 log T ) ≤ t ≤ T }, which leads to the simultaneous (1 -δ) high-probability bound

. This completes the proof of Proposition 4.4.

A.4 Proof of Lemma 4.1

Proof of Lemma 4.1. Employing Lemma D.4, each term d t can be bounded as

where the second line uses ∥AB∥ ∞ ≤ ∥A∥ 1 ∥B∥ ∞ for matrices A, B, the third line follows from ∥P ∥ 1 = 1 since each row of P is a probability vector. For any t > 1, we let α = t -2/5 ∈ (0, 1). By the triangular inequality, the switching error can be bounded as

Firstly, when t obeys ⌊(1 -α)t⌋ = ⌊t -t 2/5 ⌋ ≥ 150 (which is satisfied by t ≥ 160), for any i such that

≤ exp -αt(log t) 3 (10 + c 1 )t 3/5 , where (i) follows from (99), and (ii) follows from (100) for j ≥ ⌊(1 -α)t⌋ ≥ 150. Together with the fact that ∥d i ∥ ∞ ≤ 1, the above bound implies

On the other hand, (30) implies

for all i ≥ 1 + ⌊(1 -α)t⌋. The second inequality above is implied by

where for i ≥ 2, we use the fact that log(1 -x) ≥ -2x for x ≤ log 2/2 and e x ≥ 1 + x for x ∈ R. Therefore, noting that α ≤ 0.2 for t ≥ 150, we have

Combining ( 31) and ( 32), once T / log T ≥ 160, we have

for all T / log T ≤ t ≤ T , where the third inequality follows from log T ≥ 2 log log T , and the last inequality follows from (log T ) 3 /(80 + 8c 1 ) ≥ 7 5 log T . Therefore, we complete the proof of Lemma 4.1.

A.5 Proof of Lemma 4.2

Proof of Lemma 4.2. The ℓ ∞ -norm of ζ t can be bounded as

Here (i) uses ∥AB∥ ∞ ≤ ∥A∥ 1 ∥B∥ ∞ for matrices A, B, and (ii) follows from the fact that ∥P i -P ∥ 1 ≤ ∥P i ∥ 1 + ∥P ∥ 1 ≤ 2 and ∥P πt-1 ∥ 1 ≤ 1 (since they are all probability matrices), and the bounded magnitudes

By definition of {η t }, as long as β < 1/2 and t ≥ 300,

where the second inequality follows from (99), and the last inequality follows from the monotonicity (100).

Similarly, when ⌊(1 -β)t⌋ ≥ 150 (satisfied as long as β < 1/2 and t ≥ 300), for any 1

where the last inequality follows from (100). Combining ( 33) and (34), once β < 1/2, we have

for all t ≥ 300. Note that when T / log T ≥ 300, for all t such that T / log T ≤ t ≤ T ,

where the second inequality follows from log T ≥ 2 log log T . Meanwhile, for T / log

Therefore, for any T / log T ≤ t ≤ log T ,

if T obeys (satisfied by the conditions of Theorem 3.1)

T 2/5 log T ≥ 16(10 + c 1 ) and c 2 T 1/5 ≥ 24(10 + c 1 )(log T ) 2/5 , which completes the proof of Lemma 4.2.

Feasible Q-Learning for Average Reward Reinforcement Learning

A.6 Proof of Lemma 4.3

Proof of Lemma 4.3. We begin with some basic notations for convenience: write

Then (entries of) {z i } are martingale differences in the sense that

We shall obtain high-probability bound on ∥ζ t ∥ ∞ via Freedman's inequality in Lemma D.6, for which we compute some basic quantities that would be of use.

Firstly, when ⌊(1 -β)t⌋ ≥ 150 and 1 -β ≥ 1/2, max

where the second inequality follows from ∥P i -P ∥ 1 ≤ ∥P i ∥ 1 + ∥P ∥ 1 ≤ 2 and the bounded magnitude ∥V i-1 ∥ ∞ ≤ 1, and the third inequality follows from (103).

We denote the entrywise conditional variance of z i as Var(

It can be (entrywisely) upper bounded as

where the last inequality follows from (103) and the fact that

i ≤ 1 due to (101). In addition, since ∥V i-1 ∥ ∞ ≤ 1, a deterministic upper bound of W t is given by

To apply Freedman's inequality, we further choose the (smallest) positive integer K such that for some constant c 2 ≥ 1,

In view of ( 36) and ( 37) together with a union bound over all |S||A| entries, Freedman's inequality (Lemma D.6) implies that for any fixed t obeying ⌊(1 -β)t⌋ ≥ 150 and β < 1/2,

holds with probability at least 1 -δ, where the second line follows from the fact that log t/t ≤ log 2/2 for t ≥ 4.

Finally, for any fixed t obeying T / log T ≤ t ≤ log T , we have

The bound in (38) thus translates to

as long as t additionally satisfies

To see (39), note that under the conditions of Theorem 3.1, one has T 2/5 ≥ 64(log

Var P (V i-1 ) + T -1/5 1 , which completes the proof of Lemma 4.3.

B.3 Bound on ξ t

Similar to the proof of Lemma 4.3, we write

Then (entries of) {z i } are martingale differences, and we shall obtain high-probability bound on ∥ξ t ∥ ∞ via Freedman's inequality as usual.

Firstly, parallel to (36), when ⌊(1 -β)t⌋ ≥ 50 and 1 -β ≥ 1/2, max

where the third inequality follows from (107).

We denote the entrywise conditional variance of z i as Var(z i | V i-1 , . . . , V 0 ) ∈ R |S||A| , whose j-th element is the variance of [z i ] j conditional on V i-1 , . . . , V 0 . By the definition of z i in (44),

Similar to the situation in Lemma 4.3 (c.f. Appendix A.6), we have the crude entrywise upper bounded

where the last inequality follows from ( 107) and the fact that

i ≤ 1 due to (101). In addition, by the boundedness of ∥V i-1 ∥ ∞ ≤ 1, we also have a deterministic upper bound of W t that

To apply Freedman's inequality, we further choose the (smallest) positive integer K such that for some constant c 2 ≥ 1,

In view of ( 45) and ( 46) together with a union bound over all |S||A| entries, Freedman's inequality (Lemma D.6) implies that for any fixed t obeying ⌊(1 -β)t⌋ ≥ 50 and β < 1/2,

holds with probability at least 1 -δ, where the second line follows from the fact that log t/t ≤ log 2/2 for t ≥ 4.

Finally, for any fixed t obeying T / log T ≤ t ≤ log T , we have

The bound in (47) thus translates to

as long as t additionally satisfies

B.4 Recursive bound

Combining the three bounds in preceding subsections, for sufficiently large T satisfying all the mentioned conditions and any fixed t obeying T / log T ≤ t ≤ T , it holds with probability at least 1 -δ that

where the second inequality follows from the fact that

for T so large that T / log T ≥ 100. Once (1 -β) ≥ 3/4, for any fixed t obeying 3T /(2 log T ) ≤ t ≤ T , we apply ( 48) with a union bound over {k : 2t 3 ≤ k ≤ t} -as a result, with probability at least 1 -δ, one has

where we define

Var P (V i-1 ) + T -3/8 1 (50)

Var P (V i-1 ) + T -3/8 1 .

In the following, we are to follow exactly the same recipe as in the proof of Proposition 4.4 (c.f. Appendix A.3), where we correspondingly define the {α (t) i } according this set of learning rates {η j } here. We also set

) ≥ 2/3 as long as c 2 ≤ log(3/2)/2. Thus, when T is sufficiently large so that 1 -β ≥ 2/3, in parallel with (24), we have

In the following, we are to bound β 1 and β 2 in (51) separately. By definition of the discount factor {γ t }, we have γ j ≤ γ T for all 2t/3 ≤ j ≤ T , indicating

where (i) follows from the bounded magnitude ∥∆ H ∥ ∞ ≤ 1 and the fact that H h=1 P πi h is a probability transition matrix; (ii) follows from

Again, for β 1 , parallel to (26), we have the entrywise upper bound

We employ the following lemma to bound the first term of ( 53); it is parallel to Lemma A.1, and the proof follows exactly the same arguments hence we omit here.

Lemma B.1. Suppose T 100, then it holds for all T / log T ≤ t ≤ T that

Invoking Lemma B.1, we obtain an upper bound

Recalling ( 51), by the upper bound (52) on |β 2 | and ( 55) on |β 1 |, for any fixed t such that 3T /(2 log T ) ≤ t ≤ T ,

holds with probability at least 1 -δ.

We now further take a union bound for (56) over {t : 3T /(2 log T ) ≤ t ≤ T }, which leads to the simultaneous (1 -δ) high-probability bound

C.1 Sketch of analysis for Algorithm 2

In this section, we provide a sketch of analysis for the estimation error of Algorithm 2, which forms the basis for proving Theorem 5.2. The general approach is similar to Section 4.1 with slightly different bounds. Let

for t ≥ 0, which is the estimation error of Algorithm 2 in the t-th iteration.

Our updating rule (17) in the t-th iteration satisfies

Employing the Bellman equation q * αt = r + α t P v * αt , we obtain the decomposition

Similar as the arguments in the analysis of Algorithm 1 (see Section 4), we have

where the term

Here with some abuse of notations, we define π t as the greedy policy with respect to q t . Plugging (59a) and (59b) back into (58) leads to the recursive relation

where we define the switching error in the t-th iteration as

Applying (60a) and (60b) recursively, we arrive at

where we define θ

(1 -θ j ), and θ

Now we set (with some abuse of notation)

for some constant c 2 > 0. The upper bound of (61) can be decomposed as

The three terms, similar to before, are bounded as follows.

Lemma C.1. For all sufficiently large t such that t ≥ max{e 2+c1 , 100}, it holds that Lemma C.2. Suppose T is sufficiently large such that c 2 log T ≥ 5(2+c 1 )(log T ) 1/3 +log log T , c 1 T 3 ≥ 3(log T ) 5 and (T / log T ) 1/3 ≥ 4(2 + c 1 ). Then

for any t such that T / log T ≤ t ≤ T .

Proof of Lemma C.2. See Appendix C.6 for a detailed proof.

We utilize the Freedman's inequality to control the term ξ t .

Lemma C.3. When β < 1/2 and T / log T ≥ max{e c1 , 100}, for any fixed t such that T / log T ≤ t ≤ T ,

holds with probability at least 1 -δ, where c 3 = 16/c 1 + 144/c 2 1 is an absolute constant.

Proof of Lemma C.3. See Appendix C.7 for a detailed proof.

Based on the above three lemmas, we have the following recursive relation, which form the base of proving Theorem 5.2.

Proposition C.4. Suppose T is sufficiently large such that

for some constant c 2 > 0 and c 3 = 16/c 1 + 144/c 2 1 . Then with probability at least 1 -δ,

holds simultaneously for all 3T /(2 log T ) ≤ t ≤ T , where we define the constant c 4 = 2(1 + 3/c 1 ).

Proof of Proposition C.4. See Appendix C.4 for a detailed proof.

C.2 Proof of Theorem 5.2

Proof of Theorem 5.2. We solve the recursive bound of Propositions C.4 that

with probability at least 1 -δ for all 3T /(2 log T ) ≤ t ≤ T . For any positive integer k, we define

By (62) and the definition of w k , with probability at least 1 -δ, it holds simultaneously for all k ≥ 1 that

If there exists some k such that u k ≤ 1 and 2 k+1 ≤ 2 log T /3, then

for some sufficiently large constant c 5 > 0. Otherwise, suppose u j > 1 for any 1 ≤ j ≤ k where k ≤ ⌊log 2 (2 log T /3)⌋ -1, then

Recursively applying this relation for 1 ≤ j < k yields

where we used the fact that

for the constant c 6 = 4c 3 (1 + c 4 ). Combining the two cases above, for any fixed T obeying the given conditions,

holds with probability at least 1 -δ for some constant c 5 > 0. Finally, by Lemma 5.1, we have

Put it another way, given any ε > 0, as long as T satisfies

On the same event of probability at least 1 -δ, we also have

Still by Lemma 5.1, we also obtain the form of v * and q * , which by standard MDP theory (Puterman, 2014) satisfies the Bellman equation ( 1). Therefore, we complete the proof of Theorem 5.2.

C.3 Proof of Corollary 5.3

Proof of Corollary 5.3. Recall that π T (s) = argmax a∈A q T (s, a) for all s ∈ S is the greedy policy, and π * is the optimal policy for average reward. Then under the conditions of Theorem 5.2, we have

where ε = B+c(log T ) 4 (log

, since the function q * defined in Theorem 5.2 equals q π * . Assume without loss of generality that π * and π T are both deterministic policies. Invoking Lemma D.8 with π ′ = π T and π = π * , we know that

Here by the optimality of π * and (63), we have

where the second and fourth lines uses the uniform bound and the third line uses the property of greedy policy π T . This leads to

as desired.

Var P (v i-1 ) + 2(log T ) 6 1 with probability at least 1 -δ for any fixed t within T / log T ≤ t ≤ T , as long as T satisfies

Further simplifying this inequality leads to

as long as T additionally satisfy (log T ) 50/9 ≥ 9 2c3 . Once (1 -β) ≥ 3/4, for any fixed t obeying 3T /(2 log T ) ≤ t ≤ T , we apply (64) with a union bound over {k : 2t 3 ≤ k ≤ t} -as a result, with probability at least 1 -δ,

where we define

Following exactly the same arguments as in the proof of Proposition 4.4, we define

and arrive at the decomposition

To further apply such recursion, we define G = T 1/9 log T, and

We define the index set

Note that once T 2/9 log T ≥ 6 (implied by a stronger condition T 2/9 ≥ (log T ) 5 imposed before), we have

Feasible Q-Learning for Average Reward Reinforcement Learning

Recursively invoking (68), we obtain

We now treat the two terms β 1 and β 2 separately. The easier part is

where the second inequality uses the fact that G h=1 P πi h is a probability matrix, and the third inequality uses ∥δ j ∥ ∞ ≤ ∥q j ∥ ∞ + ∥q * αj ∥ ∞ ≤ 3j 1/3 (log j) 2 /c 1 + j 1/9 by Lemma E.2. On the other hand, following exactly the same argument as 26, we have

Var P (v i ) .

(70)

Applying Lemma D.7, we know that max ⌊t/2⌋≤i<t

which, by the boundedness that

Plug back into (70), we have

where we define the constant c 4 = 2(1 + 3/c 1 ) > 0. Therefore, combining with (69), we have

that holds with probability at least 1 -δ for any fixed t obeying 3T /(2 log T ) ≤ t ≤ T , as long as T satisfies T 10/9 (log

T |S||A| δ ) 2 ≥ (1+3/c1) 2 2c3 (log T ) 4 to ensure (72). Taking a union bound over such t and noting that log T |S||A| δ/T ≤ 2 log T |S||A| δ , we know that

holds simultaneously for all 3T /(2 log T ) ≤ t ≤ T with probability at least 1 -δ/2. On the other hand, following exactly the same arguments, starting from the lower bound in (61) leads to

simultaneously for all 3T /(2 log T ) ≤ t T with probability at least 1 -δ/2. Finally, we summarize all the conditions as

which can be simplified to

We thus complete the proof of Proposition C.4 by taking a union bound.

D.1 Relations of value functions

We quote the following lemma adapted from Jin and Sidford (2021, Lemma 2). It relates the average reward J π and the rescaled discounted ones Q π γ , V π γ of any policy π. The proof the lemma is similar to that of Jin and Sidford (2021) and is omitted here.

Lemma D.1 (Lemma 2 of Jin and Sidford (2021)). For any policy π : S → ∆(A) and any discount factor γ ∈ (0, 1], it holds that

The following lemma is adapted from Dong et al. (2021) andDe Farias andVan Roy (2006), showing that our framework is applicable when the finite mixing time condition is replaced by the reward averaging time τ (see Remark 2.2). The proof the lemma is similar to that of De Farias and Van Roy ( 2006) and is omitted here.

The following lemma bounds the difference between rescaled optimal value and Q-functions with two discount factors.

Lemma D.3. For any γ 1 , γ 2 such that 0 < γ 1 < γ 2 < 1, it holds that

where 0 (resp. 1) is a vector or matrix with all entries equal to 0 (resp. 1).

Proof of Lemma D.3. We first show (75a). The upper bound follows directly from Lemma 17 of Dong et al.

(2021) with a rescaling. For any policy π, we note that

which follows from γ 2 > γ 1 and the non-negativeness of the reward function r. Applying the above relation to π * γ1 , we obtain

which completes the proof of lower bound in (75a). Further noting V * γ (s) = max a ′ ∈A Q * γ (s, a ′ ) for any s ∈ S, the fact that maximum is a contraction map leads to (75b) and completes the proof of Lemma D.3. Lemma D.4. For any discount factors γ 1 , γ 2 such that 0 < γ 1 < γ 2 < 1, it holds that

Proof of Lemma D.4. The boundedness of reward function 0 ≤ r ≤ 1 implies 0 ≤ Q * γi ≤ 1 for i = 1, 2. For any state-action pair (s, a) ∈ S × A, applying the lower bound in Lemma D.3 yields

where the second inequality follows from Q * γ1 (s, a) ≤ 1. On the other hand, the upper bound in Lemma D.3 together with Q * γ1 (s, a) ≥ 0 implies

The second inequality in (76) follows from the same arguments. Lemma D.5. For any i ≥ 1, it holds that

Proof of Lemma D.5. We start by bounding V i -V * γi for all i ≥ 1. Recalling that

where (i) follows from the optimality of π * γi with respect to Q * γi , and (ii) holds since P πi is a probability transition matrix. Similarly,

for all i ≥ 1. By the definition of entrywise variance, we have

Furthermore, we have

where the last inequality follows from ∥P ∥ 1 = 1 and

by the bounded magnitude, and (78). Meanwhile, similar arguments yield

Plugging the two bounds back in (79) completes the proof of (77).

D.2 Proof of Lemma 5.1

Proof of Lemma 5.1. By Feinberg and Shwartz (2012, Theorem 8.1), there exists an optimal policy π * (namely, a Blackwell optimal policy) for the average reward and some α * ∈ (0, 1), such that for all α ∈ (0, α * ), π * is also the optimal policy for α-discounted reward. Since π * is the optimal policy for average reward, its long-term average reward equals J * . We define

namely, the bias function of π * . We also define P * ∈ R |S|×|S| as the transition matrix induced by π * , and P * * = lim T →∞ 1 T T t=1 (P * ) t-1 as the long-term average transition matrix. Furthermore, let

By Puterman (2014, Theorem 8.2.3), letting ρ = (1 -α)/α, for α that is sufficiently close to 1, or equivalently for ρ that is sufficiently close to 0, we have the Laurent series expansion

where J * is the long-term average reward of π * , y n = (-1) n H n+1 P f , where f ∈ R |S| is the vectorization of f (s) = r(s, π * (s)) that also satisfies v * = H P f . Thus, recalling the Blackwell optimality of π * and taking α sufficiently close to 1, we have

Therefore, there exists a constant B 1 > 0 which only depends on the underlying MDP that sup α∈(0,1)

We now define the function

for all state-action pairs (s, a) ∈ S × A, so that (v , q * ) satisfies the Bellman equation ( 1) by standard MDP theory (Puterman, 2014). The equivalent vectorized representation is

Then the Bellman equation for optimal discounted value functions implies

where the second line follows from the optimality of π * α with respect to v * α , the third line follows from (80), and the fifth line follows from the Bellman equation ( 1) for (q * , v * ). Similarly, we have

Combining the above two inequalities, we know that there exists some constant B 2 > 0 such that sup α∈(0,1)

Taking B = max{B 1 , B 2 } completes the proof of Lemma 5.1.

D.3 Freedman's inequality

The following lemma is adapted by Li et al. ( 2021) from Freedman's inequality Freedman (1975).

Lemma D.6 (Theorem 5 of Li et al. (2021)). Suppose

where we write E k-1 for the expectation conditional on {X j } j<k . Then for any given σ 2 ≥ 0, one has

In addition, suppose W n ≤ σ 2 holds deterministically. For any positive integer K, with probability at least 1 -δ one has

) D.4 Proof of Lemma A.1 Proof of Lemma A.1. Employing (77) of Lemma D.5, we have the entrywise bound H-1 h=0 γ h T h k=1 P πi k max ⌊t/2⌋≤i<t

Var

where the third line follows from max i (a i + b i ) ≤ max i a i + max i b i , and the last line follows from the fact that h k=1 P πi k 1 = 1 since the product is still a probability transition matrix. Following the same arguments as the way we bound (79), it holds for all i ≥ 1 that

On the other hand,

where the last equality follows from the Bellman equation Q * γ = (1 -γ)r + γP V * γ for all γ ∈ (0, 1). Using similar arguments as Li et al. (2021), the second term in (84) can be bounded as

where (i) follows from the fact that ∥P ∥ 1 = 1, (ii) is due to the boundedness of ∥Q * γt ∥ ≤ 1, (iii) follows from ∥Π πi h+1 ∥ 1 = 1 and V i h+1 = Π πi h+1 Q i h+1 , (iv) follows from

, and (v) follows from the property of entrywise maximum. We thus obtain the entrywise upper bound (uniform over all ⌊t/2⌋ ≤ i < t) max ⌊t/2⌋≤i<t

Var P (V * γi ) ≤ Var P (V * γt ) + 4 max ⌊t/2⌋≤i<t

where the first inequality follows from (83) and the second inequality follows from ( 84) and ( 93), and the last inequality follows from the monotonicity of γ t . Applying (94) to (82) yields the telescoping sum

H-1 h=0 γ h T h k=1 P πi k max ⌊t/2⌋≤i<t Var P (V i ) ≤ H-1 h=0 γ h T h k=1 P πi k max ⌊t/2⌋≤i<t Var P (V * γi ) + 4 1 -γ T max ⌊t/2⌋≤i<t

where the first inequality follows from (82), and the second inequality uses h k=1 P πi k 1 = 1 as the product is a probability transition matrix. As the rows of the probability transition matrix H k=1 P πi h+1 all sum up to one, we have

by the boundedness of ∥Q * γ ∥ ∞ ≤ 1 for all γ ∈ (0, 1), as well as the fact that γ t ≥ 1/2 for t ≥ 160. On the other hand, for any ⌊t/2⌋ ≤ i < t, invoking Lemma D.1, we obtain

≤ 3(1 -γ t )t mix + 3(1 -γ i )t mix ≤ 3 1 + 2 1/5 t -1/5 t mix ≤ 9T -1/5 (log T ) 1/5 t mix for T / log T ≤ t ≤ log T . In addition, for T ≥ 160, we also have

which, together with the above pieces, leads to ( 27) and completes the proof of Lemma A.1.

Lemma D.7. For any i ≥ 1, it holds that

Proof of Lemma D.7. We first bound v i -v * αi for all i ≥ 1. Recalling that δ i = q i -q * αi , we have

where (i) follows from the optimality of π * αi with respect to q * αi , and (ii) holds since P πi is a probability transition matrix. Similarly, v i -v * αi ≥ P π * α i q i -P π * α i q * αi ≥ -∥P π * α i ∥ 1 ∥q i -q * αi ∥ ∞ ≥ -∥δ i ∥ ∞ , which leads to

for all i ≥ 1. By the definition of entrywise variance, we have

Furthermore, we have

, where the last inequality follows from ∥P ∥ 1 = 1, the triangular inequality, and (96). Meanwhile, similar arguments yield

Plugging the two bounds back in (97) yields Var P (v i ) -Var P (v * αi ) ∞ ≤ 2 ∥v i ∥ ∞ + ∥v * αi ∥ ∞ ∥δ i ∥ ∞ ≤ 2 i 1/9 + 3(log i) 2 i 1/3 /c 1 ∥δ i ∥ ∞ ≤ 2(1 + 3/c 1 )(log i) 2 i 1/3 ∥δ i ∥ ∞ .

E.2 Learning rates for estimating optimal value in Theorem 3.1

In this part, we collect some useful facts about the learning rates speficied for Theorem 3.1 that would be used repeatedly. Recall that we define the learning rates as η t = (1 + c1t 3/5 (log t) 3 ) -1 , ∀ t ≥ 2 for some constant c 1 > 0.

Bound on η j . Firstly, we have the naive upper bound

(log j) 3 ≤ (log j) 3 c 1 j 3/5 , for all j ≥ 2.

(98)

One can also check that j 3/5 /(log j) 3 ≥ 0.1 for all j ≥ 1 with the convention that 1/0 = ∞, which leads to the lower bounds

(log j) 3

≥ 1

(log j) 3 + c1j 3/5 (log j) 3 ≥ (log j) 3 (10 + c 1 )j 3/5 , for all j ≥ 2.

(99)

Furthermore, it can be easily checked that (log j) 3 j -3/5 is decreasing in j for j ≥ 150. Hence η j ≥ η t and (log j) 3 j 3/5 ≥ (log t) 3 t 3/5 , for all t > 150 and 150 ≤ j ≤ t.

(100)

Compound learning rates. Some associated quantities in the analysis include η

(1 -η j ), and η

The sum of η

(t) i over i obeys t i=0 η (t) i = t j=1

(1 -η j ) + η 1 t j=2

(1 -η j ) + • • • + η t-1 (1 -η t ) + η t = 1. (101)

Moreover, we consider a generic β ∈ (0, 1) and bound the compound learning rates for i ≤ ⌊(1 -β)t⌋ and i > ⌊(1 -β)t⌋ separately.

• When β < 1/2, for any t ≥ 300 (so that ⌊(1 -β)t⌋ ≥ 150) and any i ≤ ⌊(1 -β)t⌋,

where the third inequality follows from (100), and the fourth inequality follows from (98).

• When β < 1/2, for any t ≥ 300 and any i > ⌊(1 -β)t⌋ ≥ t/2 ≥ 150, η

i ≤ η i ≤ (log i) 3 c 1 i 3/5 ≤ 2(log t) 3 c 1 t 3/5 (103) following ( 98) and (100) and the fact that log i ≤ log t and i -3/5 ≤ 2t -3/5 for any i ≥ t/2.

E.3 Learning rates for optimal policy in Theorem 3.3

We now present some useful facts about the learning rates that are particular to Theorem 3.3. Recall that in Theorem 3.3, we set γ t = 1 -t -1/8 and η t = 1 1 + c1t 5/8 (log t) 2

, t ≥ 2 for some constant c 1 > 0 in Algorithm 1.

Feasible Q-Learning for Average Reward Reinforcement Learning

Bound on η j . Firstly, we have the naive upper bound

(log j) 2 ≤ (log j) 2 c 1 j 5/8 , for all j ≥ 2. (104)

One can check that j 5/8 /(log j) 2 ≥ 0.5 for all j ≥ 1 with the convention that 1/0 = ∞, which leads to the lower bounds

(log j) 2 + c1j 5/8 (log j) 2 ≥ (log j) 2 (2 + c 1 )j 5/8 , for all j ≥ 2. (105)

Furthermore, it can be easily checked that (log j) 2 j -5/8 is decreasing in j for j ≥ 50. Hence η j ≥ η t and (log j)

2 j 5/8 ≥ (log t) 2 t 5/8 , for all t > 50 and 50 ≤ j ≤ t. (106) Compound learning rates. Some associated quantities in the analysis include η (t) t = η t , η (t) 0 = t j=1 (1 -η j ), and η (t) i = η i • t j=i+1 (1 -η j ), ∀1 ≤ i < t. The sum of η (t) i over i obeys t i=0 η (t) i = t j=1

(1 -η j ) + η 1 t j=2

(1 -η j ) + • • • + η t-1 (1 -η t ) + η t = 1.

Moreover, we consider a generic β ∈ (0, 1) and bound the compound learning rates for i ≤ ⌊(1 -β)t⌋ and i > ⌊(1 -β)t⌋ separately.

• When β < 1/2, for any t ≥ 100 (so that ⌊(1 -β)t⌋ ≥ 50) and any i ≤ ⌊(1 -β)t⌋, η

i ≤ t j=i+1

(1 -η j ) ≤ exp - where the third inequality follows from (100), and the fourth inequality follows from (98).

• When β < 1/2, for any t ≥ 100 and any i > ⌊(1 -β)t⌋ ≥ t/2 ≥ 50, η

i ≤ η i ≤ (log i) 3 c 1 i 5/8 ≤ 2(log t) 2 c 1 t 5/8 (107) following ( 104) and ( 106) and the fact that log i ≤ log t and i -5/8 ≤ 2t -5/8 for any i ≥ t/2.

E.4 Learning rates for bias function in Theorem 5.2

We now proceed to some basic facts on the learning rates of Algorithm 2. Recall that we define the learning rates as

, ∀ t ≥ 2.