Provably Efficient Algorithm for Nonstationary Low-Rank MDPs
Authors: Yuan Cheng
Jing Yang
Yingbin Liang
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning
Nonstationary Environment
Representation Learning
Policy Optimization
Statistical Complexity
TL;DR: Reinforcement Learning, Nonstationary Environment, Representation Learning, Policy Optimization, Statistical Complexity

Abstract: Reinforcement learning (RL) under changing environment models many real-world applications via nonstationary Markov Decision Processes (MDPs), and hence gains considerable interest. However, theoretical studies on nonstationary MDPs in the literature have mainly focused on tabular and linear (mixture) MDPs, which do not capture the nature of unknown representation in deep RL. In this paper, we make the first effort to investigate nonstationary RL under episodic low-rank MDPs, where both transition kernels and rewards may vary over time, and the low-rank model contains unknown representation in addition to the linear state embedding function. We first propose a parameter-dependent policy optimization algorithm called PORTAL,
and further improve PORTAL to its parameter-free version of Ada-PORTAL, which is able to tune its hyper-parameters adaptively without any prior knowledge of nonstationarity. For both algorithms, we provide upper bounds on the average dynamic suboptimality gap, which show that as long as the nonstationarity is not significantly large, PORTAL and Ada-PORTAL are sample-efficient and can achieve arbitrarily small average dynamic suboptimality gap with polynomial sample complexity.

Provably Efficient Algorithm for Nonstationary Low-Rank MDPs
Yuan Cheng
Jing Yang The Pennsylvania State University
National University of Singapore yuan chengeu. nus edu
edu
Yingbin Liang
The Ohio State University 1 laang. www8888...ccoo. edu
Abstract
Reinforcement learning (RL) under changing environment models many real-world applications via nonstationary Markov Decision Processes (MDPs), and hence gains considerable interest. However, theoretical studies nonstationary MDPs in the literature have mainly focused on tabular and linear (mixture) MDPs, which do not capture the nature of unknown representation in deep RL. In this paper, we make the first effort to investigate nonstationary RL under episodic low-rank MDPs, where both transition kernels and rewards may vary over time, and the low-rank model contains unknown representation in addition to the linear state embedding function. We first propose parameter-dependent policy optimization algorithm called PORTAL. and further improve PORTAL to its parameter- free version of Ada-PORTAL, which is able tune its hyper-parameten adaptively without any prior knowledge of nonstationarity. For both algorithms, we provide upper bounds on the average dynamic suboptimality gap, which show that as long as the nonstationarity is not significantly large, PORTAL and Ada-PORTAL. are sample-efficient and can achieve arbitrarily small average dynamic suboptimality gap with polynomial sample complexity.
Introduction
Reinforcement learning (RL) has gained significant success in real-world applications such as board
games of Go and chess (Silvrr al. 2016 2017 2018), robotics (Levine et al. 2016 Gu et al. (011)) recommendation systems (Zhao et al. (021) and autonomous driving (Bojarski et al. 2016 [M et al.
2021b. Most theoretical studies RL have been focused stationary environment and evaluated the performance an algorithm by comparing against only one best fixed policy (i.e., static regret). However, in practice, the environment is typically marevngying and nonstationary. As a result, the transition dynamics, rewards and consequently the optimal policy change over time.
There has been a line of research studies that investigated nonstationary RI. Specifically, Gajane (008):[Cheung
al. (20T8): Cheung et al. (2020); Mao et al. (202T) studied nonstationary tabular MDPs. To further
overcome the curse of dimensionality. [ei et al. (2020); Zhou et al. (2020) proposed algorithms for nonstationary linear (mixture) MDPs and established upper bounds on the dynamic regret.
In this paper, we significantly advance this line of research by investigating nonstationary RL under low-rank MDPs (Agarwal al., (2220b). where the transition kernel of each MDP admits decomposition into representation function and state-embedding function that map to low dimensional spaces. Compared with linear MDPs where the representation known, the low- rank MDP model contains unknown representation, and is hence much more powerful to capture
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

representation learning that occurs often in deep RL. Although there have been several recent studies
on static low-rank MDPs (Agarwal et al. 2020b Uehara et al. [022]] Modi et al. 202I). nonstationary low-rank MDPs remain unexfored, and are the focus of this paper.
To investigate nonstationary low-rank MDPs, several challenges arise. (a) All previous studies of nonstationary MDPs took on-policy exploration, such a strategy will have difficulty in providing sufficiently accurate model (as well as representation) learning for nonstationary low-rank MDPs. (b) Under low-rank MDPs, since both representation and state-embedding function change over time, it more challenging to use history data collected under previous transition kernels for current use.
The main contribution of this paper lies in addressing above challenges and designing a provably efficient algorithm for nonstationary low-rank MDPs. We summarize contributions follows.
We propose a novel policy optimization algorithm with representation learning called PORTAL for nonstationary low-rank MDPs, PORTAL features new components, including off-policy exploration, data-transfer model learning, and target policy update with periodic restart.
We theoretically characterize the average dynamic suboptimality gap (GapAve) of PORTAL, where GapAve serves as new metric that captures the performance of target policies with respect to the best policies at each instance in the nonstationary MDPs under off-policy exploration. We further show that with prior knowledge on the degree of nonstationarity, PORTAL can select
that minimize GapAve- If the nonstationarity is not sigmificantly large, PORTAL enjoys a diminishing GapAve with respect to the number of iterations K, indicating that PORTAL can achieve arbitrarily small GapAve with polynomial sample complexity.
Our analysis features few new developments. (a) We provide a new MLE guarantee under nonstationary transition kernels that captures errors of using history data collected under different transition kernels for benefiting current model estimation. (b) We establish trajectory-wise uncertainty bound for estimation errors via square-roof ex norm of variation budgets. (c) We develop an error tracking technique via auxiliary anchor representation for convergence analysis.
Finally, we improve PORTAL to a parameter free algorithm called Ada-PORTAL, which does not require prior knowledge on nonstationarity and is able to tune the hyper-parameteers adaptively. We further characterize GapAve of Ada-PORTAL as Ö(K à (A + 1)a), where A captures the variation of the environment. Notably, based on PORTAL, we can also use the black-box method algorithm (called MASTER+PORTAL) with GapAve of Ō(K At)). Clearly, AdR-PORTAL performs better than MASTER+PORTAL when nonstationarity is not significantly small, i.c. A 2 Õ(1).
called MASTER in Wei & Luo (22T) turn PORTAL into a parameter-
To our best knowledge, this is the first study of nonstationary RL under low-rank MDPs.
2 Related Works
Various works have studied nonstationary RL under tabular and linear MDPs, most of which can be divided into two lines: policy optimization methods and value-based methods.
Nonstationary RL: Policy Optimization Methods. As a vast body of existing literature (Cai et al., 2020: (Sanni et al.] 2020 Agarwal et al. 2020aa Xu et al., (221)) has proposed policy optimization methods attaining computational efficiency and sample efficiency simultaneously in stationary RL under various scenarios, only several papers investigated policy optimization algorithm in nonsta- tionary environment. Assuming time-varying rewards and time-invariant transition kernels, Fei et al.) (2020) studied nonstationary RL under tabular MDPs. ZZhong et al. (202T) assumed both transition kernels and rewards change over episodes and studied nonstationary linear mixture MDPs. These policy optimization methods all assumed prior knowledge nonstationarity.
Nonstationary RL: Value-based Methods. Assuming that both transition kernels and rewards are varevngrying, several works have studied nonstationary RL under tabular and linear MDPs, most of which adopted Upper Confidence Bound (UCB) based algrithms. [Cheung et al.) (2020) investigated tabular MDPs with aufinite-horizon and proposed algorithms with both known variation budgets and unknown variation budgets. In addition, this work also proposed a Handit-over-Reinfrreee
Learning (BORL) technique to deal with unknown variation budgets. Mao et al. (2021) proposed a model-free algorithm with sublinear dynamic regret bound. They then proved a lower bound for nonstationary tabular MDPs and showed that their regret bound is near min-max optimal. Touati

---

& Vincent (000)): Zhou et al. (2020) considered nonstationary RL in linear MDPs and proposed algorithms achieving sublinear regret bounds with unknown variation budgets.
Besides these two lines of researches, Wei & Luo (2021) proposed a black-box method that turns RL algorithm with optimal regret in (near- Sstaionata environment into another algorithm that can work in a nonstationary environment with sublinear dynamic regret without prior knowledge on nonstationarity. In this paper, we show that our algorithm Ada-P ada-PORTAL outperforms such a type of black-box method (taking PORTAL as subroutine) if nonstationarity is not significantly small.
Stationary RL under Low-rank MDPs. Low-rank MDPs were first studied by AAgawal al. (2020b) in a reward-free regime, and then Uchara et al. (2022) studied low-rank MDPs for both online and offline RL with known rewards. Cheng al. (2023) studied reward-fiie RL under low-rank MDPs and improved the sample complexity of previous works. Modi et al. (2021) proposed a model-free algorithm MOFFLE under low-nonnegative-nn
MDPs. [Ceeng et al. (2022); [Agarwal et al. 2022) studied multitask representation learning under low-rank MDPs, and further showed the benefit representation learning to downstream RL tasks.
Formulation
Notations: We use [K] to denote set {l,..., .K,....,KJ. for any K E N, use ||ж||, to denote the & norm of vector æ, use (AA to denote the probability simplex over set A,, use (.A) to denote uniform sampling over A, given |A| < oc, and use (SS) to denote the set of all possible density distributions over set S. Furthermore, for any symmetric positive definite matrix E, we let ||>|| = V Ex. For distributions p1 and P2, we use DKL(PI) (pL))))) (IP)()) to denote the KI. divergence between p1 and p2-
3.1 Episodic MDPs and Low-rank Approximation
fru }= where S is possibly infinite state space, A is finite action space with cardinality A, H is the time horizon of each episode, (-
An episodic MDP is denoted by a tuple M == (PA))
x A + A(S) denotes the transition kernel at each step h, and (-.-.)) S A + [0, 1] denotes the deterministic reward function each step h. We further normalize the reward as Ei= Th I 1. A policy т = ( Jee( is a set of mappings where A, (als) denotes the probability of selecting action a at state s step h. For any (s.a) E S x A, let ($), (5) ~ (P, π) denote that the state 8n, is sampled by executing policy ı to step under transition kernel and then action dg, is sampled by (-(s).)).
Th S + (AA). For any (s,a) E
Given any state s E S, the value function for policy at step h under an MDP M is defined as the expected value of the accumulative rewards as: (s, s). Similarly, given any state-action pair (s, S A,
EN=h Be oge and)~~ (P,,)) [sw- anr)ss sa the action- function (Q-function) for a policy æ at step h under an MDP M is defined as QT, (s, = a)) + E I 1 (w)))))))() [Tw (She osr) = s,
a]. Denote IR. Then we can write the action- value function as QR. (s, a) = rn,ss, a) + (Pn 1H+1,,, (s, (s, For any k E [K], without loss of generality, we assume the initial state 81 to be fixed and identical, and we use Vp, to denote (8)) ) for simplicity.
(P,f)(s, == Ex [f (s')] for any function f S -
This paper focuses low-rank MDPs (Jiang al. 2017 Agarwal et al. 2020b) defined follows.
Definition 3.1 (Low-rank MDPs), A transition kernel P% S A - A(S) admits a low-rank decomposition with dimension d N if there exist a representation function Φ : A Rd and a state-embedding function μ : S + Rd such that
P: a) (s, (h)))) Vs,8' ES
Without loss of generality, assume (s, (s, a)l2 $ for all (s, S A and for any function g + [0, 1]. II. [. (s))()))) Vd. An MDP is a low-rank MDP with dimension d if for
any h E [H], its transition kernel PY admits a low-rank decomposition with dimension d. Let o" = [di hrepa and p² (pt)n be the true representation and state-embedding functions.
3

---

3.2 Nonstationary Transition Kernels with Adversarial Rewards
In this paper, we consider an episodic RL setting under changing environment, where both transition kernels and rewards vary over time and possibly in an adversarial fashion.
Specifically, suppose the RL system goes by rounds, where each round have fixed number of episodes, and the transition kernel and the reward remain the same in each round, and can change adversarially across rounds. For each round, say round k, we denote the MDP as M AS Pd == {Pr*") Ik=1, rk = fr(3k=1), where p*, and r denote the true tran- sition kernel and the reward of round k. Further, p*. takes the low-rank decomposition as p*. = (s* ,,===)) Both the representation function σ0* and the state embedding function j** can change across rounds. Given the reward function rd there always exists an optimal policy - that yields the optimal value function , supx Vp. p abbreviated as Ve...e.. Clearly, the optimal policy also changes across rounds.
We assume the agent interacts with the nonstationary environment (i.e., the time-varying MDPs) over K' rounds in total without the knowledge of transition kemelss [ k==1 At the beginning of each round k the environment changes to possibly adversarial transition kernel unknown to the agent, picks a reward function r² which is revealed to the agent only at the end of round k;, and outputs fixed initial state 81 for the agent to start the exploration of the environment for each episode. The agent is allowed to interact with MDPs via a few episodes with one or multiple exploration policies at her choice to take samples from the environment and then should output an target policy to be executed during the next round. Note that in our setting, the agent needs to decide exploration and target policies only based on the information in previous rounds, and hence exploration samples and the reward information of the current round help only towards future rounds.
3.3 Learning Goal and Evaluation Metric
In our setting, the agent seeks to find the optimal policy each round (with only the information of previous rounds), where both transition kernels and rewards can change over rounds. Hence we define the following notion of average dynamic suboptimality gap to measure the convergence of the target policy series to the optimal policy series.
Definition 3.2 (Average Dynamic Suboptimality Gap). For K rounds, and any policy set ( ]ee[K]- the average dynamic suboptimality gap (GapAve) of the value functions over K rounds is given as GapAve () = K E Dk=IVVp.eer - Vp..,,,). For any we say an algorithm is c-average suboptimal, it outputs a policy set (** [=<])<[K]] satisfying Gapave (K) S 6.
GapAve compares the agent's target policy to the optimal policy of each individual round in hindsight, which captures the dynamic nature of the environment. This is in stark contrast to the stationary setting where the comparison policy is a single fixed best policy over all rounds. This notion is similar to dynamic regret used for nonstationary RI. (Fei et al., 2020 Gajane et al.) 2018), where the only difference is that GapAve evaluates the performance of target policies rather than the exploration policies. Hence, given any target accuracy e 2 O, the agent is further interested in the statistical efficiency of the algorithm, i.e., using as few trajectories as possible to achieve e-average suboptimal.
4 Policy Optimization Algorithm and Theoretical Guarantee
4.1 Base Algorithm: PORTAL
We propose novel algorithm called PORTAL (Algorithm D. which features three main steps. Below we first summarize our main design ideas and then explain reasons behind these ideas as we further elaborate main steps of PORTAL.
Summary of New Design Ideas: PORTAL features the following main design ideas beyond previous studies on nonstationary RL under tabular and linear MDPs. (a) PORTAL features a specially designed off-policy exploration which turns out to be beneficial for nonstationary low-rank /MDP models rather than the typical on-policy exploration taken by previous studies of nonstationary tabular and linear MDP models. (b) PORTAL transfers history data collected under various different transition kernels for benefiting the estimation of the current model. (c) PORTAL updates target

---

policies with periodic restart. As comparison, previous work using periodic restart (Fei et al. 2020 chooses the restart period based on certain smooth visitation assumption. Here, we remove such an assumption and hence our choice of 7 is applicable to more general model classes.
Step 1. Off-Policy Exploration for Data Collection: We take off-policy exploration, which is beneficial for nonstationary low-rank MDPs than simply using the target policy for on-policy exploration taken by the previous studies on nonstationary tabular or linear (mixture) MDPs (Zhong et al. 2021 Fei et al. 2020 Zhou et al. 2020). To further explain, we first note that under tabular or linear (mixture) MDPs studied in the previous work, a bonus term is introduced the actual reward to serve as point-wise uncertainty level of the estimation eтror for each state-action pair at any step h, so that for any step h, O is good optimistic estimation for Q t..t,. Hence it suffices to collect samples using the target policy. However, in low-rank MDPs, the bonus term by cannot serve point- wise uncertainty measure. For step h 2 2, Q% is not a good optimistic estimation for the true value function if the agent only uses target policy to collect data (i.e., for on un-poiicy exploration). Hence, more samples and a novel off-policy exploration low-rank MDPs. Specifically, as line 5 in Algorithm at the beginning of each round k, for each step k.A. h E [H] the agent explores the environment by executing the exploration policy =*-1 --1 to state f/-1 and then taking uniformly chosen actions where # is determined in Step of the previous round.
required for good estimation under
Algorithm PORTAL (Policy Optimization with RetronenTAAtion TAtion Learning under nonstationary MDPs)
1: Input: Rounds K, byper-parameters т, W, regularizer A,,w, coefficient äj,W, stepsize 7) and models ( }
2: Initialization: To(+(s) to be uniform; ((u,0) = 0.
3: for episode ho 1, ...... K do
4: for step h = I.... : H do
5: Roll into -h-1 using # uniformly choose 0h- 1h-1: 0n
((,b)
(R (k,b) and enter into 8h 18411
(k.A) (k.b)
6: Update datasets
(.A.W) ((.A) (1.h) ((,A))
- - -= W+1
D( h
(1,1)
(1.h) ((,,))
a sht1 ji=ik--HH
7:
end for
8: Receive full information rewards n* (rrT)eeean
9:
Estimate transition kernel and update the exploration policy ø for the next round via:
U ke (D(....W), (.(D....))
for step h = =.... H do
11:
Update Q): = Q pe end for
12:
13:
i: 1:
mod = then Set (Qh)a=[A) as zero functions and (*)) uniform distributions A.
14:
15:
end if
16:
for step h 1, 1,.... H do
Update the target policy as in Equation 18: end for
17:
19:
end for
20:
Output: {T+1KK Ik=1-
Step 2. Data-Traie Tata--rrnsfee Model Learning and U² In this step, we transfer history data collected under previous different transition kernels for benefiting the estimation of the current model. This is theoretically grounded by our result that the model estimation error can be decomposed into variation
'The subscript in = indicates that the data collected at time step h of each trajectory, and the superscript (k:, h) indicates in which loop the data is collected (as in line 3 and 4 of Algorithm
5

---

budgets plus a diminishing term as the estimation sample size increases, which justifies that the usage of data generated by mismatched distributions within a certain window is beneficial for model learning as long as variation budgets is mild. Then, the estimated model will further facilitate the selection of future exploration policies accurately.
Specifically, the agent selects desirable samples only from the latest W rounds following a forgetting rule (Garivier & Moulines I011). Since nonstationary low-rank MDPs (compared tabular and linear MDPs) also have additional variations on representations over time, the choice of W needs to incorporate such additional information. Then the agent passes these selected samples to subroutine E (see Algorithm2) 2). in which the agent estimates the transition kernels via the maximum likelihood estimation (MLE). Next, the agent updates the empirical covariance matrix Ü= W and exploration- driven bonus 8 as in lines 4 and 5 in Algorithm 2 We then define truncated value function iteratively using the estimated transition kernel and the exploration-driver reward as follows:
07, 80 (Sh, an) min { {1, (,,, an) + Ph VIT 4+1, (sh, an))
v Pe Pe Be (8)) Ex [ (oh, (oh.an)) h.
Although the bonus term b% cannot serve point-wise uncertainty measure, the truncated value function V pe,Be ge as the cumulative version of by can serve as a trajectory-wis uncertainty measure, which can be used to determine future exploration policies. Intuitively, for any policy æ, the model estimation error satisfies (ss.))-(P-.>.>> PK (-1s.a) (* a)]lrv] S Th + A, where the error term A captures the variation of both transition kernels and representations over time. As result, by selecting the policy that maximizes V7 j as the exploration policy as in line 7, the agent will explore the trajectories whose states and actions have not been estimated sufficiently well so far.
Algorithm 2 E (Model Estimation and Exploration Policy Update)
1: Input: round index k; regularizer λ and coefficient Gz,w, datasets (D/ta)) }.(D(, (K())) and models { (V) $).
2: for step h ... H do
3: Learn the representation via MLE for step h:
P
(0 ( arg ΦED,NEV
BBgg. (log(o(sh, ((ss+)))))
4: Compute the empirical covariance matrix as
Σ
dhin, an and (sh;
(sh, an) + dR.
5: Define exploration-driven bonus (:))).) minfax,w 11 Mor 1,13.
6: end for
7: Find exploration policy # arg max V fe, where V pe, defined as Equation pe,Be
8: Output: Model pk and exploration policy {
Step 3: Target Policy Update with Periodic Restart: The agent evaluates the target policy by computing the value function under the target policy and the estimated transition kernel. Then, due to the nonstationarity, the target policy is reset every J rounds. Compared with the previous work using periodic restart (Fei et al.) 2020). whose choice of t is based on a certain smooth visitation assumption, remove such assumption and hence our choice of is applicable to more general model classes. Finally, the agent uses the estimated value function for target policy update for the next round 3: + via online mirror descend. The update step inspired by the previous works (Cai et al., 2020) Schulman et al. 2017). Specifically, for any given policy n² and MDP M, define the tollowing function w.r.t. policy m:
H
Ma (T) = V + Σ Esn
[ ( (A (-1sh) -
hml

---

LMM.n0 (T) can be regarded as a local linear approximation of Vp, at "point" T² Schulman et al.
2017 Consider the following optimization problem:
π x++1 arg max I M. ,8 (TT)
Σ
Bsn--(--At (D [DuL(TA((saII
7 NETH
This can be regarded as a mirror descent step with KI. divergence, where the KI. divergence regu- larizes ıT to be close to n². It further admits a closed-form solution: a (+++) x (+b)) -xp()) 2 Pa (3 We use the estimated version Q to approximate Q Paik and get
T x
(+1-)) exp(n (%.)))).
4.2 Technical Assumptions
Our analysis adopts the following standard assumptions on low-rank MDPs. Assumption 4.1. (Realizability). learning agent can access to model class {(0, V) that contains the true model, namely, for any [H], E [K] oh E 2 U V.
While we assume cardinality of the model class to be finite for simplicity, extensions to infinite classes with bounded statistical complexity are not difficult (Sun et al. 2019).
Assumption 4.2 (Bounded Density). Any model induced by and v has bounded density, i.e. VP (6. pu) Ø O E V there exists constant B 2 0 such that =E P(s'ls, a) S B.
Assumption 4.3 (Reachability). For each round k and step h, the true transition kernel p* h that for any (s,a,s) s') E S x A S, ( 2 Pmin-
satisfies
Variation Budgets: ity of the environment:
We
next
introduce
several
measures of nonstationar-
AP
Σ Σ h= max p+ (+|s, (
ptik ()s, = EK E max (Sa) PM
Ph als.a))l
Ek=LCh A (1ss)lrr These notions are known as variation budgets or path lengths in the literature Th
Eh=1 (ax 11 1 (s,a)-o) 60 12. -E Em=1 max.es || (+|s)-
of online convex optimization (Besbes et al. 2015 Hazan 2016 Hall & Willett 2015) and
nonstationary RL (Fei et al., [020 Zhong et al. 2021] Zhou et al. 2020)) The regret of nonstationary
RL naturally depends on these notions that capture the variations of MDP models over time.
4.3 Theoretical Guarantee
To present our theoretical result for PORTAL, we first discuss technical challenges in our analysis and the novel tools that we develop. Generally, large nonstationarity environment can cause significant errors to MLE, empirical covariance and exploration-driven bonus design for low-rank models. Thus, different from static low-rank MDPs (Agarwal al. 2020b; Uehara et al. 2022) we devise several new techniques in our analysis to capture the errors caused by nonstationarity which we summarize below.
1. Characterizing nonstationary MIE guarantee. We provide a theoretical ground to support our design of leveraging history data collected under various different transition kernels in previous rounds for benefiting the estimation of the current model, which is somewhat surprising. Specifi- cally, we establish an MLE guarantee of the model estimation error, which features separation of variation budgets from a diminishing term as the estimation sample size W increases. Such result justifies the usage of data generated by mismatched distributions within a certain window as long as the variation budgets is mild. Such separation cannot be shown directly. Instead, we bridge the bound of model estimation error and the expected value of the ratio of transition kernels via Hellinger distance, and the latter can be decomposed into the variation budgets and diminishing term as the estimation sample size increases.
2. Establishing trajectory-ve wise uncertainty for estimation error V Vp j To this end, straightforward combination our nonstationary MI.E guarantee with previous techniques on low-rank MDPs would yield coefficient åg,w that depends on local variation budgets. Instead, we convert the
7

---

-norm variation budgets P to square-root foo-n variation budget AVP. In this way, the coefficient no longer depends on the local variation budgets, and the estimation error can be upper bounded by V ja plus an error term only depending on the square-root 6oo -norm variation budgets.
3. Error tracking via auxiliary anchor representation. In proving the convergence of average of V "p..** standard elliptical potential based analysis cannot work, because the representation 6** in the elliptical potential ||Ø** (s, ((s,, )- changes across rounds, where Uh the
population version of Ü.:. To deal with this challenge, in our analysis, divide the total K rounds into blocks with equal length of W rounds. Then for each block, we set an auxiliary anchor representation. We keep track of the elliptical potential functions using the anchor representation within each block, and control the errors by using anchor representation via variation budgets.
The following theorem characterizes theoretical performance for PORTAL. k= set åk.W Ô (VA++ d') and >s.w Odd). Let {T²) ]== be the output of PORTAL in Algorithm For any 5 E (0, 1). with probability at least 5, GapAve () of PORTAL is at most
Theorem 4.4. {M* is set of low-rank MDPs with dimension d. Under Assumptions 4.1 to 4.3
K
Ö
HAPA A d2+ + W
HadA K
(A+ d3 W +
H2W AVP
HT K
+
(IT)
We explain the upper bound Theorem 4.4 as follows. The basic bound as Equation in Theorem 4.4 contains two parts: the first part (4) captures the estimation error for evaluating the target policy under the true environment via the estimated value function Q* in line 16 of Algorithm I Hence, part (7) decreases with K and increases with the nonstationarity of transition kernels and representation functions. Also, part (/) is greatly affected by the window size W, which is determined by the dataset used to estimate the transition kernels. Typically, W is tuned carefully based on the variation of environment. If the environment changes significantly, then the samples far in the past are obsolete and become not very informative for estimating transition kernels. The second part (11) captures the approximation error arising finding the optimal policy via the policy optimization method as in line 8 of Algorithm [ Due to the nonstationarity of the environment, the optimal policy keeps changing across rounds, and hence the nonstationarity of optimal policy A affects the approximation eтror. Similarly to the window size W in part (T), the policy restart period T can also be tuned carefully based on the variation of environment and the optimal policies.
Corollary 4.5. Under the same conditions of Theorem 4.4 if the variation budgets are known, correspondingly ty to achieve optimality. Specially, if the
then we can select the nonstationarity of the environment is moderate, we have
GapAve Õ(H v di A ( ()+
+ +HK LAA +
If the environment is near stationary, then the best W and T are K. The GapAve reduces to O(HH4& + (())k) which matches results of stationary environment (Uehara et al. 2022).
Detailed discussions and proofs of Theorem 4.4 and Corollary 4.5 are provided in Appendices A and B respectively.
Parameter-free Algorithm: Ada-PORTAL
As shown in Theorem 4.4 hyper-parameters W and greatly affect the performance of Algorithm
With prior knowledge of variation budgets, the agent is able to optimize the performance as in Corollary 4.3 However, in practice, variation budgets are unknown to the agent. To deal with this issue, in this section, we present parameter-free algorithm called AORTPOLTAL in Algorithm which is able tune hyper-parameters without knowing the variation budgets beforehand.
Algorithm is inspired by the BORL method (Cheung et al.) 2020). The idea to use Algorithm D subroutine and treat the selection of the hyper- parameerrss such W and bandit problem.

---

Algorithm 3 Ada-PORTAL (Adaptive Policy Optimization RepresenTAAtion TAtion Learning)
1: Input: Confidence level 6, number of episodes K, block length M, feasible set of window size
Tw and policy restart period J-.
2: Initialization: Initialize a, B and {g.1 Nella in Equation 4
3: for block = I..... [K/M] do
4: Update the windows size selection distribution (u(e.D),a((:Eee as in Equation
5: Sample (k;, E J from the updated distribution (u..)), then W; [M Ja
and Ti = -LM+//>>
6: for episode = (i - 1)M + 1,..., min K} do
7: Run PORTAL with W; and T₁.
8: end for
Compute the total reward for block R,WW,, > min (i-iii+)++ Vi. where V is
9:
empirical value functions of target policy x², and update the estimated total reward of running different epoch sizes {q(..),++1 (K.))er according to Equation (6).
10: end for
11:
Output: {T*} TR=1-
Specifically, Ada-PORTAL divides the entire K rounds into [K/M] blocks with equal length of M rounds. Then two sets Tw and J, are specified (see later part of this section), from which the window size W and the restart period for each block are drawn.
For each block i [[ [ Ada-PORTAL treats each element of Jw x Jr an arm and take it as bandit problem to select the best arm for each block. In lines 4 and 5 of Algorithm 3 a master algorithm is run update parameters and select the desired arm, i.e., the window size W; and the restart period 7. Here we choose EXP3-P (Bubeck & Cesa Dasa-Bianchi] 2012) as the master algorithm and discuss the details later. Then Algorithm||] i called with input W; and тı as a subroutine for the current block i. At the end of each block, the total reward of the current block is computed by summing up all the empirical value functions of the target policy of each episode within the block, which is then used to update the parameters for the next block.
We next set the feasible sets and block length of Algorithm I Since optimal W and in PORTAL are chosen differently from previous works (Zhou et al.) [020 Cheung et al., 2019 Touati & Vincent 2020) on nonstationary MDPs due the low-rank structure, the feasible set here that covers the optimal choices of W and should also be set differently from those previous works using BORL.
Mw = d 3 K3,
Mr = K3, M = d3 Hš..
Jw = [log(Mw)], Jw =
(My [M J...., Mw). J. [log( M, M+)J, J, (MP, [MF J...., M+) == Jw J,.
Then the parameters of EXP3-P are intialized as follows:
In
In
JInJ
a N
B B-V
JJK/M/' 7 - [K/M]* 4(.0),1 0, (k,1) E (4)
J[K/M]
where J [(k, k (0.1,....Jww.. llE (0......,J+ The parameter updating rule as follows. For any (k,,) E J.iE
exp(oq(u.).))
2 J
U(k.),+ = (1 (1-7) Σ (ADEE exp(ag(.n.)) +
(5)
where "(a.), is a probability over J. From "( the agent samples a desired pair (k,, 4) for each block i, which corresponds the index of feasible set Tw x J, and is used to set W; and TÜ-
As last step, (W,,, Tz) is rescaled to update q(k.).i+1.
3 ++ (k. R (W.....)
(0.0).+11 = ((k.)),
U(k.)).
We next establish bound GapAve for Ada-PORTAL

---

Theorem 5.1. Under the same conditions of Theorem 4.4 with probability at least 1 - 8, the average dynamic suboptimality gap of Ada-PORRALL Algorithm 3 upper- bounded as Gapave(K) S
Ó( d A (A d A + + +1} + 2HK (A" + +))3).
Comparison with Wei & Luo (202T: It is interesting to compare Ada-PORRIH with an alternative black-box type of approach to see its advantage. A black-box technique called MASTER was proposed in Wei Luo (202T), which can also work with any base algorithm such as PORTAL to handle unknown variation budgets. Such combined approach of MASTER+PORTAL turns out to have worse GapAve than our Ada-PORTAL in Algorithm
3 To see this, denote A = A + AVP + A². The GapAve of PASTER+PORTAL is Ö(K $ A Then if variation budgets are not too small, i.e. A 2 O(1), this GapAve is worse than Ada- PORTAL See detailed discussion in Appendix C.2
Conclusion
In the paper, investigate nonstationary RL under low-rank MDPs. We first propose a notion of average dynamic suboptimality gap GapAve to evaluate the performance of a series of policies in nonstationary environment. Then we propose a sample-efficient policy optimization algorithm PORTAL and its parameter-free version Ada-PORTAL. We further provide upper bounds on GapAve for both algorithms. As future work, it is interesting investigate the impact of various constraints such as safety requirements in nonstationary RL under function approximations.
7
Acknowledgement
The work of Y. Liang was supported in part by the U.S. National Science Foundation under the grants RINGS-2148253, DMS-2134145 and ECCS-21 13660. The work of J. Yang was supported by the U.S. National Science Foundation under the grants CNS-1956276 and CNS-2003131.
References
Agarwal, A., Henaff, M., Kakade, S. M., and Sun, W. PC-PG: policy cover directed exploration for provable policy gradient learning. In Advances in Neural Information Processing Systems 33, 2020a.
Agarwal, A., Kakade, S. M., Krishnamurthy, A., and Sun, W. FLAMBE: structural complexity and representation learning of low rank mdps. In Advances in Neural Information Processing Systems 33, 2020b.
Agarwal, A., Song, Y., Sun, W., Wang. K., Wang, M., and Zhang, X. Provable benefits of representa- tional transfer in reinforcement learning, arXiv preprint arXiv:2205.14577, 2022.
Besbes, O., Gur, Y., and Zeevi, A. Non-stationary stochastic optimization. Oper. Res., 63(5): 1227-1244, 2015.
Bojarski, M., Del Testa, D., Dworakowski, D., Firner, B., Flepp. B., Goyal, P., Jackel, L. D., Monfort, M., Muller, U., Zhang, J., al. End to end learning for self-driving cars. arXiv preprint arXiv:1604.07316 2016.
Bubeck, S. and Cesa-Bias Bianchi, N. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Found. Trends Mach. Learn., 2012.
Cai, Q., Yang. Z., Jin, C., and Wang, Z. Provably efficient exploration in policy optimization. In Proceedings of the 37th International Conference on Machine Learning, 2020.
Cheng, Y., Feng. S., Yang, J., Zhang, H., and Liang, Y. Provable benefit of multitask representation learning in reinforcement learning. In Advances in Neural Information Processing Systems, 2022.
Cheng, Y., Huang, R., Yang, J., and Liang, Improved sample complexity for reward-free reinforce- ment learning under low-rank mdps. arXiv preprint arXiv:2303. 2023.
10

---

Cheung, W. C.C Simchi-Levi, D., and Zhu, R. Learning to optimize under non-stationarity. In The 22nd International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 1079-1087. PMLR, 2019.
Cheung. W. C., Simehi-Levi, D., and Zhu, R. Reinforcement leaming for non-stationary markov decision processes: The blessing of (more) optimism. In Proceedings of the 37th International Conference Machine Learning, 2020.
Dann, C., Lattimore, T., and Brunskill, E. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems 30, 2017.
Fei, Y., Yang, Z., Wang, Z., and Xie, Q. Dynamic regret of policy optimization in non-stationary environments. In Advances in Neural Information Processing Systems 33, 2020.
Gajane, P., Ortner, R., and Auer, P. A sliding-window algorithm for markov decision processes with arbitrarily changing rewards and transitions. CoRR, abs/1 10066, 2018.
Garivier, A. and Moulines, On upper-confidence bound policies for switching bandit problems. In International Conference Algorithmic Learning Theory, 2011.
Gu, S., Holly, E., Lillicrap, T., and Levine, S. Deep reinforcement learning for robotic manipula- tion with asynchronous off-policy updates. In IEEE international conference on robotics and automation, 2017.
Hall, E. C. and Willett, R. M. Online convex optimization in dynamic environments. IEEE J. Sel. Top. Signal Process., 94)):447-662 2015.
Hazan, E. Introduction to online convex optimization. Found. Trends Optim., 2(3-4):157-325, 2016.
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, 2017.
Levine, S., Finn, C., Darrell, T., and Abbeel, End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 17(1):1334-133, 2016.
Ma, X., Li, J., Kochenderfer, M. J., Isele, D., and Fujimura, K. Reinforcement learning for au- tonomous driving with latent state inference and spatial-temporal relationships. IEEE Interna- tional Conference on Robotics and Automation, 2021.
Mao, W., Zhang, K., Zhu, R., Simchi-Levi, D., and Basar, T. Near-optimal model-free reinforcement learning in non-stationary episodic mdps. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Modi, A., Chen, J., Krishnamurthy, A., Jiang, N., and Agarwal, A. Model-free representation learning and exploration in low-rank mdps. arXiv preprint urXiv:2102.0703: 2021.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. CoRR, abs//770.006347, 2017.
Shani, L., Efroni, Y., Rosenberg, A., and Mannor, S. Optimistic policy optimization with bandit feedback. Proceedings of the 37th International Conference on Machine Learning. 2020.
Silver, D., Huang, A., Maddison, C. Guez, A., Sifre, L., Van Den Dricssche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):4844489, 2016.
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L.,, Kumaran, D., Graepel, T., et al. Mastering chess and shogi by self-play with general reinforcement learning algorithm. arXiv preprint arXiv:1712.018855 2017.
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., et al. general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 140-1144, 2018.
11

---

Sun, W., Jiang, N.. Krishnamurthy, A., Agarwal, A., and Langford, J. Model- based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on Learning Theory, 2019.
Touati, A. and Vincent, P. Efficient learning in non-stationary linear markov decision processes. CoRR, 0bs//210..1280,, 2020.
Tsybakov, A. B. Introduction to Nonparametric Estimation. Springer series in statistics. Springer, 2009.
Uchara, M., Zhang, X., and Sun, W. Representation learning for online and offline RL in low-rank mdps. In The Tenth International Conference on Learning Representations, 2022.
Wei, C. and Luo, H. Non-stationary reinforcement learning without prior knowledge: an optimal black-box approach. Conference on Learning Theory, 2021.
Xu, T., Liang, Y., and Lan, G. CRPO: A new approach for safe reinforcement learning with convergence guarantee. In Proceedings of the 38th International Conference Machine Learning, 2021.
Zanette, A., Cheng, C.-A,, and Agarwal, A. Cautiously optimistic policy optimization and exploration with linear function approximation. In Conference on Learning Theory, 2021.
Zhao, X., Gu, C., Zhang, H., Yang. X., Liu, X., Tang, J., and Liu, H. DEAR: deep reinforcement Iearn- ing for online advertising impression in recommender systems. In Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021.
Zhong, H., Yang, Z., Wang. Z., and Szepesvári, C. Optimistic policy optimization provably efficient in non-stationary mdps. CoRR, abs/21 10.89984, 2021.
Zhou, H., Chen, J., Varshney, L. R., and Jagmohan, A. Nonstationary reinforcement learning with linear function approximation. CoRR, 2020.
12

---

Supplementary Materials
A Proof of Theorem 4.4
We summarize frequently used notations in the following list.
2 W k6
G.W
Xr,W
Od min (k. W)TH/6)
2W ACR.W + >u,Wd O 4o (2 + da.wd)
Og,W
Ōg,W
2W AGR,W + de.wd
3g.W
9dA(2W ASK.W xx,,w))+Mas
Llog A K
n
AR,I
EnER EieT (8.
Ph p (118,a) ( -P (-
TV
AYP
EnEn Ever (a)ESX)
Pr (-(s,a)))))))))))))))))) - (-
A
ENEn EIEI max
on (s,a) oh (s. as
2
R.TT.
EnEN EiET max
12 11t (s,a) - r * (s, a)
ARI
ENEN Eier maxses T x-)
(11)) - T
- (+1)
(s.a)
(-|s a) - (-ls,
U
- w Ben-(Pais (t)) [ø(sh (n)) + d
Ee on (sh, an don (sh, an) + da.
whw
Li=lyk-W )
(dss,, an (n(sn, TT + d
b%
min W.,W 0 (s an)
6%
min
åg,w
| an)
100
Proof Sketch of Theorem 4.4 The proof contains the following three main steps.
Step 1 (Appendix A.1): We first decompose the average dynamic suboptimal gap into three terms as in Lemma A.T. which can be divided into two parts: one part corresponds to the model estimation error and the other part corresponds to the performance difference between the target policy chosen by the agent and optimal policy. We then bound the two parts separately.
Step (Appendix A.2)) For the first part corresponding to model estimation error, first by Lem- mas A.13 and A.15 show that the model estimation error be bounded by the average of the truncated value functions of the bonus terms i.e. K Σ
K V
je plus term w.r.t. variation
budgets. We then upper bound the average of VT 8* as in Lemma A.18 To this end, we divide the total K rounds into blocks with equal length of W and adopt auxiliary anchor representation for each block to deal with the challenge arising from time-varying representations when using standard elliptical potential based methods.
Step 3 (Appendix A.3): : For the second part corresponding to the performance difference bound,
similarly to dealing with changing representations, since the optimal policy changes over time, adopt an auxiliary anchor policy and decompose the performance difference bound into two terms as in Equation (10) and bound the two terms separately.
We further note that the above analysis techniques also be applied to RL problems where model miissppccificttin exists, i.e. th h & 4, u
.k & V.
Organization of the Proof for Theorem 4.4
Our proof of Theorem 4.4 is organized as follows. In
Appendix A. we provide the decomposition of the average dynamic suboptimality gap GapAve in Equation 7 in Appendix A.2, A.2 we bound the first and third terms of GapAve: in Appendix A.3
13

---

we bound the second term of GapAve. and in Appendix A.4 we combine our results to complete the proof of Theorem 4.4 We provide all the supporting lemmas in Appendix A.5
A.1 Average Suboptimaility Gap Decomposition
Lemma A.1. We denote
Th * (+|s) arg max, Vi pe: Then the average dynamic suboptimality
gap has the following decomposition:
1
GapAve (K)
Vp pe gu
K
K
1
(aPP {{ pr. - Pk Va pa
K
k= h
Bsn (Pak ((0T h Me (ohs ), (+1sn) - =(((118)))
+
k= heH
V fe
km
Proof. For any function f 8 x A - I and any s) E [K] x [H] x S, define the following operators:
(T), = (f(s, .), क (+1))), (-1s),
(JRA))()) = (f(s; (-
We next consider the following decomposition:
Vp - Vp Vi pe +VP *
pe Visitentss
(8)
The term Gi can be bounded as follows:
G Vinkk V=** pe
(IE, (TL.0OT (J
(JE, P..A,, O7 fir)) ((J),) JR. 1
(JE, (8, (8,)) V2, Pr
(r)(s,,) )) plvv 2, ))) + ((T). - -IE,)Q pe
(P Va plyat
2. (x)) + ((Jk, Ju. 1 pT
(Jā.1 (priee Vi - yxt
mk } + pt. pp] yat ve.pe,n)) + ((J2,1 Ik. 1Q p, pe
( Va +B semeenat oedd [yrie (p (02) vol nie (+2)) +(UE, -Ix.) me
((o { paik pk VT Vitz.pu.ma
RE(H]
Σ (P KE[H]
[ront Pe ne (sh, ) mi (-1ss) (-(())))))
Substituting the above result to Equation
8 completes the proof.
A.2
First and Third Terms of GapAve in Equation (7): Model Estimation Error Bound
A.2.1
First Term in Equation 7
Lemma A.2.
With probability at least 8, we have
K
{ pr,k p& V=
K
hE H
14

---

so
H to log(W)+
/ HW +wW3AGnn
- [M111111111]]]]
Proof. We proceed the proof by deriving the bound:
K
[[ Ph -Ph va**
K
1= hc(M]
K
Bs )os (oo [5 (sh,
K
Rm NE(H]
K
Buinatik (ff +
B on ) meik) (sh an)
K
K
k= k=2
Barward [11,
(e ((tt 11 (sh. an)
K
H
B( [ (sh, and E (o 15h an)
K
h=2
K
11 Σ
2
(R.W C
WA
2 1,kk 1,k--W--- W.R-
K
K
h=2
K
WAC 1.1,
2d
2H
2H
1 (R.W + CBAP - 2
WA
K
K
K
H
W
WC
A
2d
h- [1-1M,,1-
h=2
(8) 2H K
K
2H
/P WAG. + V AC
2H K
K B
K
[]]K]
k=1
2 0 # [V ||
KC log())+ AMT. +vW [x1, 1)
where (i) follows from Lemmas A.13 and A.15 (ii) follows because Va + b5 Va vb, Ya,bb, 0
and Σ AVP
[h.,k--Wkk-1] S WAY
[M]] and (iii) follows from Lemma A.18
A.2.2 Third Term in Equation
Lemma A.3. With probability at least 8, we have
K
1
Vp* v
pe
K
so le Kdd(A (ogal///oo H 15d log(W)+ // Af.. +VISACGA(MiIn)
Proof. We define the model error as fh (sh, an) PT((-ss, and Pa(-1sh. an) Pa(llsnaa))lm am)llyy derive the following bound:
We next
phant
pp.kk
K
(
H
3
KL
pk
8
+
K
Aw
W ACBAP
(h-LA)
k=1
15

---

K
(w. 20B (1 w.
K
H
W WACBA (h- (A--
K
Pk. B
K
Aw
A=1
k=1h=
SR.W 2.C
K
(18)
Kd log(W)
(KA(AAlo((0 d2)
H
HHW [M]]
K
W
VP AWW (B.
where (i) follows from Lemma A.15 (ii) follows from the definition of  and (iit) follows from
Lemma A.I8 88
A.3 Second Term of GapAve in Equation
7
Performance Difference Bound
The second term in Lemma A.1
Ek=1 Ene (e h.
Me not (sh. -), Th (-(sn)
(-ss))) can be further decomposed as
K
E
Eyg (Prit [ Pe, (9 ) an (.18)) - n (-190))
k= NEW
Σ
Σ
Epai mran mrac (Kh :), T (-1sa) T (sx6))))
[E[L] k=(l-1)rrr +
Σ
Σ
Epp Bpea--rth x
1 )) o (+1sa) 7 (-18a))
[E(L] k= 1= + AE[M]
(a)
Σ Σ
Σ
E E
E pt.tt Dr 1 12)) [1h 2. (-1st) - *+((1)))))
K
[E[T. k= 1)-+ (E(H)
(6)
(10)
A.3.1
Bound (a) in Equation 10
We first present the following lemma of the descent result introduced in Cai et al. (2020).
Lemma A.4. For any distribution p and supported A and state S. and function Q
S A [0, H), holds for a distribution p' supported on A with p'(-) x p(.) expr Q(se) that
1 + 7) S
1 [DKL(P
p(-)) (Q(s,)),'') -
D
Lemma A.S. Term (a) in Equation
10
satisftes the following bound:
fr Σ Σ
Epra a 1r [1 ., * (-1sn) - o, (-(ss)))) 1==1-11)11-1 AE[H]
Σ
[E[L]
2nKHH+
Lo A + 7 TH.
"
16

---

Proof. We first decompose (a) into two parts:
lr
Σ
a 1-1444 [0t(on: 7, (+18a) - x1115/))
[E|L]
k= (1-1111)) 1)r+1 hell]
lr
Σ
Σ
Σ
B to [ ), 11.111197++11 (-1sa) (11 (+((ss))))
TE(L k- (t- 1)++ he(m
(1)
Σ
Eppat Br 1
(2 7 Tn -1ll-1) (-186))
[E[L] 1r
un)
1) Bound the term (I)
By Lemma A.4 we have
(T) S 2
RH +
Σ
Eps.a- 1 0444
NE(H
[E(L)
Σ
DKY. ( (+1o))) (+1ss) DrY (7t1011)7++(-1ss)) (
(+|sw)] ++= (-1sh)
11+1)++1
$ 2
nKH
+
Epr.at 1rtt pp 11-4444
NE(H
(E(L)
x DKL T T- 1)--))+111 (-1s (-1ss))) - DKL (.1x)))
$ 2 2nkl +
1
Σ
E Eppat 1e [De (7*:(11))++1 (-1sa)]1 (|| (+1s)))
NE(H] (E(1)
$ 2
RKH + LH log A,
17
where the last equation follows because
DKL
(1- 1r++ (1sh)) (((sss)))))))))) = Σ x (1(1-1)r++ (alsn) log(A A -1= (U-1)++1pp (-1sk)
aEA
log + Σ x x1(0011)++ log + (1-1)1++1 ((n1))+((anss)))
a
S log A.
II) Bound the term (II)
(1)) Σ
Σ
Σ
Ep
|| | (-1sn) T
-(1-1))++ (-10%) TV.
le M k= (t 1)r+1 M
Σ Σ
E
E
Σ
E 11
||| (-(ss) 2/ x (-1s((1)))
rv]
Re
1(++))
Σ Σ
Σ
Σ
x (-1s) - 2// -1--1(1113 (-18) n
max SES
TV
1 (=
+
Ir
Σ
||
(+1s)
(-1s) - 1 (-18)
max #ES
TV
17

---

S E
max SES
Th (-Is)
(-1s)
TV
ke[K] he(m]
< T 1MM
A.3.2 Bound (b) in Equation 10
Lemma A.6. The term (b) in Equation 10 can be bounded as follows:
Σ [E[L] +=([))++
(Epritata - Ep..a- wer1 .aa (0t -), m - xf((1o83)]
S 22H [M) (M)))
Proof. Denote the indicator function of state sn as I(s)), and then we have
Σ
(Eprit,oiie - Ep a -
( -), 7 (-lsa) - xf((1o7))
[EIL]
(1-1()+++1
lr
Σ E
P (sn)
1)++ Ip. p - (sh) dsn
[E(L] 1=(1-1)7++1 +1re
33 LE(L] (= the (1-1))++2
pppii (8h) pppii (sx) dons
(11)
where (s) denotes the visitation probability at state under model and policy m.
Consider San (Pp...(ss) PPp... (sn) dah can be further decomposed
(sn) - ppi-i-i (sn) don
1p-iit-l / ppit (8h) pr pi (8t) dsh + S. |ppins (8h) -Ppii (on) dsn.
For the first term San, pp... (sn) - Pppll (0n) dsn,
pppit"' (Nn) ppiii- (sn) don
(Pttt 1 (8n)
1=1
-(PP:1))
(p.t-li ... 1 (sn) dah
(Prie)5"" (s441/9:) (1 (s141181)
8h
aaygr j=1
A-1 II (1970-195)"
(8541185)
(s341ls))dsz ... dsn dsh
j=it1
h
I (pprggo* (8141184) - (P.nt-1)m1 1-111 (s4111ss)
Sk
3541
18

---

A-1
max
II
(P))))
(8541188)
II s=i+1
(Pii-lyys"
(8841183 )ds2 .oo dsn
j=1
(Prtyri" (81-118;)
(Prit1)) (B14118i)
max 6.58
5h
3641
h-1
II
(P (85t1l8;) II (prt-1)s"" (85+118))dsz ... dsh-1 d8k
max
51 #411E
j=1
s=it1
(111)
Pt. p. " TV J
Il (P
(8i+1 18; (sssds ... dsc
(x.O)Sxx x
B
max
II (P j=++
(8)talsy)d8442 ... dsh-1
dsh
84+1 ES
12
max (xx
p.. (+1s,a) P. (11)
(12)
hE]m
where (i) and (ii) follow from Holder's inequality, and (iit follows from the definition of total variation distance.
Similarly for the second term and from Lemma A.19
f ppT... (sa)
1 (sn) dsh
Σ
max +
Th
(-1s) o (-1s)
TV
(13)
he[H]
Plug Equation 12 and Equation (13) into Equation
we have
/r
Σ
Σ
Σ
E Jiik Epeit- Dv t (
(1 ), (-1sh) - *x(11s1))
(E(T) A= (1- 1
$2 Σ Σ
337
Σ
* (11s) -
max
aES
[E[L] hE(H t= 1=(1-1)++2
NE(H
pt p. (-1s, (11, o
max (x.0)ESxA
VE(H!
2 Σ hE(H]
Σ
max 3ES
(-15))
[E(T] k= (1- 1)r t= 1jr+ vE(M
P. P. (-1s,a) p (-1s, t- a) m mmm))
+ (s.a)ESxA
-2 (A
19

---

A.3.3
Combining (a) and (b) Together
Lemma A.7. Let =
Llog
and we have
K
Σ
Σ
Σ
E
E
[(0 * (oh: ) Th * (-|sx) = ((((ss))))
[ELL] ([(())))++ NE(H
S 2H /log A/T 3HT (m), + A(m,11))-
Proof. We derive the following bound:
K
(S [1OM pu ( 1), (-18%) n((s))
Es ~ (arik
REAAHH
1 5"KH H + LH log A + T (m..NK + (M (m)))))
1
(18)
- 2H / KL 3H HKKK + (()))))
2 / log A/T 3//
3// [K]
A ((),))))
where (i) follows from Lemmas A.5 and A.6 and (ii) follows from the choice of = -V blog
A.4 Proof Theorem
4.4
Proof of Theorem
Combine Lemmas A.
A.3
and A.7 we have
K
1
GapAve =
Vp
park n
pr ,
K
[[V[[[KKAA (KdA(A log( (H/))+
KA log(W)+ + (
A/WACCAA (111111)
2H
3HT
+0
+
(A A(11119)
VT
HAPA
(A d2) + HAdA
H2W3A A
0
(2+ W
[H][K] +
VP
W
K2
(
2H
3HT
+
+
(A (M) + Am).))
(14)
K
(IT)
A.5
Supporting Lemmas
We first provide the following concentration results, which is extension of Lemma 39 in Zanette et al. (002T).
Lemma A.8. There exists a constant d Od minsk, WYTH//)), the following in- equality holds for any k E [K], h E [H) S. an E A and & & with probability at least 1 8:
cl (s,a))l 5 [0n(s, (1) 5 (s,n(s, a) (0)( (-
The following result follows directly from Lemma A.8
20

---

Corollary A.9. The following inequality holds for any k E [K]. h E [H) E S,an E with probability least 6:
min @k.W
( an) Mor h 1
I (sh, an) s 3 [S an)
(0 mich)
where Ökk, 5/ 2W AGR,W dw,wd
We next provide the MLE guarantee for nonstationary RL, which shows that under any exploration policy, the estimation error can be bounded with high probability. Differently from Theorem 21 in Agarwal et al. (2020b), we capture the nonstationarity in the analysis.
Lemma A.10 (Nonstationary MLE Guarantee). Given E (0, 1), under Assumptions 4.1 to 4.3 let
CB=V Poiin'
We have the Ca_ and consider the transition kernels learned from line 3 in Algorithm
following inequality holds for any n, h 2 2 with probability at least 1 - 6/2:
E
[sh( S GR.W A.
(15)
W
(
i- W)
19%
where, St.W = W| In addition, for h 1,
W
[ & Sn.W + +2CgA/f,R-Wa. W.,-
a))((
e v.y S. The model estimation process in Algorithm can be viewed sequential conditional probability estimation setting with an instance space and a target space y, where the conditional density is given by p² (y|zz) p* x)) for any i. We are given dataset D == {(T,; 1
Proof of Lemma For simplification, we denote x = (s,a) E 8
where 24 ~ D; = (1 91:-1) and yi ~ p-(()))) Let D' denote tangent sequence {(r,, v1) function class F = &
where x/ Dj (2 1, Vis-1) and 3/1 ~ p²(-1=(). Further, we consider a (X } R and assume that the reachability condition pa* F
holds for any i.
We first introduce one useful lemma in Agarwal et al. (222bb) to decouple data.
Lemma A.11 (Lemmaa 24 of Agarwal et al. (2020b)). Let D ba a dataset with most W samples
and D' be the corresponding langent sequence. Let L(P, E Ei=v((-wy I(P, (xr)yy;) be any function that decomposes additively across examples where is any function. Let P(D) be any estimator laking as inpul random variable D and with range F. Then
Ep [oxp exp (I(P(D), D) - log
Bpr Epr (exp(I((PDD)) (opt)))))))))))) log log|F1)] $1.
Suppose F(D) is learned from the following maximum likelihood problem:
P(D) == arg maxpeF
Σ
log. fa, Bi).
(16)
(D.A))DD
Combining the Chernoff bound and Lemma A.11 probability least 1 5,
we obtain an exponential tail bound, i.e., with
llog ED' [cxp(L(P(D), D')] < - log |F| log(1/8).
(17)
To proceed, we let L(P,D) -i=iv(kw)) log P. (x,, v:)/ P(x,, v.)) where D is dataset [(,, way (and D' L(P, D).
k-1
log(P***
[11,, 3/) is tangent sequence). Then L(P*, D) 0 s
21

---

Then, the RHS of Equation 17
can be bounded as
RHS of Equation
Σ
log( pa (Ii 9:)/ P(as. Bi)) + log |F] + log(1/6)
2
== W)
log [ + log(1/6) log (1 w /00),
(18)
where the inequality follows because P is MLE and from the assumption of reachability, and the last equality follows because [F]
|
Consider for any distribution and q over a domain Z. Then the Hellinger distance (2
[VD(=) va(z)) dz satisfies that
(pllg)
= =/ (Vplz)- - v((z)) de = p(x)) -(22)_2V((a) g(z)dz
= (1 1- 11Vp(())) p(z))
V((3dd) = =2(Y1-VDlivatiid 22Eng 1 vp(z)//(2)
(19)
Next, the LHS of Equation
17 can be bounded as
LHS of Equation
PMiM(al )) |D]
log Ep
exp
Σ
2
1
log
P(ay, vl
-=Iv(k-W>
1
p prck(sg
P(xi, wi) )
Σ
log En
exp
log log
i= W)
k-1
P(r w) Park wz)
Σ
- log Ep
i=Iv(k-WW W)
P(xs, wi) Pt. v1)
1 ED
==v((k-W
11
P( Vs) P Prr Vi)
Σ
EngaD
1 - By.wPr.((la)))
(=V(W--W)
A-1
P(ar, Vi)
E
E By.
(x U:)
(=)((k-W)
k-1
P vi) pa.k Pa 21)
( vi) pa (x w1
Σ
ENDDD
V
1= (=V(K-W)
(18)
2 -WCR4 W.R-)
Σ
EngnD: H2 (11x))))PP(((aaa)))
im lmlvk--) W)
(1)
2 PWCAAP (R---I
Σ
k-1
E Bn,nD; p(o P(ac, -) ) TV
(20)
(IV(K-W)
where (i) follows from the above definition of L(F, D). (ii) follows from the fact that S
- (.) (tii) follows from the definition of variation budgets and Equation (19). and (iv) follows
from the fact that [pp()) - g()) < H² (pllg) as indicated in Lemma 2.3 in Tsybakov 2009
22

---

Combining Equations
17
18
and 20). we have
2 2log (10b v 1//02
Σ
E (p (1)
[fh an) $204))
(21)
W
W
(=Iv(k-W)
prr (1hn 1.00
We substitute 8 with 5/2nH to ensure Equation holds for any E [H] and n with probability at least 1 5/2, which finishes the proof.
The following lemma extends Lemmas 12 and 13 under infinite discount MDPs under stationary case in [ehaaa et al. (2022) episodic MDPs under nonstationary environment, which captures nonstationarity in analysis.
Lemma A.12 (Nonstationary Step Back). Let = VIV k 1 be an index set and (Ph-lhizz {(r (::1)11)) be of generic MDP model, and II be arbitrary and possibly mixture policy. Define an expected Gram matrix as follows. For any Φ E 4,
- = -
Σ REI
E
[on-1 an- (Øn- (8h- an- -))
Further, let fh-1(sh-1, ah-1) be the total variation benween P and Ph-1 time step h 1. Suppose g S A + R is bounded by B o0), i.e., 11 S B. Then, wh 2 2, V policy nhe
EE ph
ax) (15h,an)(sn-1,,,)
(1-h-1,0h-1)llpp 1-))-1 x
[Ere AB AB ppppp (a( - 1 +d Exez AB2 aidi
oh 1h-1 1-(21, [1 18- 1.84 1)33.
-
Proof. We first derive the following bound:
E
[g(s,, an) 11,1100-1)
*A SoPPE Syoeth
Σ
in 1), 15 (s
/ o (8n dds
< (80-1
where the inequality follows from the RHS of the above inequality as follows.
Schwarz inequality. We further expand the second term in
g(sn, an ((a dsn
M M
(
27 Ae.
E (a (9--
E
*h (m m) Ph-1
TeT
dh 2h
and (1 1)
E pk
+ X wdB
*k-1 ( wll
TET
(18)
E
E
g(sh an 0h-1,ah-1
+ dB
% m 2--
1E7
23

---

(186)
g(sh; an)² 8h 8h-1, an + Ad.
-1-1
B
E
P 1 1,, Phi (8h-1, 1,- ah-1)
TVl
Ph-1-(Piixp)
B
E
(80-1,
IEI
9--1011
(10) S EieT. AB
Eier B² Beg 1 1-(06 (h--1(9-1104-1)))
1--1
where (i) follows from the assumption that || S B, (it) follows from Jensen's inequality, (tii)
follows because (5h- 1)-1) is the total variation between p h-1 and Ph-1 at time step and (iv) follows from importance sampling and the definition of - This finishes the proof. C
(-Is, Recall that (s) = (-|s. a) - (-ls all Using Lemma A.12 we have the following lemma to bound the expectation of (8) a) under estimated transition kernels.
Lemma A.13, Denote a..w 2W A Aw.wd. For any l [K], policy x and reward for all h 2 2, we have
E (x) m)
f an)
8h- 84-1, 10-1
< Smin axw 10% (on- (on (oh_ an-1)
16)) 1 + V W AACB [.
(22)
for 1, we have
[f(( sv sy / + -B
IE ai
(23)
Proof. For h = 1, we have
01 [[(,
<
V A (S... + (ike-w.x-11) w
where (i) follows from Jensen's inequality, and (Mi) follows from the importance sampling.
Then for h 2 2, derive the following bound:
E (pt
(s an) 8h-1 ax-1
E
| ( a,-,,
X
A
Σ
E
[Jh am)
1
(esk
b- 1xx
im (V
*y P 11
W W.W.-1e - -W-- + dewd+ A
Σ
[1 (8h-1,
i=lvík W)
WWAP -2,k W.K-13 th.
24

---

3k Uh
(5h-1: an-1)
lot 1,00
(1i1)
W
1 an-1))
3 Aw
W (LLM WWA---
where (i) follows from Lemma A. 12 and because 1f/ (5h, an) S 1; specially the first term inside the square root follows from the definition of U h-1,80 the third term inside the square root follows
from the importance sampling; (ii) follows from Lemma A. and (ti1) follows because Va b S va + Vb, Va, b and ( an- 1) (6t
Aw
The next lemma follows similar argument to that of Lemma A.13 with the only difference being the expectation over which f (8h; an)) takes.
Lemma A.14. Denote w..W = V 2W A dk. For any ls E [K], policy x and reward r, for all h 2 2. we have
Sh JK(nn, an) 8h- 1, ah-1
E (9h.a)))(Pt.k
ag,W | 1 (sh-1 (50-11,0-22) an-
min
h )- { + 2d
W AAAAB
(24)
for 1, we have
((a. + CB
E a1ou
S
(25)
Proof. For h = 1.
E aLio
[
E
(2)
V
A (W.W
C
1
a1
where (i) follows from Jensen's inequality, and (it) follows from the importance sampling.
Then for 2 2, we derive the following bound:
E
(sn, an) 8h-11 ah-1
(
Eag
A A 1 Wi
"h-1-(Pet,,t) (1-1))))((4))
[(N(on wd
sp-paik (11--11hh11)
Vud + tn 1ile w.- 1)) ACB w.K. thawd
x 10t (86-1,
(1t k))
(111
Wk.W
( an-1) wett
+ V 2d
ACBAP
ih- ( W.-
where (i) follows from Lemma A.12 and because 1// (sk, an)l S 1, the first term inside the square root follows from the definition of t 1, the third term inside the square root follows from the importance sampling, and (id) follows from Lemma A.10
The proof is completed by noting that [ft, (sh, an)l < 1.
25

---

The following lemma is a direct application of Lemma A.13 By this lemma, we can show that the difference of value functions can be bounded by truncated value function plus a variation term.
Lemma A.15 (Bounded difference of value functions). For k [K]. 8 2 any policy a and reward with probability at least 1 - 6, we have
pi V
S
Vi pe
3
W WAC ( ( / (SAW + =20= 1, 1,1--W,b--)
Aw
2=2
(26)
Proof. (1): We first show that V ph,r S V Sh.
Recall the definition of the estimated value functions V h. ,r (9n) and ② h. (on; un) for policy m
Th (sh, an) - -min { {I, (5h, and + Ph vet
A4 (sh,
V pn (3h) E [e (sh.
We develop the proof by backward induction.
Va When = + 1, we have Vx #+L.P..,, ( Bu, (81+11) = 0 = Vn
b4 (8H+1)-
Suppose that for h + 1, V Vita - V N4,,ee, , S Vi 1tI.ee fe (8h+1) holds for any
8h+1-
Then, for h, by Bellman equation, we have,
(, an) pe an)
pr VETII (sh, PAVT h, (Sh, an)
V viti, -Van Ph (V (Viti,pneey (Vitt,mitr-V
(sn. (Pr. - Px) Vilpaa,
I min 11 (sh, an) + 1sh VoL Vitl, VIT Ae (sn, an))
min 1, fh on) PRiv h+ pa (sk. an)
TT.pe Pe. (Sp= an):
(27)
where (i) follows because pt (-1sp, an) P
(-1sh, an) an))lTy
= fh an) and the value function
rV
is at most I, and (ii) follows from the induction hypothesis. Then, by the definition of V= h. (sn), we have
TT h.pe, (8n)
E O pu (on, (on,an)) an)
-E LE Pr. an)
18
o Pi (0n, an) - Qu. (sh an)
@h pe gr (6h. (n)
E
26

---

VTT hy px (sh),
where (1) follows from Equation Therefore, by induction, we have
27
V
pe S V
(2): Then we prove that
H
V fu
V bh
3 Aw
WACB
(1- (AC
+ ( +2 22C W.s. -1
Am
By Lemma A.13 and the fact that the total variation distance upper bounded by 1, vh 2 2, with probability at least 1 - 55/2, we have
(Kh an) sn-1
ax,W | | ( (8h-1, an
E pk,m s
E
min
3 Aw
+
WACBA (k- W
(28)
Similarly, when h = 1.
& V 1 (Ge.w 2. -.ikk
E
(29)
Based on Corollary
A.9
Equation
28
and āg.W 50x,w, have
3
(sh, an)
8h
W AC A
dw
min
a..w ((th(sn.a))
3 + +V Aw
WAC (1- W.A-1]
J (8441, an+1)
(30)
For the base case f H, we have
E
pu
=
E
[H aH) SH-1
pt,
3 WACBAP (H (IH) (k-.W---
< E
QH ( (H--)lHs-)
Aw
{ I, 2 90
} +
3
<min
W A (H-M
8h-1: an
Aw
3
v H- ze (8H-1) + V
W AA (H-LHH,
dw
For any step h + 1,h 2 2, assume that Ept, Vi
ViLL.ee fr ((n+1) sh
S px +
EH V Aw
3 WACBA P 1,0, [. holds. Then, by Jensen's inequality, we obtain
E Vx (sn) s/-1, ah-1
27

---

min
E
(sn,
an)
+P V
P.Vitti Pe ,a (sh, as) 5h-18 an-1 an-1
,
min
1.
(8h-1.
WACBA
Aw
+
E
E
VT
I+ Aa (Sh+1)
8h
84-1, Oh
p
(80
3
min
1b% (sh- E,
1) +
W AACBA
dw
(h (h-1,b),(k-Wa) W:K
+ x
I (o. an 1
Σ
WAC
(R II -M-------W--- -.
Aw
h Wmhh+1
min { 1. {
H
pe (1
WAC (N-
Aw
N'=h
3
V A B (5h-1)
W
W (M-M
dw
h-=h
where (1) follows from Equation By induction, conclude that
30 and (ii) is due to the induction hypothesis.
V pa
= E ( ai)
+
E pA
VJ p. pe (82) 81
3
$ =
A V 2CBBBBBPP... Wikk
w1 11)
+ pk,bt
Vn
W WAC (W-- 1,
Aw
h'
Combining Step 1 and Step 2, we conclude that
Vp..r Vi
H
I V p + V (C.. VA(Cew + 2 1.(k (.th- (.---
W AC (N 1 [R- WC--
Aw
Similarly to Lemma A.15 we can prove that the total variance distance bounded by f g plus variation budget term Tollows. Lemmas A.15 and together justify the choice of exploration policy for the off- oof-policy exploration.
Lemma A.16. Fix 8 (0, 1), for any h [H) k E [K], any policy n, with probability at least
1- 1-6/2,
E *y k) ap
[Jh an)]
H
2
v Pa
W ACBAP
(h- 1.). 1.), W.--1 + / (S( + 2C PP w.k- -,
Aw
h=2
Proof. Fix any policy n, for any h 2 2, we have
[0%
an)
E
MAEEERR m) nor
V he (sh-1,
E (Pkk)
28

---

min { 1 ap-1) + Ph 1/
n. sa (5h-1, (n1))
E
E
(sh- ah-1)
*h 1 (-( oh-1
ai
fi B
(31)
Hence, for h 2 2, we have
(1)
3
[1 (sh. an]]
(3h-
W WACBA P (h-LMRRR-WA--
V Aw
"N (pk(pp
2 (PR.))))))
[ (n--1, [m)
3 Aw
W AC 1B-
"h-Im(Pk;s)
(18k)
3
pk B
+
Aw
W AC
(
(R-
(32)
where (i) follows from Equation 30 and (fii) follows from Equation
(ii) follows from the definition of Q 1 da (5h-1: ap-1).
5A (Sh, an)]
E
E
(sn, +
E *y r ..)) m0
[hn, - E
(sh, and
"/ Mprclpk.r) un mar
"n (MO m) ay
<
VT pt
3
W WAC
V (SR.W + AP 1.1k
Aw
h=2
where the last equation follows from Equation 32) and Lemma A.15
Lemma A.17. Denote Õk.W 50 Crk,W
22 ACk,W Ak,wd, and B..W
V (dAA Ak.wd. For any [K], policy and reward r. for all 2, we have
(1s,, as)
E
8h-1, ah-1
<Bk.W I (0 a an-1) lwve
1 vP V
+
1.1 1o--I,((----- Wk-
(33)
and for h 1, we have
9Adda W
E
B
(1)
(34)
a1
Proof. For h
(
(18)
9
E
(51,
01)
V
E
(8
01
)2
S
W
where (i) follows from Jensen's 's inequality, and (ii) follows from the importance sampling.
29

---

Then for h 2 2, we first notice that
R-1
Byt (sh. )=)
E
1=1v(E- W)
Σ (=v(k-WW
ak | an) (189]]
Σ
9a | ani
(
w=l((k-W)
h-1
S w
Σ
(on, an ) (sp, an) (Ut h
"A (pritt)))
imIv(k- w)
S 59 (Ia) 9da
(35)
Because
vb
Va
vb and for any k
E
[K].
E
[H].
max (aa)ESX)
pr pr,ktt (-1s, a) - pi (-18, a)
TV
Pr Apt 1 (-Is,
PM P TV
then for any H.I, we can convert loc
variation budgets square-root foe variation budgets.
AVP H.I- VAh. S
(36)
Recall that W the following bound:
A-1 -i=Iv(k-W) W) (ee (P)ps and) [oba (8h, an)on(sn, an) + d Ia. We derive
By (5h,, an) -h-1, an-1
E
@ 1h-1 (8h-1, (n-))
E P
h-
1-1
Σ
(sn, an)a] + AD h- 1-l--1----a WK- + Aww
x
A
E
1 (f)
==I((--W W)
ma h-1 (114-11- 1 og (l)(())
(5))
E
b n (sh-1, an-
X AdAaa + dR.wd
+ d
P (k-1
4h
1
(wa
(141)
E
| (Sh-1, an an-1) (we kk)
x
v 1dAAa + dw,
A V --
AVT
where (i) follows from Lemma A.12 (ii) follows from Equation 35 and (1i1) follows Equation 36)
Before next lemma, we first introduce a notion related to matrix norm. For any matrix A, || denotes the matrix norms induced by vector fo-nm.. Note that ||]|, is also known as the spectral norm of matrix A and equal to the largest singular value of matrix A.
Lemma A.18. With probability least 1- the summattion of the truncated value functions under exploration policies (#t)kEIk) is bounded by:
V pa J
K
Kd
a p
50
VKdA(Alog( / KH/6) + d))
H
log(W) + HWW [H]
30

---

VP WWSACBA(HL.N (M.1K)
Proof. For any [K] any policy n, have
ViT pb,Bt
pu.t P/
2. pa Ba (8), PV V pi (s1,
= (Pr P. V (e,,, an) + Prrh (vi
2.
V
( (81,
[M()), a1) + PP
(ver
2,80,,
-Va (2.
$ E (1),))
+ E
2, - Vxx
pick
H
E p
Σ
(sh,
Vipitt,es
(37)
As result, have
K
K p. sh +
K
Vp
v
p
k=1
k=
Step 1: We first bound Σx=
V
pa gr via auxiliary anchor representation.
Recall that U.
h,gg.. Σ k-1
Li=Iv wy E Eon-(priaa)) (oh (sh, (sn an an)on (sh. (sn, an) + AR.w La and
namira) ( an)o% (sn, (sn, 7| Ne. Ia. We first note that
define T. = L1 B Bog-(prs,e -2044)
E
for any h, the following equation holds.
Σ
oh (sh an) lecllers
RE(R)
Σ KE[K]
Σ
|1 ||02 (sn and
anll mon )-1
k.W
kE[K]
[K/W]
(++1)W
||o5 (on, (on, M
Σ oL Σ
(( k=tW-1
Σ
(38)
KE[K]
The th and U in Equation (38 both change with the round index k. To deal with such
issue, we divide the entire round into [#] + 1 blocks with an equal length of W. For each block / E . K W }}, we select auxiliary anchor representation ,t, and decompose
Equation (38 as follows. We first derive the following equation:
(++1)W
| Non an)
l
(PP
k=
((+1)
1 |
Σ
B ((
(sn (sh,
(++1)W
Σ
E
@ ( ann
110 (x))s/aa))//))))) (
k=t
(+11)
Σ
0h (0tt (s)
1 (5h,
(oo. horrk)
wu (w+1)
k1
31

---

+ (sh: an) ||2
10 +1
(sn. amill
(sh:
(++1)
Σ ((PR
Jont (sn. an)
13 (sh, ax)
||
weww h (
k= +1
(++1)W
11 (s and
(s. (PtNitt))))
k=tW+1
(TT)
(39)
For term (If), we have
(++1)W
Σ
Ilon (sp: an) omille lcoe.
hor 1 10 (sh: and I
R=
SE B an ste [on (on (0R. hoo "0 (n) (e)) (e
A ) 1102 -0 (s)
+ * (n))aa) (U
hopt. .W +5 (sh, - of st. (sh, an) (U (1 10 w. +1 (sh, anh)
(++1)
Σ
E ((PA
11 (sn. anill (uu.aaa 11) 9h
(s an)
16 se, (s an
1
k=
1 (on, an)
+1 (sh. an))l | ( 11 10 (sh (sn am)ll]]
(1-1)
Σ
((
2
o (Sh, ax)
an)l
Aw
k=
2W
(40)
dw
where (i) follows from the property of the matrix norms induced by vector le no-m.
For term (I), we have
(++1)W Σ
|1ot ( | looo. )- 10 (sns and |
(sn, an)
(cre
k=
(+11W
Σ
E B
(0x ( (sns
(UN.W (Uuhspaa)
(( (1) " and
k- +1
(++1)W
Σ
oo (sn, an) TaaaaaT(c ((URi) (Ustgrraw Be (r)
- U.W. hishrit )
(U
(a on (sn an)
k= +1
(o (o "11,1l22* (en,)el""()
(- (oo sky I B ((an (og.ew+ (on )on (s -0j (snsan)o (on ]1p Di A
(++1)
Σ
|1 (sh, an) wWW ( on) of * (sh, anjon d (sh. and an) [|p]]
E
AW k=tW www.++lvvik---- w (n ((P..))
(1+1)W
Σ
11 (sh, an ( +1 t
(sh, an) s/,W++1 (sh. an) an) 2 (sh, an) (sn,
B
XW k=&W +1 W (on (
+ 1o
WW' an an)
(sh, TT)
(sn, " an) (sh, (sh.
32

---

(1+1)W
2 2
Σ
[|| hh (s) 0/
greW++
(Sh. (sn,as) [n)11
AW k=tW +1 i=lv--W
(+1)
Σ
2
4
(41)
X
-1
R=EW --li--li-iiiii
where (i) follows from the property of the matrix norms induced by vector norm and (it) follows from that | oo (sh, an)
- 1.
Furthermore,
(++)WW
|1 +1
(P
k=
(++1)W
E tr (Pennaa (0 (0 (shy an )0n A (sh, an) [n) (Uhign
k=
(++1)W
Σ
((rr (ot (ssnnan)o an)on an)
+.. (sp, an)
(UA (npphimess))))
k=
(++1W
Σ
E A
(o ash, . (sh, an)
Oh
(i
h
k1
W
< 2Adlog
(42)
dAu
where the last equation follows from Lemma D.2 Then combining Equations (39
42 we have
(+++1)W IJW
||
E (sn (((Pnt
0h (sh. an)
k=tW-1
(++1)
< 2Ad
W
2W dw
A
Σ
Σ
2
dAo
(1).
AW
Am W i' -i-lk-WW
(43)
Substituting Equation
43 into Equation
38 we have
E ass (=(Pr
wn.w
2 (sn, an)
kE[R]
[K/W] (++1)W
w.w
Σ
E (Prr
|
an) llure w-1
KE[K]
1=
k=
+1
af. (K/WW
2Ad
W 2w A
Aw (w..ee
>
2k-cw Di. x (8:000+1--1)
10W
2K Ad W
W
2W
2W2
K (2W (2WAGA) ACR,W dd
log(1
A
(K),KK] +
A
(h),KK] (44)
aDo
dw
A2y
where the second equation follows from Equation Then we derive the following bound:
443
V**
p
33

---

E ) [th (sh, an)
)
KE[K] NE
(2)
ELEINT
Eilzz
B 1.n-- Din--
oz, (o- 2.1,0) + za W.Ann 1.1.14 w.-
+V GR. + CBAP
2 1,18 (.1B--W.-1)
H-1
a..w 1lo (on an) leve
E
(s (
Am1 kE[K]
H Σ
WAC
I- M--AA,A--W- W.B-
kE h=1
kE(K)
2AKd W
W
2W
2W2
K AC&,W + Ae.d)
log(1 1 + dλo ) + A
4
dw
[N).[K]
A
[A)[(K]
AW -
Σ
VAR.W
kE
kE[R]
2AKd
W
2HW
2HW2
$ / K (2W ACA, + AR.wd)
H
W
log(1
ddo
+
Aw
A
[MIJK]]
+1 V
Aiv
A [m.
AWRAC VP
E
AGR.W
(MIK)
KE[K]
2AKd
0 [|
H
log(W) + HW? H[]K]
+ V W33 /P
W
(H.(K))
(45)
where (i) follows from Lemma A.14 and (ii) follows from Equation (44)
Step We next bound E
V via an auxiliary anchor representation. Pa.k je
Bl. Jon ( awll
Similarly to the proof Step we further bound ΣkEjK] (a
We define W.k.W h.gh..
( 2i=Iv(A-W) W) ((ono)))(p))))))) s0 (sh, an an) (on,an)) + d La and
W.R.W.t = Σ (lea.a)))(Pr..)) (6 (on, (n )d, (sn h. for any h, we have
T=) (sn. + de We first note that
Ben 100 and love
B(on.on)
BE K)
2
Σ KE[K]
Se. Σ
E(en,on
( (on (ono
(wee m
RE[R]
[K/W]
(++1)W
[ l h.sr,))-1
Σ RE[R]
32
Σ
Be +1
Σ
an)
(46)
The o and W in Equation 446) both change with the round index k. To deal with this issue, we decompose follows. We first derive the following equation:
(++1)W
Σ
|ox (sn, ani)l (
k=
34

---

(++1)W
1 10t +1 (sn, (sn,
|| (wot 2,0
k=tW+I +1
(+1)W E
xxk
(sp.: un) 1img )
110% (oh, an) (a histawt+))
(
hh
k +1
(+11)
E E
(5 and
(sn an) | (wot. h.om.ew+1)
- -1|05 10. (sh; an) an)l (ooe a
+ oh (ons an)
(Www
horr )-1
(+1)W
o0 and all (- - 110 -1 (sh, a (avn +=)))
Σ
E (n
k WW+1
(111)
1)+
(sn an) allle (2)
02 1,, (sh, an)
E (n
k=tW+1
(IV)
(47)
For term (IV), we have
(++1)W
(sn )
l1o (sn.
10 (sh, and ar)) I|
Σ
k=
-2 "ow.anaaer (on (wrk. +1x "0 -0 (suran) " (We..
hoonew 20 1 (sn.an)
+ 0% (sn, an) (W (W
(iph.w on
ba. (sh,
(Sh, and - 0r x. (sh, an) (W hhotaw -1) .)- o +..W
(sn, ax)
(++1)W
Σ ((
|105 (on: an)ll
(wree (o)) ) 1
(sn, un) 2x w (sh, an)
k=
+ |0 10 (sh, an) - or +1
(sh. an)l (wree (wp)) )-2
(sn (3
(++1)W
Σ
2z (sn, - +g (3%,
Aw
k= +1
2W
(48)
Aw
where (1) follows from the property of the matrix norms induced by vector norm.
For term (ITT), we derive the following bound:
(++1)W
||ot (1 (sn, un) live.. m.ar,a) )-x -
| (sn, and |(we w2)
((e).e))((P)..0))
k=
(++1)
Σ
(00 (sn,an)) (awdh hypt - (W... hw (1) - (ss,
k=
(+1)W
Σ
E (s
(sn, T (wrei )
k1
W.w. (W..W horreii h ww....w -1 (sn, an)
35

---

(++1)W
((praa))((P)). 1l (on. an)l
||
(ll
W.k.
hisor 1/1
k=tW +1
(wrkir )=
0 (sh, an)
(++1)W
(81) 1
Σ k=WW1
(s (x(
pn (
(shs an o
wf +1 (shs an)
W (sn (
2h (sh, an Joh 1 (sh, (sh, an) 7
l12]
Dk= El w [1 - " aoo (on.en) -0x (snnan)o) (on.as) TT) [12]
(++))
$ //
(+DW Σt Ei w/) (- +9lloo,"" "oon, (on -oz (snnass)) (snvas) l1.
+ ph
W W++1 (sh; +sh, (n,an))
(sh, an)
2h (oh, an an (sh, an) (1
(++1JW
2
Σ
Σ
E (-
(5h, an) (sh, 1h w (Sho (n) [
AW k=tW+1 i
(+11W
2 A/
A
(49)
where (1) follows from the property of the matrix norms induced by vector & no-n and (it) follows
from that |ox ( on)
S 1.
Furthermore, we derive the following bound:
(+1)W
[0% 1 (sh, an) ( lieve Aig
Σ
E ((on.a)-(PPot
k=
(1+1)W
Σ tr (B o (0. (sp, an) an)on w. (sh, an)
(Wew. hoo)ow++))
k=
((-1)W
<
Σ tr (B(nnan)-(PM)) (0),WW- (sp, an an s1 (sn, an)
(sn,
k=
(++1)W
<
Σ
E (p
+ (sh, 103.an)0j on) tr 0h
1WW+ (s ash 7|
k=
< 2d 2dg(1 +
(50)
dho
where the last equation follows from Lemma D.2 Then combining Equations (39h to
and (50) we have
(+-IWW
Σ
E ((sneen)((Ptt..)))))
| i (sh, an)
(W 3-2
k=
(++1)W k-1
< 2d +
W
2W Aw
A
Σ
2
dAo
dw
k= +1 -= W
(51)
Substituting Equation
51 into Equation (46 we have
- Be. |0% (sn, an) l
h. )
KE[K]
36

---

[K/R]
1++
7
Σ &k.
Σ
Σ
(sh an) a
mon
kE[K]
+1
NNE o2 E
2d Tag ) AW A (W)) Disowts Eteive
A aw K(9d A t.., and log(1+ axo Aw Ansyan
(52)
2/
where the second equation follows from Equation (1) Then, we derive the following bound:
E RE[K]
Vāk p _
Σ
Σ
B(snsan)
(on: and
KE[K NE(H)
H
E 110 3k.w | (s ag an-1)/
live -00k)
kE[K]
2
A P h- +V
9.dda k.w
d
1,fk
lalk-- W.k
w
H-1
E as (x Br. |0h (on ( (n)) I(nns
1=1 kE[R]
9Ada
W
[H],
VP
+ Σ
W.W
d
W
KE[AT
2kd
W
2HW
K (9dA(2W A Au.wd) + de,
H
log(1 +
W
ddo
dw
2HW2
+ W
vP HM
[HIIK]
Kd
0o KKAMAAog(8|/V/////) - d2)
H
log(W) + HW22 [M]]
W
+WVAAYE VP
[H]
(53)
where (i) follows from Lemma A. and (ii) follows from Equation (52
Finally, combining Equations (3)) 45 and (33. we have
pk j 2o( [[Alog||)0
Z4Ke log(W)+ + MW
+WW VM.
[8].1]]
1=1
+0 wwA/t//loo////1////////
log(W) h
0o
log (og(W)+ log(W)+
VP +VW
The following visitation probability difference lemma is similar lemma 5 in Fei al. (020)) but we remove their Assumption 1.
Lemma A.19. For any transition kernels (P [M], e [h 1),8h S and policies [ and rt', we have
Pm Pa p (8n) -p P.. ... p < max [-(sss (-(-)s)]l
37

---

Proof. To prove this lemma. the only difference from lemma is that we need to show max,, Σx Pj (1)+1ls)) P5" (s - 2 max.es [ T)(+s)]l holds without assumption. We show this as follows:
(s,+1l8)) pai (m)+1|5))
max
5j
8,+1
((5)-11s). - E P(5)41l33,
max
5)
$541
< max
P(5)=1l3,, -
%
$j+1
P(5)4n]s,,a) -fj(ss,)
max
*j
8/
max
[r((al8)) - ,y(a|s;)] - = max [15(()1)) -a00)-/(((0 (1s)lrr
max sES
a
B Further Discussion and Proof of Corollary 4.5
In this section, we first provide a detailed version and further discussion of Corollary 4.5 in Ap- pendix B.I then present the proof in Appendix B.2 and finally present an interesting special case Appendix B.3
B.1 Further Discussion of Corollary
4.5
We present detailed version of Corollary 4.5 as follows. Let (),xx(NV) min(K, max for any K, N N.
Corollary B.1 (Detailed version of Corollary 4.5 Under the same conditions of Theorem 4.4 if the variation budgets are known, then for different variation budget regimes, we can select the correspondingly to attain the optimality for both (I) w.r.t. W and (IT) w.E.t T in B For (I), with W [p K (A V + A I.. part (I) is upper-bounded
Equation
by
H (A+d))
(av++ ns.
(54)
Ha at (A+ # (a/T+ (AVT+
k2.
For (II) in Equation
3 with T = Hp (1K3 + --) 3 1), part (II) is upper bounded by
(A (A*+ Jk <AA*+AT
Vi
2H 3 (HK) 3(A
(55)
H4 H44H 147)
R<(A++a>)
For any 6 2 0, if nonstationarity is not significantly large, i.e., there exists a constant < such that (AP= + A7) < (2HK)) and (AVP + A (2HK), then PORTAL can achieve e-average suboptimal with polynomial trajectories.
As direct consequence of Theorem 4.4 Corollary 4.5 indicates that if variation budgets are known, then the agent can choose the best hyper-parameter directly based on the variation budgets. The GapAve can be different depending on which regime the variation budgets fall into, as can be seen in Equations (54) and (55).
At the high level, we further explain how the window size W depends the variations of environment as follows. the nonstationarity is moderate and not significantly large, Corollary 4.5 indicates that for any Algorithm 1 achieves c-average suboptimal with polynomial trajectories (see the specific form in Equation (59) in Appendix [B2).. If the environment is near stationary and the variation is
relatively small, i.c., (A vP
+ + < Hd/K3, P + A < 1/VK, then the best window size W
38

---

and the policy restart period T are both K. This indicates that the agent does not need to take any
forgetting rules to handle the variation. Then the GapAve reduces to Ô (v (VH*PA(A+ d2)KK which matches the result under a stationary environment
Furthermore, it is interesting to consider special mildly changing environment, in which the representation o' stays identical and only the eabeeddib function n²* changes over time. The average dynamic suboptimality gap in Equation reduces to
R- R
MH(AP+AF)
The part (11) is the same as (11) in Equation
3 and by choosing the best window size of W
Hidt (A + d') ( part (7) becomes
δ 11'd A ( ( (HK)- A (a)))²)
(56)
Compared with the second regime in Equation (54). Equation (56) is much smaller, benefited from identical representation function Ø² In this way, samples in previous rounds can help to estimate the representation space so that W can be larger than W in terms of the order of K, which yields efficiency gain compared with changing o²
On the other hand, the nonstationarity significantly large, for example, scales linearly with K, then for each round, the previous samples cannot help to estimate current best policy. Thus, the best W and T are both 1, and the average dynamic suboptimality gap reduces to Ô (v AA d2) This indicates that for fixed small accuracy 2 matter how large the round K is, Algorithm can never achieve e-average suboptimality.
B.2 Proof of Corollary B.I (i.c., Detailed Version of Corollary 4.5
If variation budgets are known, for different variation budgets regimes, we can tune the hyper- parameters correspondingly to reach the optimality for both the term (/) that contains W and the term (T7) that contains T.
For the first term (1) in Equation 14). there are two regimes:
Small variation:
A
A
S
Hd K2
The best window size W is K, which means that the variation is pretty mild and the environment is near stationary. In this case, by choosing window size W K, the agent takes no forgetting rules to handle the variation. Then the first term (T) reduces
H4d2 A (A + d2), which matches the result under stationary environment
Then for any 2 0, with HK no more than Ô & A(A+t?)) term (1) S e.
Large variation: (A + +
Hd K2-
By choosing the window size W Hpppes (AV (AVP+ +10)=
- the term (I) reduces
to H228 A (2) (HK) (AvP A t
Since
(AVP 1 2HK, there exists
S s.t. (AVP + A < (2HK)T.
Then (I) $ 2H à (A+ d²) (HK) Then for any c 2 if 7 * with
HK no more than ò
d1 11 (A+ term (7) S.
We convert the sample complexity bound under infinite horizon MDPs dynamic suboptimality gap under episodic MDPs. We convert the regret bound under infinite horizon MDPs in Uehara et al. 2022 to the average dynamic suboptimality gap under episodic MDP.
Uchara et al 2022 the average
39

---

For the second term (IT) in Equation 14
there are three regimes elaborated as follows:
Small variation: (AP A
vK'
The best policy restart period is K, which means that the variation is pretty mild and the agent does not need to handle the variation. Then term (77) S VK"
2
-hhe for any
O, with HK more than Ô
112
term (77)
Moderate variation:
< (A P + A") K,
VK
The best policy restart period
K K3P + and the term (II) reduces to
2HK $ (A + A*)$.
-Since (A + AT) S 2HK, there exists S s.t. (A + +A²) (2HK)². Then
the term (1T) < 4H (HK) Then for any e 2 0, if 7 # 1, with HK no more
than Ō
term (11) E.
Large variation: K < (A" + A
The variation budgets scale linearly with K, which indicates that the nonstationarity of the environment significantly large and lasts for the entire rounds. Hence each round, the previous sample can not help to estimate the current best policy. So the best
policy restart period 7 = 1, and the second term (II) reduces to H + H OH)), which implies that Algorithm can never achieve small average dynamic suboptimality gap for any large K.
In conclusion, the first term is upper bounded by
H A
(A + +00) <
Hd
(A+d)),
(T)
K2
(57)
H A (A+ (HK) (AVP (AV++ + (AVP + ) > Hd
K2
and the second term is upper bounded by
2H
(A + S 1
VK
VK'
(IT) x
((A +AT)S,
1 VK
(AP A <K
(58)
H H(AP +
K << +
In addition, if the variation budgets are not significantly large, i.e. scale linearly with K, for any 2 Algorithm can achieve c-average dynamic suboptimality gap with at most polynomial samples. Specifically, if there exists a constant & < 1 such that the variation budgets satisfying (A + A+) s
(2H and (AVP + 2 < (2HK)*, then to achieve e-average dynamic suboptimality gap, i.e.,
40

---

GapAve S Algorithm 1 only needs to collect trajectories no more than d A(A+ de)
2
(AVP+ + +0) $
Hd K2
(AP P + + 5 1
if
vR"
12 d 1-1
1-9
(A + d
3
H²
e²
-
Hd
AVT + (A S 1 <
if
K²
VK*
H A(A + d
if ( <
Hd 1
VK < + A (HK)?;
12 d
1
A
(A + dR) T-7
1-7
Hd if
K2 < (AYP+ S (HKY,
< + + S (HK).
VK
(59)
B.3 A Special Case
In this subsection, we provide a characterization of a special case, where the representation d² stays identical and only the state-embedding function 1²* changes over time. In such a scenario, the variation budget A é [M],K]] 0 and the average dynamic suboptimality gap bound in Equation (4 reduces to
GapAve(Ki
H (A+ + V
H2W3A K2 (M(
VP
2H
3HT
(A [MI + Alm).o)))
VF +
W
K
z H.dd Ab (A + d2) 1 K-1 (A
HK - ( [HT,KK + A ATm)
where the last equation follows from the choice of the window side W and the policy restart period ( [H]K]] + (TH with known variation budgets.
δ Hàdd (A d))
(A VP (H)
C Proof of Theorem 5.1 and Detailed Comparison with Wei & Luo (0011
C.1 Proof of Theorem 5.1
Proof of Theorem 5.1 of W and here.
Before our formal proof, we first explain several notations on different choices
(W*, We denote W*
d + AVP + 1 and -
(K + A + 1)-8)
(W,r): Because W d ( + AVP + < d3 s Jw and 7*
δ (AP P + A + 1)- 1
< K < Jr. As a result, there exists a W E Tw such that
W < W' < 2W and 7 J, such that - < T 27.
41

---

(Wt, rt): (Wt, rt) denotes the set of best choices of the window size W and the policy restart period in feasible set that maximize Σ EAKA (W,
Then we can decompose the average dynamic suboptimality gap as
Gapawe (K)
Σ
VF
Vi
[E[K]
K
[K/M] Σ
[K/M] Σ
[K/M]]
Vp
E
(W.
F)
Σ 1=1
W,,, m)).
K
K
f=1
(1)
(II)
where the last inequality follows because if [T*} is the output of Algorithm 3 with the chosen
Jk=1
window size {W.) [r/an (W,, E
Ek=(G-1) V/J
>
MM K V holds.
k= k= 1)M+1
We next bound Terms (I) and (II) separately.
Term (I): We derive the following bound:
K
[K/M] Σ
V
,T,
(
x
H A
(A+ (A+ +
HadA
(A d2) W + [H] +
H2W 3
vP [H]
W
K
K2
2H
3H7
(A,, + ((())11))
K
(
(A+ (2) + HAdA
H2W+3 33 A
(A (+ [H]]K] +
A
VP (HI,KK)
W
K
K22
2H 3HT
+ 0
(A [m]i]]] + (p))
K
(m)) < H d' A (A
( R K K-a (AVP {
:) +
+0 + +1)+).
where (i) follows from Equation 14 (ii) follows from the definition of W and (dit) follows from the definition of W* at the beginning the proof.
Term (II): We derive the following bound:
[K/M]
K/M
1
[R(WWF) .F]
Σ
E [W,, 7
K
KR/M
[K/M]
Σ E [R((WW,,+))
Σ [W T()
< Ö(M (JT//M//K) ŌÖ(JJK) -
where (i) follows from the definition W and (ii) follows from Theorem 3.3 Bubeck Cesa- Bianchi 2012) with the adaptation that reward R; < M and the number of iteration is K/M combining the bounds on terms (I) and (II), we have
Then
(K)50 # a al (A- x- (A*P+a++1)+) () +0(2nk
+(A)+a++)))))
42

---

C.2 Detailed Comparison with Wei & Luo 2021
Based on the theoretical results Theorem 4.4 and taking Algorithm| PORTAL base algorithm, we can also use the black-box techniques called MASTER in Wei & Luo (2021) to handle the unknown variation budgets. But such an approach of MASTER+PORIAL turns out have larger average dynamic suboptimality gap than Algorithm
Denote = A + AVP +
To explain, first choose base algorithm with the suboptimality gap of Ó H A(A d')/K + v (A
k and W
K in Algorithm Then Algorithm [ reducess to
which satisfies Assumption 1 in Wei Luo (2021) with p(t)
H AAAAAAAA d²)/t and [La HHAAA (A A Then by Theorem 2 in Wei & Luo (021) p, the dynamic regret using
Ō(K Here, we find the order dependency on d, A the same as Theorem [.I and hence mainly focus on the order dependency on K and A in the following comparison. Such a bound on dynamic regret can be converted to the average dynamic suboptimality gap Ö(K à A Then it can obersed that for not too small variation budgets, i.e., A 2 O(1), the order dependency A is higher than that of Algorithm 3
MASTER+PORTAL can be upper-bounded by Ó(H d8 A (A + d²) Kå
Specifically, if we consider the special case when the representation stays identical and denote Á A VP + A", then the average dynamic suboptimality gap of MASTER+PORTAL is still Ö(K A With small modifications on the parameters, by following the analysis similar that of Theorem 5.1 and Appendix [..]] we can show that the average dynamic suboptimality gap of Algorithm satisfies Ö(K- A which is smaller than MASTER+PORTAL.
D Auxiliary Lemmas
In this section, we provide two lemmas that are commonly used for the analysis of MDP problems.
The following lemma (Dann et al. (017) is useful to measure the difference between two value functions under two MDPs and reward functions.
Lemma D.I. (Simulation Lemma). Suppose P1 and Ps are two MDPs and T1, 12 are the correspond- ing reward functions. Given a policy n, we have,
T Pirr (5h)
Σ
E " (Pain) Purrne
(n)) - r2(88, + (P1, - P2.c)
h'=h
E (P)n) o
[rilsh r2(sw, + (P1, W2.n)VV+L.P..
The following lemma a standard inequality in the regret analysis for linear MDPs reinforcement learning (see Lemma G.2 in Agarwal al. (2020b) and Lemma 10 Uehara et al. (2022)).
Lemma D.2 (Elliptical Potential Lemma). Consider sequence of d x d positive semidefinite matrices
XI...., XN with (x(),) < for all [N), Define Mo = Ag and M,, = Mn-1 + X,,. Then the following bound holds:
N dAo
Σ ir (X,M, S 2logde((MN) -2 log del((Mo)) 2d log
1+
43


Reviews:
[{"review_id": "vV2vwv8kIM", "reviewer": "Reviewer_niTs", "summary": "This paper studies reinforcement learning (RL) under non-stationary MDPs where the state transition and reward function changes across episodes. The paper focus on the low-rank MDP setting, in which the state transition function admits a low-rank decomposition. The authors propose a novel algorithm, namely PORTAL, along with theoretical results that characterize a bound for the average suboptimality gap of the learned policies over the episodes. Additionally, the paper also introduces an algorithm, namely Ada-PORTAL, for adaptive tuning of the hyperparameters of PORTAL.", "questions": "Below, I have a few questions and constructive feedback for the authors:\n\n1) In Section 3.2, I would suggest making it clearer what a “round” is. For instance, does each round have a fixed number of episodes?\n\n2) The current version of Section 4.1 is a bit hard to follow. For instance, in Step 1, terms such as “bonus term” and “target policy” are used without being previously defined.\n\n3) “However, in low-rank MDPs, the bonus term $b^k_k$ cannot serve as a point-wise uncertainty measure”. I suggest elaborating on why this is true.\n\n4) In Step 1, why the exploration policy takes two uniformly chosen actions? This algorithmic decision is not discussed or explained.\n\n5) I suggest writing comments in Algorithm 1 mentioning which lines correspond to Step 1, 2, and 3 for improving the clarity.\n\n6) In Algorithm 1, why states are indexed two times (subscript and superscript) with the time step $h$, e.g., $s_h^{k, h}$? What the indexes mean was not defined.\n\n7) What is the role of the coefficient $\\tilde{\\alpha_{k,W}}$? How is this selected?\n\n8) “Compared with the previous work using periodic restart (Fei et al., 2020), whose choice of $\\tau$ is based on a certain smooth visitation assumption, we remove such an assumption and hence our choice of $\\tau$ is applicable to more general model classes.” \nWhy can you remove this assumption? How is the value of $\\tau$ selected? Please elaborate on why it is necessary to reset the target policy every $\\tau$ episode.\n", "limitations": "Assumption 4.3 is not very realistic: in most MDPs, it is not possible to reach any state of the MDP in a single step. For instance, in a maze, the probability of reaching the end of the maze from the initial state in a single step is zero. Is this assumption also made in related works, e.g., Wei & Luo (2021)?\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The paper is the first to study non-stationarity in low-rank MDPs.\n\n* The proposed method is sound and results in a better suboptimality gap than previous related work (Wei & Luo, 2021).\n", "weaknesses": "* A few algorithmic decisions and assumptions require better explanation/justification to improve the clarity of the paper (see below).\n\n* The method relies on an assumption that is not very realistic (reachability) and should be better discussed (see Limitations below).\n\n* (Minor) The paper does not have an experimental section.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing helpful reviews! Below we address the reviewer’s comments, and we will revise the paper as suggested. If our response resolves your concerns to a satisfactory level, we kindly ask the reviewer to consider possibly raising the score of your evaluation.  \n\nQ1: Indicate what a “round” is.\n\nA1: Yes, each \"round\" has a fixed number of episodes.\n\nQ2: Revise current version of Section 4.1. Define “bonus term” and “target policy”.\n\nA2: The term \"bonus term\" is the level of uncertainty introduced to the actual reward to account for the estimation error, and hence this term leads to a near optimistic estimation of the value function. The term \"target policy\", as defined in Sec. 3.2, represents the policy generated by the algorithm, which is employed to assess the algorithm's performance through a comparison with a series of optimal policies.\n\nQ3: Elaborate why $\\hat{b}^k_h$ cannot serve as a point-wise uncertainty measure.\n\nA3: The main reason is because low-rank MDPs have unknown representations $\\phi(s,a)$ and performance guarantee on the estimation error of such unknown representation $\\phi(s,a)$ via MLE is given on the expected value over $(s,a)$ as in Lemma A.10. This further results in the following uncertainty bound on the expected value over $(s,a)$ (as in Lemma A.13), not on each individual $(s,a)$:\n$$\n  E_{(s_h,a_h) \\sim (P^k, \\pi)} [f_h^k(s_h,a_h)] \\leq E_{(s_{h-1},a_{h-1}) \\sim (P^k,\\pi)}[\\hat{b}^k_h(s_{h-1},a_{h-1})]+\\Delta\n$$\n\nwhere $f_h^k$ is total variation distance between estimated models and true models, i.e. estimation errors, and $\\Delta$ is a term related to the variation budget. \n\nQ4: In Step 1, why the exploration policy takes two uniformly chosen actions? \n\nA4: The main reason that exploration takes uniformly chosen actions is due to the fact that the representation is unknown in low-rank MDPs. So the agent needs to uniformly explore all actions and directions over the state-action space to get a comprehensive knowledge of the environment. Further, we note a single uniform step is not sufficient. Covariance matrix $U$ stores historical data information for future use of exploration. As explained above, the collected data is required to take at least one-step uniformly chosen actions. Subsequently, to effectively control estimation errors within target distribution, we use $U$ in the step back lemma (lemma A.12) to deal with distribution shifts, where importance sampling and one more uniform step is required. This leads the design of exploration policy with two-step uniformly chosen actions. \n\nQ5: Mention which lines correspond to Step 1, 2, and 3 in Alg. 1.\n\nA5: Step 1 corresponds to lines 5-8, Step 2 corresponds to line 9 (which calls Algorithm 2 E$^2$U), and Step 3 corresponds to lines 13-17.\n\nQ6: Define index of $s_h^{(k,h)}$ in Alg 1.\n\nA6: Subscript $h$ in ${s}_{h}^{(k,h)}$ indicates the data is collected at time step $h$ of each trajectory. Superscript $(k,h)$ indicates in which loop the data is collected (as in lines 3 and 4 of Algorithm 1, there are two loops regarding $k$ and $h$).\n\nQ7: What is the role of $\\tilde{\\alpha}_{k,W}$? \n\nA7: $\\tilde\\alpha_{k,W}$ quantifies data distribution shift from training data distribution to any target distribution. Consider Lemma A.13, where we bound estimation error of estimated model under target distribution (which is different from distribution of the training data used to estimate the model). $\\tilde{\\alpha}_{k,W}$ arises from applying the step back lemma to transmute target distribution back to distribution of training data. \n\nSpecially, $\\tilde\\alpha_{k,W}$ is determined by the upper bound of distribution shift level given by $O((A+d^2)\\log(kH|\\Phi||\\Psi|))$.\n\nQ8: Why can you remove assumption of [1]? How is $\\tau$ selected? Elaborate on necessity to reset target policy.\n\nA8: For the reason of removing assumption, refer to A3 to Reviewer FzWn. Regarding how to select $\\tau$, refer to A5 to Reviewer FzWn. We next elaborate the necessity to reset target policy every $\\tau$ episode. Intuitively, if environment (i.e., MDP transition and/or reward) changes significantly during some episodes, then samples far in the past are not so informative to represent current transitions/reward and hence are not very useful for updating the current policy. Hence, periodic restart helps to stick with the most relevant samples and stablize the algorithm's performance against the nonstationary drift of the environment.\n      \nQ9: The paper does not have an experimental section.\n\nA9: We will try our best to work out some experimental results.\n\nQ10: Assump. 4.3 is not very realistic. Is this assumption also made in related works, e.g., Wei and Luo (2021)?\n\nA10: Assumption 4.3 is introduced to deal with the nonstationarity. In order to improve the model estimation efficiency, here we need to apply historical data collected across different transition kernels for estimating the current model. To control such a model estimation error, both historical and current transition kernels should maintain non-zero transition probabilities (Assumption 4.3) to avoid singularity issues.\n\nNotably, Wei and Luo (2021) does not introduce an algorithm for nonstationary low-rank MDPs. Instead, for any types of MDPs, they require an off-the-shelf algorithm that performs effectively within nonstationary scenario with low variation as an input, and then uses a black-box approach to output an algorithm that performs efficiently under arbitrarily nonstationary environment without knowing variation budgets. In other words,  Wei and Luo (2021) would need our Algorithm 1 as an input in order to specialize to the nonstationary low-rank setting. This will make them also rely on our Assumption 4.3. \n\n[1] Jin, C., et. al (2020) Provably efficient reinforcement learning with linear function approximation. COLT.\n\n[2] Wei, C. Y., & Luo, H. (2021). Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. COLT."}, {"review_id": "E4LYa69oWO", "reviewer": "Reviewer_FzWn", "summary": "This paper investigates nonstationary RL in the context of episodic low-rank MDPs, where both transition kerns and rewards may change from round to round, and where the low-rank model contains unknown representations. The goal of this work is then to develop methods with low average dynamic suboptimality gap, which is a measure of how well the agent performs across all rounds. The authors start by proposing PORTAL, a base algorithm with three main ideas: (a) off-policy exploration for data collection which is particularly useful for non-stationarity; (b) the transfer of recent history data collected under previous different transition kernels for benefiting the estimation of the current model; and (c) updating target policies with periodic restart. PORTAL requires few hyperparameters, which greatly affect performance but may not be easy to set. for this reason, the authors also propose Ada-PORTAL, a second method that uses PORTAL as a subroutine and additionally treats the selection of the hyperparameters as a bandit problem. Under standard assumptions for low-rank MDPs and assuming that non-stationarity is not significant, the authors show that both methods achieve arbitrarily small average dynamic suboptimality gap with polynomial sample complexity.", "questions": "1. Why periodic restart in this work does not require a smooth visitation frequency assumption (compared to Fei et al., 2020)?\n2. The authors use EXP3-P in Ada-PORTAL. Is this choice critical or could other choices be made instead? Are there reasons to prefer one over the others?\n3. The authors stress the significance of \\tau and W. For the first algorithm W and \\tau, how exactly should the be selected? Could the authors provide clear guidelines?", "limitations": "None.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper extends the literature in low-rank MDPs by incorporating non-stationarity. In particular, the work advances the recent research on nonstationary linear (mixture) MDPs. Overall, the contribution is interesting, given the attention that both low-rank MDPs as well as non-stationarity have recently attracted.\n2. The paper makes assumptions that are consistent with both the low-rank MDP literature as well as the non-stationary RL literature.\n3. I was only able to check part of the derivations, which looked correct. I liked that the authors clarified how their work is different from recent works on non-stationarity or low-rank MDPs, not just in terms of the problem statement but also in terms of the new technical challenges.", "weaknesses": "1. I appreciate the fact that the authors provided insights and clarifications in several parts of the paper. But the paper is still hard to follow. I think what generally helps with such works is to provide an overview of the proof strategy, explain which exactly elements from prior works are used, and what elements are new. I acknowledge that the paper contains some discussions here and there, but I feel that a more structured approach would significantly improve the exposition.\n2. In its current form and presentation, I feel that the paper is only relevant to a very small audience of the ML/AI community.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing the helpful review! Below we address the reviewer’s comments, and we will revise the paper as suggested. If our response resolves your concerns to a satisfactory level, we kindly ask the reviewer to consider possibly raising the score of your evaluation. \n\nQ1: Provide an overview of the proof strategy.\n\nA1: Thanks for the comments. Please note that we have provided a proof sketch starting from line 451 in Appendix A. Based on the suggestions, we will further explain new elements as follows in the revision. \n\nIn step 1, we decompose the average dynamic suboptimal gap into three terms, which can be divided into two parts: $T_1$ and $T_2$.\n\nIn step 2, for part $T_1$ corresponding to model estimation errors, the proof contains two sub-steps. (i) First by Lemmas A.13 and A.15, we show model estimation errors can be bounded by the average of the truncated value functions of bonus terms plus a variation budgets term. In this sub-step, we provide a new nonstationary MLE guarantee as in Lemma A.10, which is novel as it characterizes the performance of MLE under nonstationary environment for the first time. We also develop the Nonstationary Step Back Lemma to handle distribution shift from the training data distribution to target data distribution. (ii) We then upper bound the average of the truncated value function as in Lemma A.18. Here, we adopt an auxiliary anchor representation for each block to deal with the challenge arising from time-varying representations when using standard elliptical potential based methods. This design of auxiliary anchor representation is new because of the unknown and nonstationary representations.\n\nIn step 3, we bound part $T_2$ corresponding to performance difference bound. The analysis of step 3 is inspired by [4], which explores policy optimization under tabular MDPs, and we extend it to low-rank MDPs. Our novelty lies in adopting different techniques to bound Eq. (11) (please refer to A3), which removes the Assumption 1 in [4]. \n\nQ2: The paper is only relevant to small audience of ML/AI community.\n\nA2: We will revise the paper as follows in order for the paper to be appreciated by a large set of audience in ML/AI community. (i) We will provide application examples to connect the nonstationary low-rank MDP model to realistic applications such as real-time online auctions, arm manipulation in robotics, autonomous driving, etc. In this way, we hope to attract a broad set of audience in these application areas. (ii) In order for the paper to be appreciated by a large set of audience who are interested in nonstationary RL, we will revise our description of the algorithm to help readers catch our main design ideas to handle nonstationarity and improve the sample efficiency. We will also explain our results on the sample complexity from the high level to make it easier for people to understand the performance guarantee. (iii) On the theory side, we will explain our proof techniques better and clearer to make them more accessible to people who will potentially use these techniques to study various other RL problems with nonstationarity, such as offline RL, multi-agent RL, RL with safety constraints, etc. \n\nQ3: Why this work does not require a smooth visitation assumption?\n\nA3:  Fei et al., (2020) [4] chose to make the following smooth visitation assumption in proving Lemma 5: \n$\\max_{s_j}\\sum_{s_{j+1}}|P^{\\pi^{(j)}}(s_{j+1}|s_j)-P^{\\pi^\\prime}(s_{j+1}|s_j)| \\leq C\\\\|\\pi^{(j)}-\\pi^\\prime\\\\|_{\\infty}$. \n\nInterestingly, we discovered that such an inequality can be proven to hold with equality as follows.\n\\begin{align*}\n    & \\quad \\max_{s_j}\\sum_{s_{j+1}}|P^{\\pi^{(j)}}(s_{j+1}|s_j)-P^{\\pi^\\prime}(s_{j+1}|s_j)|\\\\\\\\\n&=\\max_{s_j}\\sum_{s_{j+1}}|\\sum_{a}P(s_{j+1}|s_j,a)\\pi^{(j)}(a|s_j)-\\sum_{a}P(s_{j+1}|s_j,a)\\pi^\\prime(a|s_j)|\\\\\\\\\n&\\leq \\max_{s_j}\\sum_{s_{j+1}}\\sum_{a}P(s_{j+1}|s_j,a)|\\pi^{(j)}(a|s_j)-\\pi^\\prime(a|s_j)|\\\\\\\\\n&=\\max_{s_j}\\sum_{a}\\sum_{s_{j+1}}P(s_{j+1}|s_j,a)|\\pi^{(j)}(a|s_j)-\\pi^\\prime(a|s_j)|\\\\\\\\\n&=\\max_{s_j}\\sum_{a}|\\pi^{(j)}(a|s_j)-\\pi^\\prime(a|s_j)|=\\\\|\\pi^{(j)}-\\pi^\\prime\\\\|_{\\infty}\\\\\\\\\n\\end{align*}\n\nQ4: Is this choice of EXP3-P critical or could be made instead? Reasons?\n\nA4: We believe other choices can be made instead. In Ada-PORTAL, the selection of the hyper-parameters such as $W$ and $\\tau$ can be regarded as an adversarial bandit problem. In this paper, we choose EXP3-P because it is one of the most popular algorithms for adversarial bandits. Any other efficient algorithms for adversarial bandits, for example SAO in [5], can also be applied to serve the purpose. Given that SAO exhibits the same regret performance as EXP3-P (omitting the logarithmic term), there is no special preference on these two algorithms. \n\nQ5: The authors stress the significance of $\\tau$ and $W$. For the first algorithm $W$ and $\\tau$, how exactly should the be selected? Could the authors provide clear guidelines?\n\nA5: Thanks for the comments. Please note that in Appendix B, we explained how to select $W$ and $\\tau$ in detail. More specifically, Theorem 4.4 provides an upper bound on the average suboptimality gap $\\mathrm{Gap_{Ave}}(K)$ w.r.t. the values of $\\tau$ and $W$. We can then select their values to minimize such an upper bound. The optimal values of $\\tau$ and $W$ can be found in  Appendix B.\n\n[1] Cheung, W. C., et.al (2023). Nonstationary reinforcement learning: The blessing of (more) optimism. Management Science.\n\n[2] Cheung, W. C., et.al (2022). Hedging the drift: Learning to optimize under nonstationarity. Management Science, 68(3), 1696-1713.\n\n[3] Guo, X., et.al (2019). Learning mean-field games. NeurIPS 32.\n\n[4] Fei, Y.,  et.al (2020). Dynamic regret of policy optimization in non-stationary environments. NeurIPS 33.\n\n[5] Bubeck, Sébastien, and Aleksandrs (2012) Slivkins. The best of both worlds: Stochastic and adversarial bandits. COLT.\n"}, {"review_id": "TIp4oQSTWU", "reviewer": "Reviewer_ga5z", "summary": "This paper present an algorithm for solving non-stationary low-rank MDP. It also provide a theoretical analysis of their algorithm,", "questions": "See the 'weakness' section.", "limitations": "See the 'weakness' section.", "rating": 3, "confidence": 3, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "This is an interesting question. The presentation is clear.", "weaknesses": "I sketch through the results and the proof. I doubt that the proof might be wrong.  In page 14, the inequality (i) require the author to provide an upper bound of E_{P^*} f_h^k - E_{\\hat P}f_h^k. The paper says that inequality (i) holds since Lemma A.13 and Lemma A.15. However, none of the lemma is related with the term I mentioned above. Therefore, I am worried that the proof might be wrong.\n\nMore over, the writing of the proof can be improve, and the clearity of the paper have room for improvement. For example, it would be helpful to provide the definition of $\\lambda$ in the main part. It would also be helpful to mention that $W\\leq K$ in the main part.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing the helpful review! Below we address the reviewer’s comments.\n\nQ1: I sketch through the results and the proof. I doubt that the proof might be wrong. In page 14, the inequality (i) require the author to provide an upper bound of $E_{P^*,{\\pi^{\\star,k}}} f_h^k - E_{\\hat P,{\\pi^{\\star,k}}}f_h^k$.  The paper says that inequality (i) holds since Lemma A.13 and Lemma A.15. However, none of the lemma is related with the term I mentioned above. Therefore, I am worried that the proof might be wrong.\n\n\n\nA1: **We confirm that the proof is correct!** The term $E_{P^*,{\\pi^{\\star,k}}} f_h^k - E_{\\hat P,{\\pi^{\\star,k}}}f_h^k$ can indeed be upper bounded by using Lemma A.15. To see this, Lemma A.15 provides upper bounds on the value function difference between estimated models and true models for any generic reward. Now consider a specific reward function $r^k$, which takes the value $f_h^k$ at step $h$ and takes the value 0 at all other steps. For such a reward, we have $ V_{P^{\\star,k},r^k}^{\\pi^{\\star,k}}-V_{\\hat{P}^k,r^k}^{\\pi^{\\star,k}}=E_{P^*,{\\pi^{\\star,k}}} f_h^k - E_{\\hat P,{\\pi^{\\star,k}}}f_h^k$. \nIn this way, the bound in Lemma A.15 on \n$ V_{P^{\\star,k},r^k}^{\\pi^{\\star,k}}-V_{\\hat{P}^k,r^k}^{\\pi^{\\star,k}} $ \nbecomes a bound on \n$E_{P^*,{\\pi^{\\star,k}}} f_h^k - E_{\\hat P,{\\pi^{\\star,k}}}f_h^k$. \n\nQ2: More over, the writing of the proof can be improve, and the clearity of the paper have room for improvement. For example, it would be helpful to provide the definition of $\\lambda$ in the main part. It would also be helpful to mention that $W \\leq K$ in the main part.\n\nA2: Thanks for the suggestions. We will make our best efforts to improve both the clarity and readability of our paper in the revision. Specifically, regarding the regularizer $\\lambda$,\nwe have defined it in line 1 of Algorithm 1 and specified its value in line 285 in Theorem 4.4. We will further emphasize these in the revision. We will mention $W \\leq K$ as the reviewer suggested in the main part.\n\nFinally, if our response resolves your concerns to a satisfactory level, we kindly ask the reviewer to consider raising the score of your evaluation. Certainly, we are more than happy to answer any further questions that you may have during the discussion period. We thank the reviewer again for the helpful comments and suggestions for our work. "}, {"review_id": "4WpXHQ36U8", "reviewer": "Reviewer_5jBS", "summary": "The paper presents a new way to perform off-policy RL coupled with representation learning over non-stationary low-rank MDPs, both in a parameter-based and a parameter-free fashion. The paper proposes some interesting new algorithmic techniques to tackle this (off-policy\nexploration, data-transfer model learning, and target policy update with periodic restart).", "questions": "No questions", "limitations": "I didn't find any section where the limitations of the proposed method were addressed", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "# originality\nThe work seems quite original in both the analysis and the contribution. \n\n\n# quality \n\nThe quality of this work is satisfactory and the analysis is thoughtful.\n\n# clarity\n\nThe exposition is clear and neat, I would suggest presenting the algorithms differently (See weaknesses)\n \n\n# significance\n\nThe work seems to provide a significant contribution to the field, due to the several techniques it introduces.", "weaknesses": "My only comment is about the exposition of the algorithm. I would suggest not citing equations but reporting them, and providing the output of the subroutines.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing the helpful review! Below we address the reviewer’s comments.\n\nQ: My only comment is about the exposition of the algorithm. I would suggest not citing equations but reporting them, and providing the output of the subroutines.\n\nA: Thanks for the suggestions. We will revise the presentation of the algorithm as the reviewer suggested.\n\nFinally, we thank the reviewer again for the helpful comments and suggestions for our work. We are more than happy to answer any further questions that you may have during the discussion period.\n\n\n\n\n"}]

Author rebuttal:
Dear all reviewers,

We thank all the reviewers for providing the helpful review comments! 

We further thank Reviewers niTs, FzWn and 5jBS for your positive evaluation of our paper. We have responded to your specific questions and will revise our paper based on your comments. 

We also thank Reviewer ga5z for going through our proof, and want to clarify that the proof step you pointed out as the main concern is correct. Please see our response for detailed explanation. 

We thank all the reviewers again for your efforts!

Meta-review: This paper had strong support from a majority of its reviewers. The reviewers appreciated the soundness of the assumptions and the results, improvements in bounds and applicability (non-stationarity) over prior work and adequate placement of the surrounding literature.

Reviewer ga5z raised a concern regarding the proof, but did not respond to the authors' rebuttal. Additionally, we were unable to trace the origins of his concerns; so, we are setting aside the said review when evaluating the present work.

Therefore, we are happy to recommend the paper for acceptance.
Decision: Accept (poster)