Online Reinforcement Learning via Posterior Sampling of Policy
Authors: Shuqing Shi
zhiqiang xu
Fan Zhang
Zhiyou Yang
Yali Du
Hong Qu
Venue: Submitted to ICLR 2023 (2023)

Abstract: We propose a Reward-Weighted Posterior Sampling of Policy (RWPSP) algorithm to tackle the classic trade-off problem between exploration and exploitation under finite Markov decision processes (MDPs). The Thompson sampling method so far has only considered posterior sampling over transition probabilities, which is hard to gain the globally sub-optimal rewards. RWPSP runs posterior sampling over stationary policy distributions instead of transition probabilities, and meanwhile keeps transition probabilities updated.  Particularly, we leverage both relevant count functions and reward-weighting to online update the policy posterior, aiming to balance between local and long-term policy distributions for a globally near-optimal game value. Theoretically, we establish a bound of $\tilde{\mathcal{O}}(\Gamma\sqrt{T}/S^{2})$\footnote{The symbol $\tilde{\mathcal{O}}$ hides logarithmic factors.} on the total regret in time horizon $T$ with $\Gamma/S^{2} < D\sqrt{SA}$ satisfied in general, where $S$ and $A$ represents the sizes of state and action spaces, respectively, $D$ the diameter. This matches the best regret bound thus far for MDPs. Experimental results corroborate our theoretical results and show the advantage of our algorithm over the state of the art in terms of efficiency.

Under review as a conference paper at ICLR 2023
ONLINE REINFORCEMENT LEARNING VIA POSTERIOR SAMPLING OF POLICY
Anonymous authors Paper under double-blind review
ABSTRACT
We propose Reward- Reward-Weighted Posterior Sampling of Policy (RWPSP) algorithm to tackle the classic trade-off problem between exploration and exploitation under finite Markov decision processes (MDPs). The Thompson sampling method so far has only considered posterior sampling over transition probabilities, which is hard gain the globally sub-optimal rewards. RWPSP runs posterior sampling over stationary policy distributions instead of transition probabilities, and meanwhile keeps transition probabilities updated. Particularly, we leverage both relevant count functions and seward-weighting to online update the policy posterior, aiming to balance between local and long-term policy distributions for globally near-optimal game value. Theoretically, we establish a bound of ÓTVVT/S² [
on the total regret time horizon with S/S² < DV satisfied general, where S and A represents the sizes of state and action spaces, respectively. D the diameter. This matches the best regret bound thus for MDPs. Experimental results corroborate theoretical results and show the advantage of our algorithm over baselines in terms of efficiency.
INTRODUCTION
Online reinforcement learning (Wei al. 2017) addresses the problem of learning and planning in real-time sequential decision making systems with the interacting environment partially observed or fully observed. The decision maker tries to maximize the cumulative reward during the interaction with the environment, which however inevitably leads to the trade-off between exploration and exploitation. Many attempts have been made to mitigate such dilemma by improving underlying regret bounds (Zhang et al. (0200)(Mééan) et al.] 22han al.) b021b) (Zhang et al. 2022 (Agrawal ctt al. 2021).
Trade-off between exploration and exploitation has been studied extensively in various scenarios. The goal of exploration to find as much information as possible of the environment, while the exploitation process aims maximize the long-term term total reward based on the exploited part of the environment. To handle the trade-off problem, one popular way is to use the naive exploration method such adaptive e-greedy exploration (Tokic. 2010). The method adjusts the exploration parameter adaptively, depending on the cumporal-difference (TD) error observed from the value function. Optimistic initialisation methods have also been studied in factored MDPs (Szita & Lörinez 2009
Brafman & Tennenholtz] 2003). They encourage systematic exploration in the early stage. Another the optimism the face of uncertainty (OFU) principle (Lai & Robbins 1985
common way is
where the agent constructs confidence sets to search for the optimistic parameters associated with the maximum reward. Thompson sampling, as an OFU-based approach, was originally presented for stochastic bandit scenarios (Thompson, 1933). It has been applied in various MDPs contexts (Oshand et 2013 Agrawal & Goyal (012)) since it can achieve tighter bounds (Ding et al.) 202T Oh & Iyengar 2019 Moradipari et al. 2019) and better compatibility with other structures in both
theory and practice (Chapelle Li, 201 1; Zhang et al., 10 Agrawal Goyal 2013). has also achieved great performance contextual bandit problems(Agrant Agrawal & Jia 2017MOsband & Van Roy 20baadOsband et al. The general optimistic algorithms require to solve all MDPs lying within the confident sets, while Thompson sampling- caaseing-based algorithms only need to solve the sampled MDPs
'The symbol Ô hides logarithmic factors.

---

Under review as a conference paper at ICLR 2023
to achieve similar results (Russo & Van Roy 2014). Thompson sampling offers speedup one hand, and results in biased estimates of the transition matrix on the other hand.
This paper addresses the trade-off problem between exploration and exploitation in finite MDPs. We propose a rewaht-weighted posterior sampling of policy (RWPSP) algorithm that samples posterior policy distributions rather than posterior transition distributions, which optimizes the long-term policy probability distribution. While updating posterior policy distribution, we use the count functions of the state-action pairs to capture the importance of each sampled episode. This way, we manage to optimize the policy distribution in time horizon T and achieve the total regret bound of
with r/s² < DVSA, where S and represent the sizes of the state and action spaces respectively. D is the diameter of the finite MDP. In addition, we propose a new Bayesian method to update transition probabilities which also achieves a state-of-art regret bound. In comparison, existing model-based methods like Upper Confidence Stochastic Game Algorithm(U/CSC achieve regret bound of (VDS2 on stochastic MDPs (Wei et al. 2017). while model-free methods like optimistic Q-learning achieve regret bound of O (T2)3) under MDPs Wei et al. 2020). To summarize, this work makes the following contributions:
average reward
We propose weightee posterior sampling of policy (RWPSP) algorithm that strikes a balance between the posterior projection of the long-term policy and the local policy.
RWPSP is the first posterior sampling method that samples posterior policy distributions while Bayesian updating transition probabilities. It achieves a regret bound of Ö ((5) where T/5² < DVSA. We show that the total regret bound is less than the state-of fifie-of-the- afrt, i.e., DVSAT, to the best of our knowledge.
We conduct experimental studies to verify our theoretical results and demonstrate that our RWPSP algorithm outperforms other online learning methods in complex MDP environ- ments.
RELATED WORK
Regret Bound Analysis In the finite-horizon setting, most of the Thompson Sampling-bast based algorithms follow a basel- approach (Abbasi Yadkori et al.) 2013) Xu & Tewari, 2020 Auer cet al. 2008 Fruit et al.) 2020; Dong et al. 2020][Agarwar et 2020). as model-based reinforcement learning methods are required to approximate the optimal transition matrix of MDP. In Xu & Tewari (2020), eoi-edico factored Markov decision processes are sampled using extreme transition dynamics which encourages visiting new states in order to minimize regret. Although various approaches had been used to minimize the regret bound, current methods still minimize the regret bound by updating the transition matrix. A good comparison can be found in Zhang al. (2021c); Weil eet al.] (2020) among existing Thommson sampling based methods. In contrast to existing works with focus on posterior sampling over transition matrices, our work only considers posterior sampling over policy distributions in finite-horizon MDP. The transition probabilities will be updated based on the real trajectory. On the other hand, while existing model- free methods have not yet achieved the state-of-at art regret bound (Jin et al. 2018: Strehl et al. 2006). some of them improved the total regret bound (Zhang et al. 2020a).
Intrinsic Reward Shaping Intrinsic reward shaping was first introduced in 1999 (Ng et al. 1999). which is a generic idea to guide the policy iteration with intrinsic reward. Count-based methods are then proposed reach nearly state-of-the-an performance on a nigh-dimensional environment (Tang et al. 2017). Intrinsic reward is also used in Du et al. (2019) to compute a distinct proxy critic for the agent to guide the update of its individual policy. In order to shape the reward during the policy iteration, we adopt the weight- update to verify the intrinsic reward. Count functions of states and/or actions are usually used the exploration process of an agent to help build the intrinsic reward (Tang al. 2017 Bellemare al. 2016 Burda et al. 2018 In our algorithm, we consider the count function as the posterior projection of the intrinsic reward, and then use the generated reward to update the posterior distribution. The previous methods mainly focus on the instantaneous rewards generated from the exploration process, while our method uses a reward weighte count function to generate long-term rewards which can guide the policy towards globally optimal value.
2

---

Under review as a conference paper at ICLR 2023
3 PROBLEM SETTING
3.1 MARKOV DECISION PROCESS
A finite stochastic Markov decision process (fMDP) (Ferns et al. 2004) could be defined by tuple M = (S, r. A. respectively. represents the reward function defined by S x A |0, 1 represent the transition probability such that 0 (s' 8,a) = IP (8t+1 ground-truth transition probability 0. is randomly generated before the game starts, which is then fixed and unknown to the agent. For the model-based agents, the transition probability at time step t within episode & could be defined as 0.. As for each episode, the transition probability would be defined as 0g. A stationary policy S - a deterministic function that maps a state to an action. We could define the instantaneous policy under transition probability bt, as To., The globally optimal policy under local optimal transition probability and global optimal transition probability could be defined as TØ.y and _Ø respectively. For notational brevity, let it. T&. Tie - To.," x _ TØ.
Denote the sizes of the state and action spaces S S] and A [A]. Let x A x S 8 ===a 8,00 = a). The
In the fMDP, the average reward function per time step under stationary policy is defined as:
T+T Σ r (se, av)
((TO)) = lim
E
(1)
T-
Therefore, we could denote the instantaneous average reward under transition probability 0.2 as J ) Note that ( ) is hypothetical average reward generated from 0r, and Tty The locally optimal average reward J (m could be derived from the corresponding locally optimal policy "t.- The globally optimal average reward could be represented as J(r*). Define the maximum average reward as r = max J )TTO). which is the maximum average reward that an agent could achieve during its exploration in a fMDP. The maximum value I' will be achieved under the optimal transition probability with the optimal stationary policy, i.c., I = (xr).
In the online learning setting, total regret is defined to be the difference between the optimal total game value and the actual game value as follows:
T
Reg max Σ (st a) Σ (().
is used to measure the performance of a decision maker. Since this metric is hard to calculate in general, define the following bias vector b(0, π,, (Wei et al. 2017) the relative advantage of each state to help us measure the total regret.
b(0, - E
Σ
-s) J(T) =.a x-1ss)
Under stationary policy т, the advantage of one state s over another state s' is defined as the difference between their accumulated rewards with initial states and s', respectively, which will eventually converge to the difference of their bias vectors, i.e., 6(0, n, 8) b(0,T,, TT)) Denote the expected total reward under stationary policy ı by r(s, T) Eu 12 r(s, a)). and the expected transition probability by Po (s' T) Ea-r(1ss) (po (po(s'ls,a) a)]. The bias vector then satisfies the Bellman equation below:
((TO) + b(0,T,)) r( + Σ pa (s' 8,,))(0,777)),
(4)
Define the span of a vector x as sp(x) max o4 min x.. The regret strongly connected the span of bias vector b(O,, ग. :), i.e., sp(b(A., m," ))). The span of any b(0, .) upper bounded " (0.,), ), i.e., the maximum expected time to reach to state s' from state under by D A max Tx2
transition probability bt, and policy ne..
In finite MDP, the reward in each episade should be confined within |0, 1].
3

---

Under review as a conference paper at ICLR 2023
3.2 ASSUMPTIONS
The globally optimal policy is hard to learn for MDPs under online settings. As they often get stuck in locally optimal results. The e-tolerance then introduced help measure the performance of the algorithm. When the difference between the current average reward and the optimal average reward less than constant e, the current policy said be c-optimal.
Assumption 3.1. (e-Optimal policy) (Hartman probability, if policy St,, satisfies
1975) Under sub-optimal and optimal transition
Jr, (0,,) Jac, (0c)
Then, policy Tt. is e-optimal.
Assumption 3.2 implies that under all cireumstances, all the states could be visited in D steps average. When the agent conducts the optimal policy under the optimal transition probability, the transition time 1 (f.) should be the shortest, because the agent tends to explore the fewest non-
related states under the optimal stationary policy. In a similar fashion, the transition time "t (0t,) for agent conducting optimal policy under sub-optimal transition probability is assumed be less than the maximum transition time max,,8! o' T (0t.) in normal settings.
Assumption 3.2. (Expected transition time) When conducting stationary policy n, we assume that the maximum expected time to reach to state s' from state under sub- sub-optimal transition probability and optimal transition probability is less than constant D:
max T...(( S. max (0
T (Bo.) S max T Th (0..)
Let e(t) A be the episode where time instant belongs. When conducting stationary policy n, we could define the count function for the episode number e(t) as (Fe(()). Define Hay (k, m) as the set of all the time instants that the state transition $1 - $2 occurs in the first episodes with stationary policy used:
Hl(e (k,
Σ 1 (Te()) =, (St, S.41) = (21,
N ((Te()) S k}..
(5)
Under transition probability On the expected transition time from state to state s' with stationary policy Tes could be denoted as F.... i.c., Fxe, & (0..). Therefore, the posterior probability of the stationary policy be assumed as the difference between the empirical state pair frequency (k and the corresponding expected value ....'
Assumption 3.3. (Posterior distribution under sub-optimal trajectories) Gopalan & Mannor 2015
For any given 61,ey e2 2 O, there exists p & p()1,e2) > O satisfying 0gg (mT)) index k at which sub-optimal transition frequencies have been observed:
2 p for any episode
H4s 82)) 82) (k, a)
ei log (e2 logk)
Fir.. (51(52) s
52 E 1.
h
PROPOSED ALGORIHTM
In this section, we propose new algorithm to tackle the trade-off between exploration and ex- ploitation. One parameter that we need under the posterior sampling setting is the prior distribution, denoted as fin- Note that we generate prior distributions for both transition probabilities and stationary policies, but only do posterior sampling over stationary policy distributions. While the transition probabilities will be Bayesian updated by the trajectory generated from the posterior policy. In each episode k, at each time step t, the action would be sampled from the posterior policy distribution. And such policy distribution 14, (r) will be updated based on the previous history h4,- Let (2 a) be the number of visits to any state-action pair (s, a) during period of time t:
(s, 1[ t: (8r, 07) a))
(6)
4

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Reward Weighted Posterior Sampling of Policy (RWPSP)
Game environment, prior distribution for stationary policy Pro transition probability 0o. initial state So E S, time step & =. 0.
Input:
Output: Stationary policy тK
1: for Episode & = 0, 1, 2.. K do
2: T tx
3:
+-t
4: Generate ju (T&&) based prior distribution
Update 0g using 02 = 9x 1(4) (22.0g)+ H,, May,og (N,, (R).))
(+).z)
5:
(k)
6:
for S 4x + Th-1 and (1 a) S 2N,, (8, (8 do
7:
Sample Fe, Mr, (T) and apply action Observe new state 8141, reward r1+1
Tea
8:
Update posterior distribution pit+1), (T) using RWPI 10: t f +-t+1
9:
11:
end for
12: end for
We then have algorithm called the Reward-Weighted Weighted Posterior Sampling of Policy, RWPSP for short, described in Algorithm [
At the beginning of each episode the RWPSP algorithm, i.e., Algorithm I samples policy distribution from the prior distribution (((-11) (T&-1) (Line 4), which equals the updated posterior policy distribution from the last episode (Line 9). Then, the transition probability distribution will be generated from the history transition matrix 0/-1 and count function Ha, (Na (k), T) and Nr. (will be defined in Section 4.1 (Line 5). We use two stopping criteria to limit agent's exploration direction. The first stopping criterion aims to stop meaningless exploration, while the second stopping criterion ensures that any state-action pair (s, a) will not be encountered twice during the same episode (Line 6). At each time step /4, actions are generated from the instantaneous policy Tt, (Line 7) which follows a posterior distribution Pt, (T). These actions are then be used by the agent to interact with the environment observe the next state 81+1 and the reward Tr+1 (Line 8). The observation results are then be used to find the optimal posterior distribution for policy T(++1),
(Line 9).
4.1 UPDATE RULE
In previous Bayesian methods, the transition matrix is updated with Thompson/posterior sampling. But in our case, we apply posterior sampling over the policy distributions. Based on the Bayes" rule, the posterior distribution of policy can be written as:
(8t+1 18,, a+) (t. (T))
M++1(T) = Σ 0' (8141 at) Me (x')
The way update stationary policy resembles how Thompson sampling updates transition proba- bilities, as our algorithm uses the prior policy to guide the current policy. The key difference that Reward- Reward-Weighted Weighted Policy Iteration (RWPI) algorithm shown in Algorithm 2is able to balance between the instantaneous action and the history actions. This will help our method approximate the long-term maximum reward, which is the globally optimal value in this scenario. We could define We as the posterior weight in episode k at time t (Line 2 in Algorithm 2). Let Jnyg and J=;, denote the instantancous average reward and the locally optimal value. This locally optimal value is induced by adopting the greedy policy on the transition probabilities 0,. The value of Wt, is proportional to the log difference between the average reward of the locally optimal policy and the current policy. At last, we could generate the policy distribution (I() based on the previous policy distribution 14-1 (T)) and the current locally optimal policy गī (s. 0.) (Line 3 in Algorithm 2
We measure the distance between the history optimal policy and the instantaneous policy using the Marginal Kullback- Leibler Divergence (Marginal KI. Divergence) which is widely used metric
5

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Reward- Weighted Policy Iteration(RWPP)
Input:
Game environment, prior distribution for stationary policy pr(TT) Output: Stationary policy
1: repeat
Jr, 2: Wa (T) exp(E ( x) log (3)
3: (e(TT) = (T) + (1 (], = (8,00)
4: until (= (T) 6
for characterizing the difference between two probability distributions. The distance then could be written as follows:
log Me
Σ 51
Σ He (T)
Me (T)
81
#2ES
Σ 81ES
KLL (1.( (1a(T)))(),n
a,
Parameter c in Algorithm AigorithmZreprrsenttts the tolerance between the optimal policy and the instantaneous policy. RWPI updates the policy dynamically with the posterior weight. The policy will converge to an e-optimal value after certain number of iterations under this update method. In the following section, we will analyze the convergence this posterior update method and the total regret bound of our method.
5 MATHEMATICAL ANALYSIS
5.1 CONVERGENCE OF THE UPDATE RULE
We show the convergence of our posterior policy update method demonstrate its superiority, To this end, we need the following three Lemmas. Lemma 5.1 shows that RWPI enjoys asymptotic convergence. We then demonstrate Lemma [.2 that the output policy of such policy iteration method updates monotonically towards the optimal direction, which is vital evidence for the global optimality of our update method. At last, Lemma 5.3 proves that under MDP M, the output policy generated from the RWPI method would reach c-opimalltty after constant number of iterations.
Lemma 5.1. Suppose Assumption holds for some stochastic MDP M, then the policy iteration algorithm on M converges asymptotically.
Proof. If Assumption 3.2 holds, by Theorem 4 in Wal, van der (1977) the successive policy approxi- mation process yields an e-band and stationary e-optimal strategies for the agent. This results match Assumption 3.1 Therefore, the convergence of the policy could be proved.
Lemma 5.2. The average reward deducted by Algorithm 2 will be monotonically increasing.
Proof. From Algorithm
2 we can write the update rule of the average reward as follows:
Jz. -J (8) (We 1)J,- (1 Wo
(8)
= =(1 - (.) (s. J=._, (0)).
If Jn, (0) (8, then W. < since log J,-1s.8j (0) J=._, (0)
(0) < O, otherwise W. 2 1. Thus,
(J) (s, Jr._, (0)) 2 0.
(9)
That is, the sequence J=, (8) is monotonically increasing with time step t.
Lemma 5.3. Suppose Assumptions 3.2 hold for some stochastic MDP M. Let us be the state value in iteration i. Define N as the maximum iteration number of the algorithm. Then Tt, is e-optimal after N iterations.
Proof. The detailed proof is shown in Appendix A.2

---

Under review as a conference paper at ICLR 2023
5.2 REGRET BOUND ANALYSIS
In the proof of the regret bound, we always consider for the worst case. The randomness of the algorithm is reduced the minimum level in order get fair measurement of the performance of the algorithms. After proving the convergence of the RWPI method, we now turn to the proof of the total regret bound. The regret in time horizon T be written as:
Regr (JK)(OK)
Σ
T'e (st. 0e)
t=
(10)
TJ (0k)
Σ (0x)
+
JR. (0k)
Σ Jm, (0.)
RRegt + Regi.
Let the episode number be K in time horizon T. The regret are defined separately Regl. TJxx (0x) - Σi= Jz. (fx) and Reg = Σt= (0k))) - Ei= Jz,(0)), The final average reward under the final policy Ty and final transition matrix 0x defined as Jrx (0x). Regh represents the posterior policy regret and Regì represents the posterior transition probability regret. For any measurable function f and any h4, meesurable random variable X, E [f (0., X) heal = [f (0x, X) h Osband et al. 2013).
In order to bound the first regret Regr. we first bound the ratio between the expected optimal average reward and the instantancous reward. Based on Assumptions 3.3 the expected optimal reward that an agent could achieve in the fMDP could be bounded by parameter and e.
Lemma 5.4. log
Ju. (0) J.,, (0)
Proof. The detailed proof is shown in Appendix A.2
After bounding the log ratio between the expected optimal average reward and the instantancous reward, we now bound the instantaneous posterior weight Wt. which is important to our proof. At each time step, the posterior weight will be updated based on the previous policy and the observed {T(()) = T) as the total number
data. First, we define the counter function N+(1) == Σ of the time instants during the period of / when policy was conducted. When Assumption 3.3 holds, we could bound the posterior weight based on the count function episode k and the average transition time 7.
Lemma 5.5. Under Assumption 3.3 for each stationary near-optimal policy π and episode k 2 1. The following upper bound holds for negative log-density:
llog W.. (x) < (ISP(p(ka) + + tt..)).
The real reward is expected to get close to the expected reward by certain optimization method. A large number of iterations would be needed for this purpose. Therefore, from the convergence proof proposed in section 5.I. we could derive the bound on the expected convergence time during the optimization process. In Lemma [.6 we give the bound on the instantancous difference between the real reward and the expected reward with VT. This bound inversely proportional to vT, since our update method updates towards the optimal direction (see Lemma (.2).. For brevity, the full proof will be given in Appendix A.5
Lemma 5.6. The difference between the local optimal average reward and the instantaneous average
reward can be bounded as JJz, J+ Ó g-VT
We then could combine the previous Lemmas together to get the final regret bound of Regr. Theorem 5.7. The first part of the regret in time horizon T is bounded by: Regr I Õ(TVT)
is not clear if the above result improves over the state-of-art methods. We further give a tighter bound for our method below, which shows that under the fMDP our method has a lower regret bound compared to the current state-of-art method Ö(DVSAT).
7

---

Under review as a conference paper at ICLR 2023
Lemma 5.8.
F 32 DVSA when |S| 2 or |A] 2 2.
The second regret Reg represents the posterior difference generated by the update method of the transition probability. First, we use the definition of the Bellman iterator of the average reward transmit the one-step posterior transition difference into the difference between the transition probability. Then we apply the Assumption 3.3 to help bound such difference. At last, the regret could be bounded by summing all the one-step posterior transition difference.
Theorem 5.9. The regret caused by transition matrix update could be bounded by: Reg - Ō(D(SAT)))
EXPERIMENT
In this section, we compare our method with various state-of-the-arr methods: SACL (Fruit al. 2018a), UCRL2 (Auer et al. 2008). UCRL2B (Fruit et al. 2020), UCRL3 (Bourel et al. 2020). and KL-UCRL (Talebi Maillard 2018). SACL is an exploartion-bast based method that uses proper exploration bonus to solve any discrete unknown weakly-commmnicating MDP. It admits regret bound O (D Es,a K (Tgg( (Fruit et al. 2018b). UCRL2, UCRL2B, and UCRL3 are
three optimistic methods that used certain confidence bounds to minimize the total regret. The UCRL2 algorithm performs the regret minimization in unknown discrete MDPs under average-reward criterion. UCRL2B refines the previous UCRL2 method by exploiting empirical Bernstein inequalities to prove a regret bound of O(DVTSAT) where max,.a [(s, a) S S. UCRL3 modifies the previous algorithms by using time-uniform concentration inequalities to compute confidence sets the reward and transition distributions for each state-action pair. Finally, the KL-UCRL studied the ergodic MDPs and proposed gegh-rrbbbbility regret bound Ô the bias function with respect the next-state distribution following action in state
(VS 5555... s,a Vi.oT) where V the variance of
1.0
CunRoward
CurfRooord
3.0
0.2
0.6
0.8
1.0
0.0
0.2
0.6
1.0
Time steps
x10
Time stops
x10
Figure 1: RiverSwim25-biChar
Figure 2: RiverSwimErgo50
LIGRL3
UCAL3
CumRRwward
CumRowwrr
3.0
0.2
0.4
0.6
0.3
1.0
0.0
0/2
0.6
1.0
Time stops
x10*
Time stops
x10
Figure 3: Three-States
Figure 4: Four-Rooms
In order to measure the performance of our method empirically, we consider several traditional game environments:
RiverSwim, 4-room, and three-state. RiverSwim is one of the most important
8

---

Under review as a conference paper at ICLR 2023
metrics for online learning algorithms. It was first proposed in Sttrhl & Littman (2008) by Michael L. Littman in 2008. The basic RiverSwim consists of six states. The agent starts from a random state and the two actions available to the agent are to swim left or right. But the current will push the agent to the left side. The agent will receive a much larger reward for swimming upstream and reaching the rightmost state. In our experiment, we use its enhanced version: RiverSwimErgo500, The RiverS SiverSwim25--iclaeee is a 25-state communicating riverSwim environment with transition probability for the middle states cut in two subsets. And the RiverSwimErgoo is a 50-states ergodic RiverSwim environment. For the three-state environment, it was first proposed in Fruit al. (2018b) as the metric for the SACL. It is an environment with random reward that contains three states and two actions. 4-room is classic reinforcement learning environment, where the agent must navigate a maze composed four rooms interconnected by 4 gaps in the walls. To obtain a reward, the agent must reach the green goal square.
SeeerrSwi22-BBiiilee and
In the experiment, we use the cumulative reward as the metric. We can see from Figure [nnd Figure 2 that the RWPSP method tends to perform better in the high-dimensional games like RiverS wwim2-- biclass and SeeerSSii--rgoooo than other state-of-the-arr methods, which matches our theoretical analysis since RWPSP is designed to discover the long-term average reward in finite-horizon MDPs. Also, our algorithm performs well in three-state case and surpasses the performance of SCAL. We observe that our method RWPSP shows significant improvements over other methods in RiverSwim25- Biclass, RiverSwimErgo50 and 4-room. That is because the total regret bound Ō (T/T of our method indicates that the regret bound will decrease when the number of states of the environment increases. Thus, our method RWPSP performs pretty well on complex online learning environments.
$2
7 CONCLUSION
In this work, we propose policy-based -bsed posterior sampling method that can achieve the best total regret bound ((TVT//S3) in finite-horizon stochastic MDPs. This algorithm provides new way to trade-off between exploration and exploitation by sampling from the posterior distributions of policy. The posterior policy can be updated to balance between the long-term policy and the current greedy policy. Our study shows that this posterior sampling method outperforms other optimization algorithms both theoretically and empirically.
Despite that the sampling method is known to be efficient in discrete environments, our work shows that it could be further improved with count functions and reward re-weighting for posterior updates. However, it remains unknown in this work if similar ideas are applicable to continuous environments as well, which we leave to our future work. For example, we may use some metric accommodate the difference between states of a continuous space, and then apply our algorithm to such environments.
REFERENCES
Yasin Abbasi Yadkori, Peter L Bartlett, Varun Kanade, Yevgeny Seldin, and Csaba Szepesvari. Online learning in markov decision processes with adversarially chosen transition probabil- ity distributions. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Wein- berger (eds.). Advances in Neural Information Processing Systems, volume 26. Curran Asso- ciates, Inc., 2013. URL https: / http::///ooceeeeeeeeeeee neurips wwtppppp...pppppeeeeee// httpippp...c/ppppe//////////
Alekh Agarwal, Sham Kakade, and Lin F Yang. Model- reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory, pp. 67-83. PMLR, 2020.
Priyank Agrawal, Jinglin Chen, and Nan Jiang. Improved worst-case regret bounds for randomized least-squares value iteration. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 35, pp. 6566 006666653,20 2021.
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pp. 39-1. JMLR Workshop and Conference Proceedings, 2012.
Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sampling. In Artificial intelligence and statisties, pp. 99-1 PMLR, 2013.

---

Under review as a conference paper at ICLR 2023
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Advances in Neural Information Processing Systems, 30, 2017.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for re- inforcement learning. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou (eds.), Advances in Neural Information Processing Systems, volume 21. Curran Asso- ciates, Inc., 2008. URL htttps://proceeedingg c/eerp/pp..c/pppprr/////////11 http:://ppoooooonn..eeeeeeeeee/p
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. Advances in neural information processing systems, 29, 2016.
Hippolyte Bourel, Odalric-Ambrym Maillard, and Mohammad Sadegh Talebi. Tightening exploration in upper confidence reinforcement learning. Proceedings of the 37th International Conference on Machine Learning, ICML'20. JMLR.org. 2020.
Ronen I. Brafmmn and Moshe Tennenholtz. R-max general polynomial time algorithm for near-optimal reinforcement learning. J. Mach. Learn. Res., 31ml1):213-2311, mar 2003. ISSN 1532-4435. doi: 10.1 10.166//1522433376666333
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexci A Efros. Large-scale study of curiosity-driven learning. arXiv preprint arXiv: /808. 04355, 2018.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. Advances in neural information processing systems, 01-2249-22577 2011.
Qin Ding, Cho-Jui Hsich, and James Sharpnack. An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling. In International Conference on Artificial Intelligence and Statistics, pp. 1585-1593, PMLR, 2021.
Kefan Dong, Yuanhao Wang. Xiaoyu Chen, and Liwei Wang. Q-learning with ucb exploration is sample efficient for infinite-horizon mdp. ArXiv, 00/11901.09111, 2020.
Yali Du, Lei Han, Meng Fang, Ji Liu, Tianhong Dai, and Dacheng Tao. Liir: Learning individual
intrinsic reward in multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite markov decision processes. In UAI, volume 4, pp. 162-169, 2004.
Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Near optimal exploration-exxloitation in non- communicating markov decision processes. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018a. URL httpt:ttt///tc httppsss//pproccediiiiiit ings neur ps cc/ 5267 7077777abb33660002ee62 Pawp:e/eeeeeeee-eeeeaeeeee
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-span-consttraieed in reinforcement learning. In International Conference on Machine Learning, pp. 1578-1586. PMLR, 2018b.
Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Improved analysis of ucr12 with empirical bernstein inequality, 2020. URL htt.:ttpp//ax....oo////aaee 2045
Aditya Gopalan and Shie Mannor. Thompson sampling for learning parameterized markov decision processes. In Conference Learning Theory, pp. 861-898. PMLR, 2015.
James K Hartman. Epsilon- optimality for global optimization algorithm. Epsilon, pp. 12, 1975.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably effi- cient? In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Biaan -ianchi, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Asso- ciates, Inc., 2018 URL httpttt//prccceediiiiim nwwrips http:///w....aaaeo.cocc///////// 333
pdf
10

---

Under review as a conference paper at ICLR 2023
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang. and Michal Valko. Ucb momentum q learning: Correcting the bias without forgetting. In International Conference on Machine Learning. pp. 7609-7618. PMLR, 2021.
Ahmadreza Moradipari, Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Safe linear thompson sampling. arXiv preprini arXiv: 19111.1011666 2019.
Andrew Y Ng. Daishi Harada, and Stuart Russell. Policy invariance under reward transformations:
Theory and application reward shaping. In Ieml, volume 99, pp. 278-287, 1999.
Min-hwan Oh and Garud Iyengar. Thompson sampling for multinomial logit contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International conference on machine learning, pp. 2701-2710. PMLR, 2017.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. arXiv preprint arXiv::3000 1.06. 0940, 2013.
Ian Osband, Benjamin Van Roy, Daniel J Russo, Zheng Wen, et al. Deep exploration via randomized value functions. J. Mach. Learn, Res., 20(124):1-66 62, 2019.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221-11433 2014.
Alexander Strehl and Michael Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 14:1339-133,, 12 2008. doi: 10.10166fjcss.2007.08000
Alexander L. Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L. Littman. Pac model- free reinforcement learning. In Proceedings the 23rd International Conference Machine Learning, ICML, '06, pp. 881-888, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595933832 doi: 10. 143844. 1143954..114955... 143955. htLtt:s::://de
N0.1145/114344411100
Istvan Szita and András Lörinez. Optimistic initialization and greediness lead polynomial time learning in factored mdps. volume 382, pp. 126, 06 2009, doi: 10.1145/1553334.15555000
Mohammad Sadegh Talebi and Odalric-Ambrym Maillard. Variance-aware regret bounds for undis- counted reinforcement learning in mdps. In ALT, 2018.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAI Xi Chen, Yan Duan, John Schulman, Filip DeTurck, and Pieter Abbeel. Exploration: A study of count- based exploration for deep reinforcement learning. Advances in neural information processing systems, 30, 2017.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-294 1933.
Michel Tokic. Adaptive e-greedy exploration in reinforcement learning based on value differences.
In Annual Conference on Artificial Intelligence, pp. 203-210. Springer, 2010.
J. Wal, van der. Successive approximation for average reward Markov games. Memorandum COSOR. Technische Hogeschool Eindhoven, 1977.
Chen-Yu Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Online reinforcement learning in stochastic games. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL 36e 23ee:99eee1222243333335255222222
newrips http://g.......oc..////////////. .ddf

---

Under review as a conference paper at ICLR 2023
Chen- Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free reinforcement learning in infinite-horizon average-rewars markov decision processes. In International conference machine learning, pp. 10170-10180. PMLR, 2020.
Ziping Xu and Ambuj Tewari. Reinforcement learning in factored mdps: Oracle-efficient algorithms and tighter regret bounds for the non-episodic setting. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 18226-18236. Curran Associates, Inc., 2020. URL /tLLtttps//prrrceeinnng..ss neurips CC/ httppppprr2222//1ee///eee
Fb029644a (2202222466423312222222222-82--2
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. ArXiv, abs/2010.00827, 10 102
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Systems, 2020-December, 2020a. ISSN 1049-5258.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference-advantage decomposition. Advances in Neural Information Processing Systems, 33: 15198-15207, 2020b.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference Learning Theory, pp- 4528 4531. PMLR, 2021
Zihan Zhang, Xiangyang Ji, and Simon Shaolei Du. Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In COLT, 2021c
Zihan Zhang, Xiangyang Ji, and Simon Du Horizon-free reinforcement learning in polynomial time: the power of stationary policies. In Conference on Learning Theory, pp. 3858-3904. PMLR, 2022.
12

---

Under review as a conference paper at ICLR 2023
A DETAILS OF PROOFS
The appendix aims to introduce the complete proof the previous lemmas and theorems.
A. THE CONVERGENCE OF
Lemma A.1. Under update algoritium RWPI, the average reward should be monotonically increased.
Proof. From Algorithm 2, we could deduce the update rule of the average reward:
Jz. (0) J (0) = (W, 1- (0) + (1 - W,) (s, = (1 (.) (s, () (0))
(11)
When J=- (8, (8, - (0), we could deduce that log J,,- (s,0) S 1. So the posterior weight W is
(0)
less than This result holds vice versa. The first term W, < 0 when (=, S J J (0). Therefore, we could prove that:
(0) Jr, (0) = -1- (J) Jr, (0)) 2 0.
(12)
The sequence JR (0) is monotonically increased with time step
Lemma A.2. Suppose Assumption I and Assumption 2 hold for some stochastic MDP M. Let us be the state value in iteration Define N as the maximum iteration number of the algorithm. Then Ttp is e-optimal after N iterations.
Proof. Define min, (1++1(1) and max, ( Then we could deduce:
D+ S UN+1
WHIN + (1 ())=((s00)
(13)
S WiHN + (1 - WG)(NN + 0uN)
Since 0 < W, 1, the upper equation could be turned to:
D (1 W.) (0).
(14)
Based on the definition in Preliminaries, let x* be the optimal policy under all states that satisfies n = E.es n. (s, 0). Then
D (1 W. (0) S (1 W.) (0).
(15)
In a similar way, we could also prove U 2 (1 W.)J (0). From the definition of the stopping criterion of the Policy Iteration algorithm, we could assume - D s (1 w,)e. Therefore, we have
US (1 W.)
5 (11 - Wr)Ja, (0) + (1 Wa)e
< <1 (.) +c)
(16)
(1 W.JJ I (1 - W.)(J,, +
J, v (0) +
We could deduce that stationary policy π is e-optimal after N iterations.
A.2 REGRET BOUND ANALYSIS
Lemma A.3.
Jr. (0) log Jz. (8)
<
Proof. First, could multiply Jx, (0) in order to construct the inequality. Let Jn, (0)
=)
lim e" In(+1) n +o0
lim
+ n
R- +000
(17)
In (=(1-g)
aim
13

---

Under review as a conference paper at ICLR 2023
Apply the L'Hopital's Rule:
lim
(1+ )
n
lin +000
(18)
lm 11 6
Then, we could prove that (1 + n is monotonically increased with n::
(1 + = 3 1.
11+ n2
(1+
1 1+ x
n
n
(1 + n
(1+ +
n+t
n ++1
1 n(1 + 1 n+
(19)
n + 1
n+1
(n + 1)
x m++
S
The first inequality holds for the arithmetic mean equality. We could deduce that (1 + 4) S 6". Therefore, we have:
Jn, (0) Ja. (0)
Jz. Se.
(20)
Based on the definition r, we could deduce the upper bound of average reward. Then the lemma could be proved.
Lemma A.4. Under Assumption 3, for each stationary near-optimal policy a and epoch counter 2 Let p(x) satisfies p(x) == O( (VVoo(((ooggoo /log(lo(())), The following upper bound holds for negative log-density.
-log (T) (ps(( kn tt..
Proof. When W,, I 1, we could have:
Jn. (0)
W (0) exp Σ (N*(),, m) log Js. (0)
(21)
8,81.82
Based on the definition of the counter H. we could deduce the value of the posterior weight in single epoch:
[T(()) = = (S,, = (21, (((())) - k} log (0)
Wr, (0) = exp
Σ
Jr, (0)
1=1
T
{ Te(i) = =T, (St. = (s1, 82)) log Jz, (0) Jn. (0)
Σ
Σ
Σ
= exp
(22)
NEl ($), t=1
Te(t) RT, (St, S. (81, $2)
Jn. (0)
exp
(t)
Σ
log
Nx
Jr. (0)
(81182) ES2
Where (t) := ΣE E Te(()) = π.
represents the total number the time instants during the period of when policy conducted.
14

---

Under review as a conference paper at ICLR 2023
When Assumption 3 holds, we could know that (t) (o,)). where (k
Ek=o Evem (T())) = holds for the number of the epochs where policy chosen(The notation of 7 will be represented as Nx (k) = kr (.. = ke) Therefore, we could have:
log Wa,,(T (TT)
1 Te(t) = n, (Sc. S1+1) = (s1, 82) log (.) (0) (t)
-N)
Σ
J=. (0)
($1))2)ES2 1=0
Juc (0)
Σ
ke kn (0), (Tee 1T) log J=. (0)
(51,
J0) J (0)
T 0(11|8)) log Jr. (0) J (0)
Σ
[ieek oo))))) (Fee T) Te On (81)82) log
+
Σ
(#1,22)E82
(#1,2))682
(23)
The last equation is based on the logarithmic property log E = -log B 4.
Based on the Assumption 3,
define p(x) ((o/o((log())))
(0)
Jx. (0)
log (x)
Σ
p(ka) (ea)Vk, le log (0)
k Torik
Σ
(2)))2) log
Jr. (24)
(81102)E82
( Ke + k
Lemma A.S. The difference between the local optimal average reward and the instantaneous average reward could be bounded by:
- Jn.l S Õ
Proof. We could know that the current policy probability distribution is updated based on the previous
distribution and the current local optimal policy distribution:
(x( W, ( + (1 (s,
(25)
We could extend this result to reward function:
Jx. WiJa,
W.) J" (0:)
+ (1-,1,-) J + 2W, (1 W.) J I W.2 + (1-W,, y²2 + 2W, (1 J"J= The inequality is based on the monotonicity of the algorithm. We could simplify Equation 26
J 81
(26)
(1-W?) 22 s (1- 2 S² + +2W W.) J"
+ (1+ S2 s - ( + +WW,J" Jm.
J3. WiJh < J -W,J* +2W,J' Jr.
(27)
W, (J2 + j j - +2W,J" Jx:
1 (J²-J2) - J2. + 2J.
J2 + J <
W.
Based the definition of the regret of each time step, could deduce the bound of the instantancous regret:
(Jat - J²)² J2 + J²² 2*
1
(J²² - -2, + Jr. - -2J,
<
We
1
(J²² - -J2]
(28)
We
1
(J" - -Ja.) (J* + Jz.).
W,
15

---

Under review as a conference paper at ICLR 2023
Therefore, could deduce that:
1 JT. - J - We
Jx. + J.I
(29)
From Lemma A.4 we could know that - log W,, (TT) is bounded by B, with B = k Jk,) Therefore, we could construct the following inequalities.
W - 2 log Wta 2 -
1
(30)
W
B
Factor B is proportional parameter k which could be bounded by the total number of episode of under total time T. Therefore, we could bound Wi by T(gnoring the constants):
1
W. S - (p(k) Ven + Farte
(31)
S VVTV--V VT
Based the definition of r, the average reward function is bounded by P. So the difference between the local optimal average reward and the instantaneous average reward could bounded by:
| Jm
J
1
J
Jacl
W.
(32)
1- (ps))( hi + k Fen
2r
$ 2
52 S
Lemma A.6.
r
DVSA
S2
when [S| 2 or |A| 22
We could know that is defined as the upper bound of the average reward. So we could deduct:
Proof.
I 2 Jr. (0.)
D 2 max T (0..)
(33)
r S max T (0.) S max T (0x,) S D.
Assuming Lemma A.6 is established, we could get:
r D
$ S < DVSA
D VSA
(34)
8/ 1.
Therefore the Lemma could be proved when the IMDP process has more than one state and one action.
Theorem A.7. The first part of the regret in time step T is bounded by:
Regt < 0 VT
$2
16

---

Under review as a conference paper at ICLR 2023
Proof. From the definition before, could know that Regt could be represented as:
T
Regi = Tm (0x)
Σ Jz. (0x).
(35)
Since this theorem won't it involve the transformation of the transition probability, So let (+) Jn Based on the update rule of the posterior distribution (*+1(()) of policy m. We could divide the average reward into several parts: At time step = T, we could assume the instantancous regret equals to zero:
Regh,
JmN Jxr
(36)
At time step - 1, define the local optimal average reward as J Note that this local optimal value is virtual. The instantaneous regret could be represented as:
Regl,
Juc JKT-1
Wi-1Jam-1 (1 (1-W1, W JaT-1
(37)
(W,-1 -1)-sT-1 (1- W1-1)
-1- J
In similar fashion, at time step T 2, the instantaneous regret could be represented as:
Reghy 2 = JTC Jrr-2
= Jnc - Jrr + J Jxr
(38)
=1 Wi-1)(1 Jzr-1) + (1--W
Jrr-1)-
Based on Lemma A.5 the difference between the local optimal value and the current average reward could be bounded by:
J= - Jn,1 Ó T
(39)
The sub-optimal models sampled when their posterior probability is larger than 7. This ensures the time complexity of the Thompson sampling process is no more than O(1). So we could deduce the total regret in time step T.
1
Regt
T (Regt + Regir +.. Reg
2r
< (
-
(40)
52
T
T
2T
52
In order to deduce the second regret bound generated by the transition probability, we should analyze our algorithm's performance over T time step. We define the number of macro episodes M ltt, < T}. An episode is defined as the set of the time steps under stopping criterions. Therefore, we could deduce the bound of the number of episode.
Lemma A.8. Under the stopping criterion, the number of episodes M could be bounded by:
M SA logg(T)).
Wei et al. 2017
Proof. The stopping criterion triggered whenever the visits number of the initial state-action pair doubled. So M could be represented
M(s.)) {k- < Kr No, (s, 2Nr, 28,,-(8s,a)
(41)
17

---

Under review as a conference paper at ICLR 2023
Since the number of the visit state-action pair (s, a) is doubled at the beginning of every epoch k. The size of M(a.a) should be no larger than O(log(T)). Assume [Mssaa 2 log (8,+1(s,a) 1. We could have:
Nexy (8,0)
II
No.. (s,
1 Kr.Nii (s,0)21
II
2
(42)
(EM (2,022
2 N
This contradicts the fact that Ne (s.a) a) S (s, a). This leads to (Mss.)) I log (Nr+11ss,)) Therefore, could obtain the bound of the number of the episodes:
M 1
Σ
(s.a)
< 1 + Σ
log (Nr+118,0))
(s.a)
(43)
< + SA log
Σ
(r,1(S,
(s.0)
1 + SA loglTT//SS (SA)..
Since the logarithmic function is concave, we could simplify the inequality to:
M < SAlog(T)).
(44)
Lemma A.9. The total number of episodes of total time step T could be bounded by:
KT S (/SATlog(T))
Wei et al. 2017
Proof. Define macro episodes with start times bn, 1,2,, where Ins = w, we could have bmtt1 min {4x > bn No, (s) > 2N,
Let T; - Tg be the length of the ith episode. Therefore, within the ith macro episode,
Ty = Tx-1 + for all h = ni, ns + ... M441 2.
B++1-1
T; =
Σ Tk
k=
D++1 B41--111
Σ
(Tn-1++5) +T
Tma--1
(45)
me -11-m-11
2
Σ
(j+1)+1= 0.5 (1 n.) (n:41 - n; + 1
Consequentlym4411 n, S 2T, for all i 1,,.. M. From this property, could obtain:
M
M
Kr nM+1 - 1 1= Σ (ne41 n <
27.
(46)
Based on Equation and Σ M T, T. could get:
Di=1
Ky < Σ
V 2T.
M M
27,
V2MT.
(47)
t=1
18

---

Under review as a conference paper at ICLR 2023
Where the second inequality is based Sauchy-Schwarz inequality. From Lemma A.8 could know that the number of the macro episodes until time bounded by M I SAlog TT. Therefore, the lemma could be proved.
Theorem A.10. The regrel caused by transition matrix sampling could be bounded by:
Regî S Ō(D(2SAT)))
Proof. In this theorem, we mainly focus on the difference between transition probability. From the previous definition of the Bellman iterator of the average reward, we could have:
J(Ok) + b(Ok N. r(s, x + Σ OK (s' (0x,))
(48)
(0.) + 6 (0,, n,, r(s, (T Σ 0,
The difference between the average reward under near-optimal transition probability and instantaneous transition probability could be represented as:
J(Ok) J (0x) = b (6,, π) b(0x, π)
+ Σ (Ox (s' bb, 02 (s' b T &T)
(49)
We could bound the first term with the largest difference between each state:
0 b(0k. ग. 8) b (0,, ,) S sp(b(0) D
(50)
0 2 (0,, π,, s) - b(0k, 2 - D.
Based on Equation 50 we could bound the second term in a similar way:
0x (8') 8, () b (0x; n,, nT,', 8') Oz. (8/ 8, x) (0., 8²)
(51)
s Σ (5 s) - Oe (s' s, s,
Then, we define the total transition difference as:
0,(s'ss, TT) 0c(5' ss = (s'ss,s, - 0c (ss'(s,
0g (s'(ss, TT (s'ss,, (,, T) 0x (s' T) 0 x) 0x-1
(5'''18 TT).
(52)
From Equation 52 we could deduct the one-step transition difference to be:
(,(''ss, Rt) 0.- 0 0 (s' π) + H (N=(k), m)) 00-1(8118,
(53)
N₂
Based on Assumption 3, we could bound the one-step transition difference:
0z-1
H
Σ 00-1)
Σ
00-1
N
81,92
0
+ Ho
Σ 0-11
N
(54)
O
+
H
TTT
(01-))(0111
N
$1.52
0-1
H H
-
N
81.82
19

---

Under review as a conference paper at ICLR 2023
where
1 + Hs H5i.2 (a Σ
(55)
N
N
When we use stationary policy и in epoch k, we could know that the count function of the policy should be less or equal to the total number of epochs. Therefore, we could deduct that:
01-1 +
(sg,s((ke)) N
H. (2
Σ $1,62
(56)
N
Based Assumption 3, could deduct the bound for Es, ,0 (0l 02-1):
Σ - (0.-01-1) S El log (e2 log $1.42
(57)
k
Combining Equation 57 with Equation 52 Since the update of the transition matrix only happens in each epoch, could deduct the difference between the periodic transition matrix and instantaneous transition matrix based on A.9
el log (E2 log k)
Ox (s' 18, 01 (6') 8) S Ky
k
I kei log (e2 log k)
(58)
2SAT log Tei log (e2 log k).
Therefore, we could combine Equation 58 with Equation 51
T Σ J ( S DV 2SAT Tog log (e2 log k)
Σ J(Ok)
(59)
s 5DDV V2SAT).
20


Reviews:
[{"review_id": "R_HxAWlsJwe", "reviewer": "Reviewer_craj", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a sampling-based policy search for MDPs. The algorithm uses Thompson sampling over policies rather than over individual actions within policies. The algorithm is empirically evaluated and theoretically analyzed. ", "summary_of_the_review": "The paper may contain interesting ideas, however significant work is required to make it ready for publication.", "strength_and_weaknesses": "Strengths: the paper contains both theoretical analysis and empirical evaluation of the proposed algorithm. \n\nWeaknesses: the paper requires significant proofreading to be followed. There are many typos and inconsistencies, and settings, assumptions,  and algorithm descriptions are unclear. The empirical evaluation results are hard to interpret, and will be problematic to reproduce as there was no code or data provided. Citations are rather random.\n\nExamples: $\\Gamma$ appears on page 2, not counting the abstract, but is only defined on page 3. Citation for 'online reinforcement learning' on page 1, first line of introduction, points to an article on a specific application of online RL, not particularly relevant to what follows. 3.1, problem setting, defines finite MDP and then refers to  'episodes' and 'epochs', which are not defined, and are used in a confusing way. Why the total reward of an episode should be in [0, 1]? How is this related to the reward function r to be SxA -> [0, 1]? In Assumption 3.3, it is not clear what do $e_1$ and $e_2$ correspond to, and this is not defined. In Algorithm 1, \"game environment\" suddenly pops up, without having been defined anywhere earlier. And so on, so forth.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QFgKv6CmQ7_", "reviewer": "Reviewer_RWGK", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies reinforcement learning theory in the average-reward MDP setting. The main result is a $\\tilde{O}(D\\sqrt{SAT})$ regret bound for a new algorithm that performs posterior sampling over policies. ", "summary_of_the_review": "This paper studies a topic that received wide attention in recent years (online RL in average-reward MDPs). However, the paper seems quite lacking in awareness of recent work, and has many issues in basic definitions and the clarity of the setups, which makes its contributions questionable in my opinion. ", "strength_and_weaknesses": "While I acknowledge that both average-reward MDPs, as well as the posterior sampling type algorithms themselves are interesting objects in RL theory, I think overall I am highly concerned about the contribution of this paper, due to its lack of awareness of existing work, as well as the many clarity / consistency issues within the basic definitions and settings.\n\n* For high-level comparisons of existing work, first of all, I think the authors did not make clear that they are restricting to the average-reward MDP setting, which is strange—There are at least two equally popular models, discounted MDPs, and finite-horizon MDPs, that are extremely well-studied in terms of online RL in the tabular case, but almost not mentioned at all in related work. With the exception of mentioning Jin et al. (2018) and Zhang et al. (2020), which the authors claim “have not achieved the state-of-art regret bound”. However, Jin et al.’s result is only one H (horizon) factor from optimal regret, and this was closed by Zhang et al. (2020)’s algorithm which achieves the minimax regret $\\sqrt{H^3SAT}$ in the finite-horizon setting. \n\n* For the regret bound, I think the current best result for average-reward MDPs is already $\\sqrt{DSAT}$, for example, achieved by the work of Zhang and Ji (2019, Corollary 1). Thus the claim of the established $D\\sqrt{SAT}$ result “matching the current best regret bound” sounds questionable.  \n[Reference] Zhang, Zihan, and Xiangyang Ji. \"Regret minimization for reinforcement learning by evaluating the optimal bias function.\" Advances in Neural Information Processing Systems 32 (2019).\n\n* Many basic definitions seem non-standard and inconsistent throughout the paper. For example, the definition (2) of regret does not look like the standard definition for RL (it maximizes over a single action $a$ instead of policies). Eq (2) also disagrees with the later appearance of Regret in Eq (10). Neither agrees with the standard definition of regret, which measures the difference against the optimal average reward (e.g. Zhang and Ji, Page 3). \n\n* The authors define $\\theta_{t_k}$ as the “transition probability” of the “model-based agents” within time-step $k$ and epoch $t$ (Section 3.1), whereas $\\theta_\\star$ is the true transition probability. What is the “transition probability of model-based agents”? Do the authors mean some estimate maintained within the algorithm?\n\n* Assumption 3.1, why is “$\\epsilon$-optimal policy” measured on this (estimated) $\\theta_{t_k}$? I think the standard definition is to measure the deployed policy versus the optimal policy on the ground truth model $\\theta_\\star$?\n\nOverall, because of these concerns, I am quite concerned about the contributions even before getting into the actual algorithms / analyses.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Pdkvn3F3Le", "reviewer": "Reviewer_j9Gs", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces a new posterior sampling algorithm (RWPSP) for the horizon-free finite state tabular MDP setting in RL. The algorithm is part of the posterior sampling family of approaches (e.g. a la Thompson sampling), but differentiates itself from past results by:\n- not attempting to sample an estimate the transition model and optimize a policy out of that\n- but instead building directly a posterior on policies based on an estimate transition model, and then sample a policy out of that\n\nThis different approach results in a different regret bound of O(\\Gamma T^1/2 S^-2) which the authors show is always smaller or equal than the current best bounds of O(D(SAT)^1/2).\n\nFinally, preliminary results on toy MDPs are provided to highlight the improved performance in terms of regret of the proposed method.", "summary_of_the_review": "Overall I feel the paper introduces a nice idea (side-stepping the problem of estimating and sampling the transition model), but I could not understand from the theoretical derivation how this change unlocks new solutions in the regret analysis. Due to this lack of clarity and confusion in the soundness of the result I would not reccomend acceptance for the paper in its current state.\n\nHowever, despite having a background in theoretical RL, I also recognize that the field is extremely specialized and I might be missing necessary context and conventions given for granted in the proof derivation, and remain open to re-evaluate my position if the authors can clarify their work.", "strength_and_weaknesses": "The main strength of the method are matching (and potentially improving) the current best rates for this setting, the novelty of the approach to the posterior sampling family, and the seemingly complete lack of propabilistic statements in the regret proof.\n\nThe weaknesses are:\n- The claim of optimality of O(D(SAT)^1/2) regret only holds for posterior sampling approaches (the paper \"Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function\" Zihan Zhang, Xiangyang Ji, NeurIPS2019 seems to report a O((DSAT)^1/2) bound under comparable assumptions). I am not sure if since 2019 no other posterior sampling approach also matched this bound.\n- Could the authors clarify the proof of lemma 5.8? From Lemma A.6 in the appendix we have equation (33) proving \\Gamma \\leq D by application of Assumption 3.2. At this point further bounding D with DS^2(SA)^1/2 seems pointless. A finite MDP cannot have less than 1 state, so a direct application of \\Gamma \\leq D would yield a O(DT^1/2/S^2) regret, much better than existing results.\n- Lemma A.6 seems to rely on Assumption 3.2 heavily. However I do not see why it would be natural to assume that the optimal policy would reduce the diameter between *any two states* in the MDP compared to any of the policies encountered during optimization. In particular the MDP reward (and therefore the optimal policy) does not usually care about arbitrary transition times, but only about transitioning to a good state as quickly as possible. On the other hand a sub-optimal policy might be well aligned (due to sheer randomness) with the explorative goal of tansversing the whole space as efficiently as possible.\n- Assumption 3.2 does not define what would the max be over.\n- I am not fully familiar with the setting, but the complete lack of any probabilistic statement in any of the results (i.e. none of the theorem hold only with some probability, and the regret bounds seem to rely only on the assumptions). The only statistical comment is a brief reference in section 5.2. This seems very unlikely to be rigorous considering posterior sampling is a randomized algorithm. If this was indeed the case it would be a significant aspect of the contribution and should be highlighted in the text.\n- The exposition of the whole paper is well structured, but clarity falls apart at a more careful inspection. Most of the maxes are missing the variable that are being maxed on. Section 3.1 contains broken phrases, including crucially the one that introduces \\theta. p_\\theta is never introduced. the span is mentioned once and never again. Lemma 5.3 uses a different notation in the main paper and in the appendix. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8B48h8gD5K", "reviewer": "Reviewer_5tze", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors consider the regret minimization problem for infinite-horizon average-reward Markov decision process (MDP). They propose the Reward-Weighted Posterior Sampling of Policy (RWPSP) a Thompson sampling inspired algorithm. Precisely  RWPSP maintains a posterior distribution over policies with is updated with the optimal policy of the estimated probability transitions. They prove a regret bound of order O(\\Gamma \\sqrt(T)/S^2) where \\Gamma /S^2\\leq D\\sqrt{SA} where T is the horizon, S the number of states, A the number of actions and D the diameter of the MDP. They experimentally show that  RWPSP compares favorably to other baselines.", "summary_of_the_review": "See above", "strength_and_weaknesses": "Weaknesses:\n \n- Presentation ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject