Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs

Abstract:
We study the reinforcement learning problem for discounted Markov Decision Processes (MDPs) under the tabular setting. We propose a model-based algorithm named UCBVI-γ, which is based on the optimism in the face of uncertainty principle and the Bernstein-type bonus. We show that UCBVI-γ achieves an Õ (√ SAT/(1− γ) ) regret, where S is the number of states, A is the number of actions, γ is the discount factor and T is the number of steps. In addition, we construct a class of hard MDPs and show that for any algorithm, the expected regret is at least Ω̃ (√ SAT/(1− γ) ) . Our upper bound matches the minimax lower bound up to logarithmic factors, which suggests that UCBVI-γ is nearly minimax optimal for discounted MDPs.

text: ) regret, where S is the number of states, A is the number
of actions, γ is the discount factor and T is the number of steps. In addition, we construct a class of hard MDPs and show that for any algorithm, the expected regret is at least Ω̃ (√ SAT/(1− γ)1.5 ) . Our upper bound matches the minimax lower bound up to logarithmic factors, which suggests that UCBVI-γ is nearly minimax optimal for discounted MDPs.

heading: 1 Introduction
text: The goal of reinforcement learning (RL) is designing algorithms to learn the optimal policy through interactions with the unknown dynamic environment. Markov decision process (MDPs) plays a central role in reinforcement learning due to their ability to describe the time-independent state transition property. More specifically, the discounted MDP is one of the standard MDPs in reinforcement learning to describe sequential tasks without interruption or restart. For discounted MDPs, with a generative model [12], several algorithms with near-optimal sample complexity have been proposed. More specifically, Azar et al. [3] proposed an Empirical QVI algorithm which achieves the optimal sample complexity to find the optimal value function. Sidford et al. [22] proposed a sublinear randomized value iteration algorithm that achieves a near-optimal sample complexity to find the optimal policy, and Sidford et al. [23] further improved it to reach the optimal sample complexity. Since generative model is a powerful oracle that allows the algorithm to query the reward function and the next state for any state-action pair (s, a), it is natural to ask whether there exist online RL algorithms (without generative model) that achieve optimality.
To measure an online RL algorithm, a widely used notion is regret, which is defined as the summation of sub-optimality gaps over time steps. The regret is firstly introduced for episodic and infinitehorizon average-reward MDPs and later extended to discounted MDPs by [15, 30, 35, 35]. Liu and Su [15] proposed a double Q-learning algorithm with the UCB exploration (Double Q-learning),
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
which enjoys Õ( √ SAT/(1 − γ)2.5) regret, where S is the number of states, A is the number of actions, γ is the discount factor and T is the number of steps. While Double Q-learning enjoys a standard √ T -regret, it still does not match the lower bound proved in [15] in terms of the dependence on S,A and 1/(1 − γ). Recently, Zhou et al. [34] proposed a UCLK+ algorithm for discounted MDPs under the linear mixture MDP assumption and achieved Õ ( d √ T/(1− γ)1.5 ) regret, where d is the dimension of the feature mapping. However, directly applying their algorithm to our setting would yield an Õ ( S2A √ T/(1− γ)1.5 ) regret1, which is even worse that of double Q-learning [15] in terms of the dependence on S,A.
In this paper, we aim to close this gap by designing a practical algorithm with a nearly optimal regret. In particular, we propose a model-based algorithm named UCBVI-γ for discounted MDPs without using the generative model. At the core of our algorithm is to use a “refined” Bernstein-type bonus and the law of total variance [3, 4], which together can provide tighter upper confidence bound (UCB). Our contributions are summarized as follows:
• We propose a model-based algorithm UCBVI-γ to learn the optimal value function under the discounted MDP setting. We show that the regret of UCBVI-γ in first T steps is upper bounded by Õ( √ SAT/(1− γ)1.5). Our regret bound strictly improves the best existing regret
Õ( √ SAT/(1− γ)2.5)2 in [15] by a factor of (1− γ)−1.
• We also prove a lower bound of the regret by constructing a class of hard-to-learn discounted MDPs, which can be regarded as a chain of the hard MDPs considered in [15]. We show that for any algorithm, its regret in the first T steps can not be lower than Ω̃( √ SAT/(1− γ)1.5) on the
constructed MDP. This lower bound also strictly improves the lower bound Ω( √ SAT/(1− γ) +√
AT/(1− γ)1.5) proved by [15]. • The nearly matching upper and the lower bounds together suggest that the proposed UCBVI-γ
algorithm is minimax-optimal up to logarithmic factors.
We compare the regret of UCBVI-γ with previous online algorithms for learning discounted MDPs in Table 1.
Notation For any positive integer n, we denote by [n] the set {1, . . . , n}. For any two numbers a and b, we denote by a ∨ b as the shorthand for max(a, b). For two sequences {an} and {bn}, we write an = O(bn) if there exists an absolute constant C such that an ≤ Cbn, and we write an = Ω(bn) if there exists an absolute constant C such that an ≥ Cbn. We use Õ(·) and Ω̃(·) to further hide the logarithmic factors.

heading: 2 Related Work
text: Model-free Algorithms for Discounted MDPs. A large amount of reinforcement learning algorithms like Q-learning can be regarded as model-free algorithms. These algorithms directly learn the action-value function by updating the values of each state-action pair. Kearns and Singh [13] firstly proposed a phased Q-Learning which learns an -optimal policy with Õ(SA/((1− γ)7 2)) sample complexity for ≤ 1/(1 − γ). Later on, Strehl et al. [25] proposed a delay-Q-learning algorithm, which achieves Õ(SA/((1− γ)8 4)) sample complexity of exploration. Wang [29] proposed a randomized primal-dual method algorithm, which improves the sample complexity to Õ(SA/((1− γ)4 2)) for ≤ 1/(1− γ) under the ergodicity assumption. Later, Sidford et al. [23] proposed a sublinear randomized value iteration algorithm and achieved Õ(SA/((1− γ)4 2)) sample complexity for ≤ 1. Sidford et al. [22] further improved the empirical QVI algorithm and proposed a variance-reduced QVI algorithm, which improves the sample complexity to Õ(SA/((1− γ)3 2)) for ≤ 1. Wainwright [28] proposed a variance-reduced Q-learning algorithm, which is an extension of the Q-learning algorithm and achieves Õ(SA/((1− γ)3 2)) sample complexity. In addition, Dong
1Linear mixture MDP assumes that there exists a feature mapping φ(s′|s, a) ∈ Rd and a vector θ ∈ Rd such that P(s′|s, a) = 〈φ(s′|s, a),θ〉. It can be verified that any MDP is automatically a linear mixture MDP with a SA-dimensional feature mapping [2, 35].
2The regret definition in [15] differs from our definition by a factor of (1− γ)−1. Here we translate their regret from their definition to our definition for a fair comparison. A detailed comparison can be found in Appendix.
et al. [9] proposed an infinite Q-learning with UCB and improved the sample complexity of exploration to Õ(SA/((1− γ)7 2)). Zhang et al. [33] proposed a UCB-multistage algorithm which attains the Õ(SA/((1− γ)5.5 2)) sample complexity of exploration, and proposed a UCB-multistage-adv algorithm which attains a better sample complexity Õ(SA/((1− γ)3 2)) in the high accuracy regime. Recently, Liu and Su [15] focused on regret minimization for the infinite-horizon discounted MDP and showed the connection between regret and sample complexity of exploration. Liu and Su [15] proposed a Double Q-Learning algorithm, which achieves Õ( √ SAT/(1− γ)2.5) regret within T steps. Furthermore, Liu and Su [15] constructed a series of hard MDPs and showed that the expected regret for any algorithm is lower bounder by Ω̃ (√ SAT/(1 − γ) + √ AT/(1− γ)1.5 ) . There still exists a 1/(1− γ)-gap between the upper and lower regret bounds. In contrast to the aforementioned model-free algorithms, our proposed algorithm is model-based.
Model-based Algorithms for Discounted MDP. Our UCBVI-γ falls into the category of modelbased reinforcement learning algorithms. Model-based algorithms maintain a model of the environment and update it based on the observed data. They will form the policy based on the learnt model. More specifically, to learn the -optimal value function, Azar et al. [3] proposed an empirical QVI algorithm which achieves Õ(SA/((1− γ)3 2)) sample complexity. Azar et al. [3] proposed an empirical QVI algorithm which improves the sample complexity to Õ(SA/((1− γ)3 2)) for ≤ 1/ √ (1− γ)S. Szita and Szepesvári [27] proposed an MoRmax algorithm, which achieves
Õ(SA/((1− γ)6 2)) sample complexity. Later, Lattimore and Hutter [14] proposed a UCRL algorithm, which achieves Õ(S2A/((1− γ)3 2)) sample complexity in general and Õ(SA/((1− γ)3 2)) sample complexity with a strong assumption on the state transition. Recently, Agarwal et al. [1] proposed a refined analysis for the empirical QVI algorithm which achieves Õ(SA/((1− γ)3 2)) sample complexity when ≤ 1/ √ 1− γ.
Upper and Lower Bounds for Episodic MDPs. There is a line of work which aims at proving sample complexity or regret for episodic MDPs (MDPs which consist of restarting episodes) [7, 18,
4, 19, 11, 8, 24, 21, 31, 32, 17, 20]. Compared with the episodic MDP, discounted MDPs involve only one infinite-horizon sample trajectory, suggesting that any two states or actions on the trajectory are dependent. Such a dependence makes the learning of discounted MDPs more challenging.

heading: 3 Preliminaries
text: We consider infinite-horizon discounted Markov Decision Processes (MDP) which are defined by a tuple (S,A, γ, r,P). Here S is the state space with |S| = S, A is the action space with |A| = A, γ ∈ (0, 1) is the discount factor, r : S ×A → [0, 1] is the reward function, P(s′|s, a) is the transition probability function, which denotes the probability that state s transfers to state s′ with action a. For simplicity, we assume the reward function is deterministic and known. A non-stationary policies π is a collection of function {πt}∞t=1, where each function πt : {S × A}t−1 × S → A maps history {s1, a1, ..., st−1, at−1, st = s} to an action. For any non-stationary policy π, we denote πt(s) = πt(s; s1, a1, ..., st−1, at−1) for simplicity. We define the action-value function and value function at step t as follows:
Qπt (s, a) = E [ ∞∑ i=0 γir(st+i, at+i) ∣∣∣∣s1, ..., st = s, at = a], V πt (s) = E
[ ∞∑ i=0 γir(st+i, at+i) ∣∣∣∣s1, ..., st = s], where at+i = πt+i(st+i), and st+i+1 ∼ P ( · |st+i, πt+i(st+i) ) . In addition, we denote the optimal action-value function and the optimal value function as Q∗(s, a) = supπ Q π 1 (s, a) and V
∗(s) = supπ V π 1 (s) respectively. Note that the optimal action-value function and the optimal value function are independent of the step t. For simplicity, for any function V : S → R, we denote [PV ](s, a) = Es′∼P(·|s,a)V (s′). According to the definition of the value function, we have the following nonstationary Bellman equation and Bellman optimality equation for non-stationary policy π and optimal policy π∗:
Qπt (s, a) = r(s, a) + γ[PV πt+1](s, a), Q∗(s, a) = r(s, a) + γ[PV ∗](s, a). (3.1)

heading: 4 Main Results

heading: 4.1 Algorithm
text: In this subsection, we propose the Upper Confidence Bound Value Iteration-γ (UCBVI-γ) algorithm, which is illustrated in Algorithm 1. The algorithm framework of UCBVI-γ follows the UCBVI algorithm proposed in Azar et al. [4], which can be regarded as the counterpart of UCBVI-γ in the episodic MDP setting.
UCBVI-γ is a model-based algorithm that maintains an empirical measure Pt at each step t. At the beginning of the t-th iteration, UCBVI-γ takes action at based on the greedy policy induced by Qt(st, a) and transits to the next state st+1. After receiving the next state st+1, UCBVI-γ computes the empirical transition probability function Pt(s′|s, a) in (4.1). Based on empirical transition probability function Pt(s′|s, a), UCBVI-γ updates Qt+1(s, a) by performing one-step value iteration onQt(s, a) with an additional upper confidence bound (UCB) term UCBt(s, a) defined in (4.3). Here the UCB bonus term is used to measure the uncertainty of the expectation of the value function Vt(s). Unlike previous work, which adapts a Hoeffding-type bonus [15], our UCBVI-γ uses a Bernsteintype bonus which brings a tighter upper bound by accessing the variance of Vt(s), denoted by Vars′∼P(·|,s,a)Vt(s′). However, since the probability transition P(·|s, a) is unknown, it is impossible to calculate the exact variance of Vt. Instead, UCBVI-γ estimates the variance by considering the variance of Vt over the empirical probability transition function Pt(·|s, a) defined in (4.1). Therefore, the final UCB bonus term in (4.3) can be regarded as a standard Bernstein-type bonus on the empirical measure Pt(·|s, a) with an additional error term. Compared with UCBVI algorithm in Azar et al. [4], the action-value function Qt(s, a) in UCBVI-γ is updated in a forward way from step 1 to step T with the initial value Q1(s, a) = 1/(1− γ) for all s ∈ S, a ∈ A, while UCBVI updates its action-value function in a backward way from Qt,H to Qt,1 with initial value Qt,H(s, a) = 0. Compared with UCRL in Lattimore and Hutter [14], UCBVI-γ does not need to call an additional extended value iteration sub-procedure [10, 26], which is not easy to implement even with infinite computation [14].
Algorithm 1 Upper Confidence Value-iteration UCBVI-γ 1: Receive state s1 and set initial value function Q1(s, a)← 1/(1− γ), N0(s, a) = N0(s, a, s′) = N0(s)← 0 for all s ∈ S, a ∈ A, s′ ∈ S
2: for step t = 1, . . . do 3: Let πt(·) ← argmaxa∈AQt(·, a), take action at ← πt(st) and receive next state st+1 ∼ P(·|st, at) 4: Set Nt(s) ← Nt−1(s), Nt(s, a) ← Nt−1(s, a) and Nt(s, a, s′) ← Nt−1(s, a, s′) for all s ∈ S, a ∈ A, s′ ∈ S 5: Update Nt(st) ← Nt(st) + 1, Nt(st, at) ← Nt(st, at) + 1 and Nt(st, at, st+1) ← Nt(st, at, st+1) + 1 6: For all s ∈ S, a ∈ A, set
Pt(s′|s, a) = Nt(s, a, s
′)
Nt(s, a) ∨ 1 . (4.1)
7: Update new value function Qt+1(s, a) and Vt+1(s) by Qt+1(s, a) = min { Qt(s, a), r(s, a) + γ[PtVt](s, a) + CγUCBt(s, a) } ,
Vt+1(s) = max a∈A Qt+1(s, a). (4.2)
where
UCBt(s, a) =
√ 8UVars′∼Pt(·|s,a)(Vt(s′))
Nt(s, a) ∨ 1 + 8U/(1− γ) Nt(s, a) ∨ 1
+
√ 8 ∑ s′ Pt(s′|s, a) min { 100Bt(s′), 1/(1− γ)2 } Nt(s, a) ∨ 1 , (4.3)
and Bt(s′) = β/ [ (1− γ)5 ( Nt(s ′) ∨ 1 )] .
8: end for
Computational complexity In each step t, Algorithm 1 needs to first compute the empirical transition Pt and update the value function Vt+1 by one-step value iteration, which will cost O(S2A) time complexity for each update. However, the number of updates can be reduced by using the “batch” update scheme adapted in [10, 7] and in this case Algorithm 1 only needs to update the value function Vt+1 when the number of visits Nt(s, a) doubles. With this update scheme, the number of updates is upper bounded by O(SA log T ) and the total cost for updating the value function is O(S3A2 log T ). In addition, the Algorithm 1 still needs to choose the action with respect to the value function Vt and it costs O(AT ) time complexity. Thus, the total computation complexity of the “batch” version of Algorithm 1 is O(AT + S3A2 log T ).

heading: 4.2 Regret Analysis
text: In this subsection, we provide the regret bound of UCBVI-γ. We first give the formal definition of the regret for the discounted MDP setting. Definition 4.1. For a given non-stationary policy π, we define the regret Regret(T ) as follow:
Regret(T ) = T∑ t=1 [ V ∗(st)− V πt (st) ] .
The same regret has been used in prior work [30, 35, 34] on discounted MDPs. It is related to the “sample complexity of exploration” [12, 14, 9]. For more details about the connection between the regret and the sample complexity, please refer to Appendix A. Remark 4.2. Without the use of generative model [12], an agent may enter bad states at the first few steps in discounted MDPs and there is no “restarting” mechanism as in episodic MDPs that can prevent the agent from being stuck in those bad states. Due to this limitation, both the regret and the sample complexity of exploration guarantees are not sufficient to ensure a good policy being learned. We think this is the fundamental limitation in the online learning of discounted MDPs.
With Definition 4.1, we introduce our main theorem, which gives an upper bound on the regret for UCBVI-γ. Theorem 4.3. Let U = log(40SAT 3 log2 T/(δ(1 − γ)2)). If we set β = S2A2U5 in UCBVI-γ, then with probability at least 1− δ, the regret of UCBVI-γ in Algorithm 1 is bounded by
Regret(T ) ≤ 752S 2A1.5U3.5
(1− γ)3.5 +
60U √ SAT
(1− γ)1.5 +
4 √ TU
(1− γ)2 .
Remark 4.4. Notice that when T = Ω̃(S3A2/(1− γ)4) and SA = Ω(1/(1− γ)), the regret is bounded by Õ (√ SAT/(1− γ)1.5 ) . In addition, since Regret(T ) ≤ T/(1− γ) holds for any T ,
we have E[Regret(T )] = Õ (√ SAT/(1− γ)1.5 + Tδ/1− γ ) . When choosing δ = 1/T , we have
E[Regret(T )] = Õ (√ SAT/(1− γ)1.5 ) .
We also provide a regret lower bound, which suggests that our UCBVI-γ is nearly minimax optimal. Theorem 4.5. Suppose γ ≥ 2/3, A ≥ 30 and T ≥ 100SAL/(1− γ)4, then for any algorithm, there exists an MDP such that
E[Regret(T )] ≥ √ SAT 10000(1− γ)1.5 − 4 √ STL (1− γ)1.5 − 8S (1− γ)2 ,
where L = log (300S4T 2/(1− γ)) log(10ST ). Remark 4.6. When T is large enough and A = Ω̃(1), Theorem 4.5 suggests that the lower bound of regret is Ω̃( √ SAT/(1− γ)1.5). It can be seen that the regret of UCBVI-γ in Theorem 4.3 matches this lower bound up to logarithmic factors. Therefore, UCBVI-γ is nearly minimax optimal.

heading: 5 Proof of the Main Results
text: In this section, we provide the proofs of Theorems 4.3 and 4.5. The missing proofs are deferred to the appendix.

heading: 5.1 Proof of Theorem 4.3
text: In this subsection, we prove Theorem 4.3. For simplicity, let δ′ = (1− γ)2δ/(80T log2 T ), then U = log(SAT 2/δ′). We first present the following key lemma, which shows that the optimal value functions V ∗ and Q∗ can be upper bounded by the estimated functions Vt and Qt with high probability: Lemma 5.1. With probability at least 1− 64Tδ log2 T/(1− γ)2, for all t ∈ [T ], s ∈ S, a ∈ A, we have Qt(s, a) ≥ Q∗(s, a), Vt(s) ≥ V ∗(s).
Equipped with Lemma 5.1, we can decompose the regret of UCBVI-γ as follows:
Regret(T ) ≤ T∑ t=1 [ Vt(st)− V πt (st) ] = T∑ t=1 [ Qt(st, at)−Qπt (st, at) ] ︸ ︷︷ ︸
Regret′(T )
,
where the inequality holds due to Lemma 5.1. Therefore, it suffices to bound Regret′(T ). We have
Regret′(T ) ≤ T∑ t=1 ( r(st, at) + γ[Pt−1Vt−1](st, at) + CγUCBt−1(st, at)
− r(st, at)− γ[PV πt+1](st, at) )
= T∑ t=1 ( γ[Pt−1Vt−1](st, at) + CγUCBt−1(st, at)− γ[PV πt+1](st, at) ) ,
where the inequality holds due to the update rule (4.2) and the Bellman equation Qπt (st, at) = r(st, at) + γ[PV πt+1](st, at). We further have
T∑ t=1 ( γ[Pt−1Vt−1](st, at) + CγUCBt−1(st, at)− γ[PV πt+1](st, at) )
= T∑ t=1
γ(Vt−1(st+1)− V πt+1(st+1))︸ ︷︷ ︸ I1 +
T∑ t=1 γ [ (Pt−1 − P)(Vt−1 − V ∗) ] (st, at)︸ ︷︷ ︸
I2
+ T∑ t=1
γ[(Pt−1 − P)V ∗](st, at)︸ ︷︷ ︸ I3 +
T∑ t=1
CγUCBt−1(st, at)︸ ︷︷ ︸ I4
+ T∑ t=1 γ [ P(Vt−1 − V πt+1) ] (st, at)− γ [ Vt−1(st+1)− V πt+1(st+1) ] ︸ ︷︷ ︸
I5
. (5.1)
In the above decomposition, term I1 controls the estimation error between the value functions Vt−1 and V πt+1, terms I2 and I3 measure the estimation error between the transition probability function P and the estimated transition probability function Pt−1, term I4 comes from the exploration bonus in Algorithm 1, and term I5 accounts for the randomness in the stochastic transition process, which can be controlled by the third term O( √ TU/(1− γ)2) in Theorem 4.3.
In the remaining of the proof, it suffices to bound terms I1 to I5 separately.
First, I1 can be regarded as the difference between the estimated Vt−1 and the value function V πt+1 of policy π, and it can be bounded by the following lemma. Lemma 5.2. For the term I1, We have I1 ≤ γRegret′(T ) + (2S + 2)γ/1− γ
Next, I2 can be regarded as the “correction" term between the estimated Vt−1 and the optimal value function V ∗. It can be bounded by the following lemma. Lemma 5.3. With probability at least 1− 64Tδ log2 T/(1− γ)2 − 3δ, we have
I2 ≤ (1− γ)Regret′(T )/2 + √ 2TClog(1/δ) + 5S2AClog(ST/δ) log(3T )
(1− γ)2 .
In addition, I3 can be regarded as the error between the empirical probability distribution Pt−1 and the true transition probability P. Note that V ∗ is a fixed value function that does not have any randomness. Therefore, I3 can be bounded through the standard concentration inequalities, and its upper bound is presented in the following lemma. Lemma 5.4. With probability at least 1− 2δ − δ/(1− γ), we have
I3 ≤ 2SAU2 1− γ + U √ 2SA
√ 5T
1− γ +
29U
3(1− γ)3 + 2Regret′(T ) 1− γ +
√ 2TU
(1− γ)2 .
Furthermore, I4 can be regarded as the summation of the UCB terms, which is also the dominating term of the total regret. It can be bounded by the following lemma. Lemma 5.5. With probability at least 1− 4δ − δ/(1− γ), we have
I4 ≤ 37S2A1.5U3.5 (1− γ)2.5 + U √ 8SA
√ 5T
1− γ +
29U
3(1− γ)3 + 2Regret′(T ) 1− γ + 12SU
√ AT
(1− γ)2 .
Finally, I5 is the summation of a martingale difference sequence. By Azuma-Hoeffding inequality, with probability at least 1− δ, we have
I5 ≤ √ 2T log(1/δ)
1− γ . (5.2)
Substituting the upper bounds of terms I1 to I5 from Lemma 5.2 to Lemma 5.5, as well as (5.2), into (5.1), and taking a union bound to let all the events introduced in Lemma 5.2 to Lemma 5.5 and (5.2) hold, we have with probability at least 1− 20TU2δ/(1− γ)2, the following inequality holds:
(1− γ)Regret′(T ) ≤ 160S 2A1.5U3.5
(1− γ)2.5 +
54U √ SAT√
1− γ +
2 √ 2TU
1− γ + 12U
√ SARegret′(T )
1− γ .
(5.3)
Using the fact that x ≤ a+ b √ x⇒ x ≤ 1.1a+ 4b2, (5.3) can be further bounded as follows
Regret(T ) ≤ Regret′(T )
≤ 752S 2A1.5U3.5
(1− γ)3.5 +
60U √ SAT
(1− γ)1.5 +
4 √ TU
(1− γ)2 .
This completes our proof.
5.2 Proof of Theorem 4.5
s1,0 ... ... ... s1,1
1− γ + γ −
1− γγ
s2,0 1− γ
γ
... ... ... s2,1
sS−1,0... ... ... sS−1,1sS,0... ... ... sS,1
Figure 1: A class of hard-to-learn MDPs considered in Theorem 4.5. The MDP can be regarded as a combination of S two-state MDPs, each of which is an MDP illustrated on the top-left corner. In addition, the i-th two-state MDP has the a∗i -th action as its optimal action. The blue arrows represent the optimal actions in different states. = √ A(1− γ)/K/24.
In this subsection, we provide the proof of Theorem 4.5. The proof of the lower bound is based on constructing a class of hard MDPs. Specifically, the state space S consists of 2S states {si,0, si,1}i∈[S] and the action space A contains A actions. The reward function r satisfies that r(si,0, a) = 0 and r(si,1, a) = 1 for any a ∈ A, i ∈ [S]. The probability transition function P is defined as follows.
P(si,1|si,0, a) = 1− γ + 1a=a∗i 1
24
√ A(1− γ)
K ,P(si,1|si,1, a) = γ,
P(si,0|si,0, a) = γ − 1a=a∗i 1
24
√ A(1− γ)
K ,P(si+1,0|si,1, a) = 1− γ,
where we assume sS+1,0 = s1,0 for simplicity and a∗i is the optimal action for state si,0. The MDP is illustrated in Figure 1, which can be regarded as S copies of the “single" two-state MDP arranged in a circle. The two-state MDP is the same as that proposed in [15]. Each of the two-state MDP has two states and one “optimal" action a∗i satisfied P(si,1|si,0, a∗i ) = 1 − γ + . Compared with the MDP instance in [10], both instances use S copies of a single MDP. However, unlike the MDP in [10] which only has one “optimal" action among all SA actions, our MDP which has in total S “optimal" actions, which makes it harder to analyze.
Now we begin to prove our lower bound. Let Ea∗ [·] denote the expectation conditioned on one fixed selection of a∗ = (a∗1, . . . , a ∗ S). We introduce a shorthand notation E∗ to denote E∗[·] = 1/AS · ∑
a∗∈AS Ea∗ [·]. Here E∗ is the average value of expectation over the randomness from MDP defined by different optimal actions. From now on, we aim to lower bound E∗[Regret(T )], since once E∗[Regret(T )] is lower bounded, E[Regret(T )] can be lower bounded by selecting a∗1, . . . , a∗S which maximizes E[Regret(T )]. We set T = 10SK in the following proof. Based on the definition of E∗, we have the following lemma. Lemma 5.6. The expectated regret E∗[Regret(T )] can be lower bounded as follows:
E∗[Regret(T )] ≥ E∗ [ T∑ t=1 V ∗(st)− r(st, at) 1− γ ] − 4 (1− γ)2 .
By Lemma 5.6, it suffices to lower bound ∑T t=1[V
∗(st)− r(st, at)/(1− γ)], which is RegretLiu(T ) defined in [15]. When an agent visits the state set {sj,0, sj,1} for the i-th time, we denote the state in {sj,0, sj,1} it visited as Xj,i, and the following action selected by the agent as Aj,i. Let Tj be the number of steps for the agent staying in {sj,0, sj,1} in the total T steps. Then the regret can be further decomposed as follows:
E∗ [ T∑ t=1 V ∗(st)− r(st, at) 1− γ ] = S∑ j=1 E∗ [ Tj∑ i=1 V ∗(Xj,i)− r(Xj,i, Aj,i) 1− γ ] = I1 + I2 + I3,
where
I1 = S∑ j=1 E∗ [ K∑ i=1 V ∗(Xj,i)− r(Xj,i, Aj,i) 1− γ ] ,
I2 = S∑ j=1 E∗ [ Tj∑ i=K+1 V ∗(Xj,i)− r(Xj,i, Aj,i) 1− γ ∣∣∣∣Tj > K] · P∗[Tj > K], I3 = −
S∑ j=1 E∗ [ K∑ i=Tj+1 V ∗(Xj,i)− r(Xj,i, Aj,i) 1− γ ∣∣∣∣Tj < K] · P∗[Tj < K]. Note that I1 essentially represents the regret over S two-state MDPs in their first K steps, and it can be lower bounded through the following lemma.
Lemma 5.7. If K ≥ 10SA/(1− γ)4, then for each j ∈ [S], we have
E∗ [ K∑ i=1 (1− γ)V ∗(Xj,i)− r(Xj,i, Aj,i) ] ≥
√ AK
2304 √ 1− γ − 1 1− γ .
This lemma shows that the expected regret of first K steps on states sj,0 and sj,1 is at least Ω̃ (√ AK/(1− γ)0.5 − 1/(1− γ) ) . Therefore by Lemma 5.7, we have
I1 = S∑ j=1 E∗ [ K∑ i=1 V ∗(Xj,i)− r(Xj,i, Aj,i) 1− γ ] ≥
√ SAT
2304 √ 10(1− γ)1.5 − S (1− γ)2 . (5.4)
To bound I2, we need the following lemma.
Lemma 5.8. With probability at least 1−2STδ log T/(1−γ), for each j ∈ [S] and K+1 ≤ t ≤ T , we have
t∑ i=K+1 V ∗(Xj,i)− r(Xj,i, Aj,i) 1− γ ≥ −
√ 2t log(1/δ) log T
(1− γ)1.5 − 4 (1− γ)2 .
Lemma 5.8 gives a crude lower bound of I2. Taking expectation over Lemma 5.8 and taking summation over all states, we have
I2 ≥ S∑ j=1 E∗ [( − √ 2Tj log(1/δ) log T (1− γ)1.5 − 4 (1− γ)2 )∣∣∣∣Tj > K]P∗[Tj > K] −
S∑ j=1 T 1− γ · 2STδ log T (1− γ)2
≥ S∑ j=1 E∗ [ − √ 2Tj log(1/δ) log T (1− γ)1.5 ] − 4S (1− γ)2 − 2S 2T 2δ log T (1− γ)2 ≥ S∑ j=1 − √ 2E∗[Tj ] log(1/δ) log T (1− γ)1.5 − 4S (1− γ)2 − 2S 2T 2δ log T (1− γ)2
≥ − √ 2ST log(1/δ) log T
(1− γ)1.5 − 4S (1− γ)2 − 2S
2T 2δ log T (1− γ)2 , (5.5)
where the first inequality holds due to Lemma 5.8, the second inequality holds since 1 − 2STδ log T/(1− γ) ≤ 1 and E[−X|Y ]P(Y ) ≥ E[−X] when X ≥ 0, the third inequality holds due to Jensen’s inequality and the fact that √ x is a concave function, and the last inequality holds due to
Jensen’s inequality and the fact that ∑S j=1 E∗[Tj ] = T . To bound I3, we need the following lemma, which suggests that when K is large enough, Ti > K happens with high probability: Lemma 5.9. When K ≥ 10A log(1/δ)/(1− γ)4, with probability at least 1− 2Sδ, for all i ∈ [S], we have Ti > K. Notice that the difference of transition probability between the optimal action and suboptimal actions is √ A(1− γ)/24K. In this case, when T is large enough, Ti is close to T/S = 10K. Thus I3 can be lower bounded as follows:
I3 ≥ − S∑ j=1 K 1− γ P∗[Tj < K] ≥ − STδ 5(1− γ) , (5.6)
where the first inequality holds due to 0 ≤ r(Xj,i, Aj,i) ≤ 1 and the second inequality holds due to Lemma 5.9. Finally, setting δ = 1/ ( 4ST 2(1− γ)2 log T ) , we can verify that the requirements
of K in Lemma 5.7 and Lemma 5.9 hold when T satisfies T ≥ 100SAL/(1− γ)4, and L = log (300S4T 2/((1− γ)2δ)) log T . Therefore, substituting δ = 1/ ( 4ST 2(1− γ)2 log T ) into (5.5) and (5.6), and combining (5.4), (5.5), (5.6) and Lemma 5.6, we have
E[Regret(T )] ≥ √ SAT 10000(1− γ)1.5 − 4 √ STL (1− γ)1.5 − 8S (1− γ)2 ,
which completes the proof of Theorem 4.5.

heading: 6 Conclusions and Future Work
text: We proposed UCBVI-γ, an online RL algorithm for discounted tabular MDPs. We show that the regret of UCBVI-γ can be upper bounded by Õ( √ SAT/(1− γ)1.5) and we prove a matching lower bound on the expected regret Ω̃( √ SAT/(1− γ)1.5). There is still a gap between the upper and lower bounds when T ≤ max{S3A2/(1 − γ)4, SA/(1 − γ)4}, and we leave it as an open problem for future work.
Acknowledgments and Disclosure of Funding We thank Csaba Szepesvári for a valuable suggestion on improving the presentation of the proof. We thank the anonymous reviewers for their helpful comments. JH, DZ and QG are partially supported by the National Science Foundation CAREER Award 1906169, IIS-1904183, BIGDATA IIS-1855099 and AWS Machine Learning Research Award. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.

Review summaries:
The authors study the problem of learning a discounted tabular-MDP. They adopt a notion of regret that is closely related to policy identification problem.  The authors make two main contributions: 1. They show how to adapt UCBVI to discounted MDP. This lead to an algorithm called UCBVI-\gamma algorithm. This model-based algorithm uses OFU principle by computing Bernstein-type bonus for empirical Q-function. The policy of the algorithm is updated every time step (online algorithm).  The author prove that its regret is upper bounded by \tilde{O}(\sqrt{SAT}/(1-\gamma)^1.5) where \gamma is the discount factor.  2. The authors also derive a minimax lower bound for the problem that essentially match the upper bound of the algorithm {\Omega}(\sqrt{SAT}/(1-\gamma)^1.5). This shows that their algorithm is minimax-optimal. 

This work studies the problem of learning stochastic discounted infinite-horizon Markov Decision Processes (MDPs) with unknown transition. The authors propose an algorithm UCBVI-gamma based on recent advances in episodic MDPs (e.g. Azar et al., 2017; Jin et al., 2018; Zanette and Brunskill, 2019) and specifically the Bernstein-type exploration bonus. Besides, the authors provide a lower bound which indicates that UCBVI-gamma matches the minimax lower bound up to logarithmic factors.