稀疏模型变化下在线强化学习的自适应记忆
摘要
一篇强化学习论文提出了一种自适应记忆算法,在仅有一小部分奖励和转移条目发生变化时,选择性地复用过去部署中的观测,仅使用最近 O(1/ε) 次部署的数据,就能实现 Õ(√(ε/H)) 的长期平均差距。
arXiv:2611.21879v1 Announce Type: new
Abstract: We study the discounted reinforcement learning (RL) problem in a setting where the underlying environment changes between deployments. Each deployment provides $H$ observations from a fixed MDP. The reward function and transition kernel are fixed within each deployment. Across deployments, at most an $\epsilon >0$ fraction of the reward and transition kernel entries may change. In this setting, learning each model to deploy from scratch may discard useful observations from past deployments, whereas pooling all past observations can bias the estimates of entries that have already changed. We then propose an algorithm that for each state and action pair, selects how much history to reuse to estimate the reward and probabilities of the next state. We start with observations from the current deployment and add earlier deployment observations one at a time, the most recent first. After each addition, we check whether a single average reward agrees with the estimates from all histories considered until that point. We apply the same check to the distribution of next states. For each estimate, we leverage the last history that passes these aforementioned checks. The optimal control policy is then computed on top of the fitted MDP. We characterize the average gap between the optimal return and the return of the learner's policies over a finite number of deployments. We demonstrate that when $0< |S|\epsilon \leq 2$, with $|S|$ being the cardinality of the state space, our algorithm needs only the observations from the most recent $O(1/\epsilon)$ deployments, and achieves a long-run average gap of at most $\widetilde{O}(\sqrt{\epsilon/H})$.
查看缓存全文
缓存时间: 2026/11/19 03:35
# Adaptive Memory for Online Reinforcement Learningunder Sparse Model Changes
Source: [https://arxiv.org/html/2611.21879](https://arxiv.org/html/2611.21879)
Sukanya ModakLeonardo F\. Toso††thanks:Sreejeet Maity is with the Department of Electrical and Computer Engineering, North Carolina State University\. Sukanya Modak is with the Department of Electronics and Communication Engineering, RCC Institute of Information Technology\. Leonardo F\. Toso is with the Department of Electrical Engineering, Columbia University\. Emails:˜smaity2@ncsu\.edu,ece2024065@rcciit\.org\.in,leonardo\.toso@columbia\.edu\.
###### Abstract
We study the discounted reinforcement learning \(RL\) problem in a setting where the underlying environment changes between deployments\. Each deployment providesHHobservations from a fixed MDP\. The reward function and transition kernel are fixed within each deployment\. Across deployments, at most anϵ\>0\\epsilon\>0fraction of the reward and transition kernel entries may change\. In this setting, learning each model to deploy from scratch may discard useful observations from past deployments, whereas pooling all past observations can bias the estimates of entries that have already changed\. We then propose an algorithm that for each state and action pair, selects how much history to reuse to estimate the reward and probabilities of the next state\. We start with observations from the current deployment and add earlier deployment observations one at a time, the most recent first\. After each addition, we check whether a single average reward agrees with the estimates from all histories considered until that point\. We apply the same check to the distribution of next states\. For each estimate, we leverage the last history that passes these aforementioned checks\. The optimal control policy is then computed on top of the fitted MDP\. We characterize the*average gap*between the optimal return and the return of the learner’s policies over a finite number of deployments\. We demonstrate that when0<\|𝒮\|ϵ≤20<\|\\mathcal\{S\}\|\\epsilon\\leq 2, with\|𝒮\|\|\\mathcal\{S\}\|being the cardinality of the state space, our algorithm needs only the observations from the most recent𝒪\(1/ϵ\)\\mathcal\{O\}\(1/\\epsilon\)deployments, and achieves a*long\-run average gap*of at most𝒪~\(ϵ/H\)\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{\\epsilon/H\}\)\.
## IIntroduction
A control policy learned in one environment may perform poorly when that environment changes\. For example, a blocked route changes where a robot can move, while a shift in customer demand can change how much stock a retailer should order\[[1](https://arxiv.org/html/2611.21879#bib.bib7),[2](https://arxiv.org/html/2611.21879#bib.bib4)\]\. Such changes need not affect the entire model\. If only a few reward or transition entries change, past observations of the remaining entries still provide useful information about the current environment\. Learning the underlying deployed model from scratch may discard that information\. On the other hand, reusing all past observations can produce inaccurate and biased estimates of the entries that have already changed\. The problem is how to adaptively select which observations to reuse \(i\.e\., how to adapt the memory to the past observations\) when the learner does not know where the changes occurred\.
We study discounted infinite\-horizon reinforcement learning \(RL\) across a sequence of deployments\. A deployment is a period ofHHobservations during which the reward function and transition kernel are fixed, the deployment boundary is the known time at which the next period begins and the model may change\. The state and action spaces are shared across deployments\. At each boundary, at most anϵ\\epsilonfraction of the reward entries and anϵ\\epsilonfraction of the transition\-probability entries may change, as illustrated in Fig\.[1](https://arxiv.org/html/2611.21879#S2.F1)\. A change is local in this sense: it affects a small set of the model entries, although it may alter the optimal underlying policy\. The learner knows the change budgetϵ\\epsilonbut neither the changed entries nor their magnitudes\.
As observations arrive, the learner updates its policy to track the changing environment\. We measure performance by the average gap from each deployment’s optimal return, including during adaptation\. In particular, we ask the following question:*How much can selective reuse of past observations improve policy tracking under sparse model changes, and how much memory does it require?*
Related Work\.Learning across changing environments involves two closely related goals: adapting to model changes and reusing information from earlier environments\. The former is central to nonstationary RL, where existing methods account for model variation\[[3](https://arxiv.org/html/2611.21879#bib.bib3)\], use sliding windows with confidence widening\[[2](https://arxiv.org/html/2611.21879#bib.bib4)\], adapt to unknown nonstationarity\[[4](https://arxiv.org/html/2611.21879#bib.bib5)\], or restart after detecting changes\[[5](https://arxiv.org/html/2611.21879#bib.bib6)\]\. The latter underlies multitask learning, which exploits shared representations across related tasks\[[6](https://arxiv.org/html/2611.21879#bib.bib8),[7](https://arxiv.org/html/2611.21879#bib.bib9),[8](https://arxiv.org/html/2611.21879#bib.bib16)\], and related control methods that establish sample complexity benefits from sharing information across dynamical systems\[[9](https://arxiv.org/html/2611.21879#bib.bib21),[10](https://arxiv.org/html/2611.21879#bib.bib10),[11](https://arxiv.org/html/2611.21879#bib.bib11),[12](https://arxiv.org/html/2611.21879#bib.bib17)\]\. Bringing adaptation and reuse together, Meta\-RL learns policy updates\[[13](https://arxiv.org/html/2611.21879#bib.bib12)\], dynamics\-model priors\[[14](https://arxiv.org/html/2611.21879#bib.bib13)\], reusable model mixtures\[[15](https://arxiv.org/html/2611.21879#bib.bib18)\], or task representations\[[16](https://arxiv.org/html/2611.21879#bib.bib19)\]to facilitate adaptation, while domain randomization trains policies across varied simulator parameters\[[17](https://arxiv.org/html/2611.21879#bib.bib14),[18](https://arxiv.org/html/2611.21879#bib.bib15),[19](https://arxiv.org/html/2611.21879#bib.bib20)\]\. Our work exploits a specific source of shared structure: individual reward entries and transition rows can remain unchanged even when the environment as a whole changes\. With known deployment boundaries and sparse model changes, the learner selects a separate history for each component, allowing persistent components to benefit from past observations while adapting estimates of those that change\.
Our setting has known deployment boundaries and sparse changes in reward and transition entries\. We exploit*components that remain unaltered*across deployments by selecting a*separate history for each reward entry and transition row*\. These histories are used to fit the current model, and we evaluate the resulting policies against the current deployment’s optimal policy throughout adaptation\. A closely related approach uses local forgetting in replay buffers to adapt to localized reward changes in deep model\-based RL\[[1](https://arxiv.org/html/2611.21879#bib.bib7)\]\. Our results characterize the statistical benefits of a selective history reuse under independent sampling and exact planning\. We consider changes in both rewards and transitions and bound the average policy loss from the start of each deployment, including before the learner receives its first new observation\. Our contributions are as follows:
∙\\bulletAdaptive history selection\.We propose an algorithm that selects a history separately for each reward entry and transition row \(Section[III](https://arxiv.org/html/2611.21879#S3)\)\. For each state–action pair, the learner selects separate histories for estimating the mean reward and the distribution over next states\. It starts with the observations from the current deployment and adds earlier deployments one at a time, most recent first\. After each addition, it checks whether a single mean reward lies in every confidence interval constructed until that point\. It applies the same check to the next\-state distribution using the transition confidence sets\. For each estimate, it keeps the longest history that passes these checks and computes an optimal policy for the model fitted on top of the selected history\. The algorithm stores only state\-action visit counts, reward sums, and next state counts for each stored deployment\. We call this collection a*deployment summary*\.
∙\\bulletAverage policy\-loss bounds\.We establish expected and high\-probability bounds over any finite number of deployments \(Section[IV](https://arxiv.org/html/2611.21879#S4)\)\. The bounds account for the initial learning step where the learner has no past observations\. In addition, our bounds also accounts for the limit on retained history, and the adaptation to the sparse changes\. Our proof controls the accumulated estimation error across deployments\. For0<ϵ≤10<\\epsilon\\leq 1, storingB=⌈ϵ−1⌉B=\\lceil\\epsilon^\{\-1\}\\rceilcompleted summaries provides a long\-run average policy loss of𝒪~\(ϵ/H\)\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{\\epsilon/H\}\)in the regime\|𝒮\|ϵ≤2\|\\mathcal\{S\}\|\\epsilon\\leq 2, where\|𝒮\|\|\\mathcal\{S\}\|denotes the cardinality of the state space\. The number of completed summariesBBis selected to balance the contribution from limited history with respect to the model changes\.
## IIBackground and Problem Formulation
Consider a discounted MDPℳ=\(𝒮,𝒜,𝒫,R,γ\)\\mathcal\{M\}=\(\\mathcal\{S\},\\mathcal\{A\},\\mathcal\{P\},R,\\gamma\)with finite nonempty state and action spaces, transition kernel𝒫\\mathcal\{P\}, mean rewardR\(s,a\)=𝔼\[r∣s,a\]R\(s,a\)=\\mathbb\{E\}\[r\\mid s,a\], andγ∈\(0,1\)\\gamma\\in\(0,1\)\. Letd:=\|𝒮\|\|𝒜\|d:=\|\\mathcal\{S\}\|\|\\mathcal\{A\}\|and letΔ\(ℬ\)\\Delta\(\\mathcal\{B\}\)denote the probability distributions on a finite setℬ\\mathcal\{B\}\. Assume\|r\|≤R¯\|r\|\\leq\\bar\{R\}almost surely for a knownR¯≥1\\bar\{R\}\\geq 1\. The standard objective is to maximize𝔼𝒫,π\[∑t=0∞γtR\(st,at\)∣s0=s\]\\mathbb\{E\}\_\{\\mathcal\{P\},\\pi\}\[\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{t=0\}^\{\\infty\}\\gamma^\{t\}R\(s\_\{t\},a\_\{t\}\)\\mid s\_\{0\}=s\]over stationary policiesπ:𝒮→Δ\(𝒜\)\\pi:\\mathcal\{S\}\\to\\Delta\(\\mathcal\{A\}\)for every initial statess\. A stationary deterministic optimal policy exists\[[20](https://arxiv.org/html/2611.21879#bib.bib1)\]\.
In this paper, we study successive deployments in which the MDP remains fixed within each deployment but may undergo sparse reward and transition changes between deployments\. Our goal is*small average discounted policy loss*through selective reuse of past data, without knowing which components have changed\. We formalize this setting next\.
Fig\. 1:Sparse reward and transition changes across deploymentsℳk−2,ℳk−1,ℳk\\mathcal\{M\}\_\{k\-2\},\\mathcal\{M\}\_\{k\-1\},\\mathcal\{M\}\_\{k\}\. Red cells are the entries that change\.■\\blacksquareMDPs and Deployment Structure\.The environment is held fixed during deployments containingH≥1H\\geq 1observation times each\. Deploymentkk, wherek=0,1,…k=0,1,\\ldots, is described by the MDPℳk=\(𝒮,𝒜,𝒫k,Rk,γ\)\.\\mathcal\{M\}\_\{k\}=\(\\mathcal\{S\},\\mathcal\{A\},\\mathcal\{P\}\_\{k\},R\_\{k\},\\gamma\)\.The state space𝒮\\mathcal\{S\}, action space𝒜\\mathcal\{A\}, and discount factorγ\\gammaare shared across deployments, while the transition kernel𝒫k\\mathcal\{P\}\_\{k\}and mean reward functionRkR\_\{k\}may change between consecutive deployments\. For each\(s,a\)∈𝒮×𝒜\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\},𝒫k\(⋅∣s,a\)∈Δ\(𝒮\)\\mathcal\{P\}\_\{k\}\(\\cdot\\mid s,a\)\\in\\Delta\(\\mathcal\{S\}\)specifies the distribution of the successor state during deploymentkk\. Similarly,Rk:𝒮×𝒜→\[−R¯,R¯\]R\_\{k\}:\\mathcal\{S\}\\times\\mathcal\{A\}\\to\[\-\\bar\{R\},\\bar\{R\}\]specifies the expected reward associated with each state–action pair\. The almost\-sure reward bound\|r\|≤R¯\|r\|\\leq\\bar\{R\}holds uniformly across deployments, with the same known constantR¯\\bar\{R\}\. We index observation times within deploymentkkbyh∈\{0,…,H−1\}h\\in\\\{0,\\ldots,H\-1\\\}and use\(k,h\)\(k,h\)to identify an observation time\. Thus,𝒫k\\mathcal\{P\}\_\{k\}andRkR\_\{k\}remain unchanged throughout theseHHobservation times, and any change occurs at a deployment boundary\. Both𝒫k\\mathcal\{P\}\_\{k\}andRkR\_\{k\}are unknown to the learner\. The learner knowsHHand the deployment boundaries, but does not observe which model entries change or the magnitudes of those changes\. Observations collected in earlier deployments may be retained and reused when adapting to the current MDP\. We impose sparsity on consecutive changes as follows\.
###### Assumption 1\.
\(Sparse Changes in Model Entries\)For a knownϵ∈\[0,1\]\\epsilon\\in\[0,1\]and eachk≥0k\\geq 0, define𝒞kR:=\{\(s,a\)∈𝒮×𝒜:Rk\+1\(s,a\)≠Rk\(s,a\)\},ℰkP:=\{\(s,a,s′\)∈𝒮×𝒜×𝒮:𝒫k\+1\(s′∣s,a\)≠𝒫k\(s′∣s,a\)\}\.\\mathcal\{C\}\_\{k\}^\{R\}:=\\big\\\{\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}:R\_\{k\+1\}\(s,a\)\\neq R\_\{k\}\(s,a\)\\big\\\},\\mathcal\{E\}\_\{k\}^\{P\}:=\\big\\\{\(s,a,s^\{\\prime\}\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\\times\\mathcal\{S\}:\\mathcal\{P\}\_\{k\+1\}\(s^\{\\prime\}\\mid s,a\)\\neq\\mathcal\{P\}\_\{k\}\(s^\{\\prime\}\\mid s,a\)\\big\\\}\.At every deployment boundary,\|𝒞kR\|≤ϵd,\|ℰkP\|≤ϵ\|𝒮\|d\.\|\\mathcal\{C\}\_\{k\}^\{R\}\|\\leq\\epsilon d,\\hskip 2\.84526pt\|\\mathcal\{E\}\_\{k\}^\{P\}\|\\leq\\epsilon\|\\mathcal\{S\}\|d\.
Assumption[1](https://arxiv.org/html/2611.21879#Thmassumption1)bounds\|𝒞kR\|\|\\mathcal\{C\}\_\{k\}^\{R\}\|and\|ℰkP\|\|\\mathcal\{E\}\_\{k\}^\{P\}\|\. Changes may have any admissible magnitude, and their locations may vary or recur across boundaries\. Let𝒞kP:=\{x:Pk\+1\(⋅∣x\)≠Pk\(⋅∣x\)\}\\mathcal\{C\}\_\{k\}^\{P\}:=\\\{x:P\_\{k\+1\}\(\\cdot\\mid x\)\\neq P\_\{k\}\(\\cdot\\mid x\)\\\}\. Each changed row has at least two changed entries, so Lemma[1](https://arxiv.org/html/2611.21879#Thmlemma1)gives\|𝒞kP\|≤ϑd\|\\mathcal\{C\}\_\{k\}^\{P\}\|\\leq\\vartheta d, whereϑ:=min\{1,\|𝒮\|ϵ/2\}\\vartheta:=\\min\\\{1,\|\\mathcal\{S\}\|\\epsilon/2\\\}\.
■\\blacksquareObservation Model\.At observation timeh∈\{0,…,H−1\}h\\in\\\{0,\\ldots,H\-1\\\}of deploymentkk, the learner receives a tuple
\(sk,h,ak,h,rk,h,sk,h′\)∈𝒮×𝒜×\[−R¯,R¯\]×𝒮\.\\displaystyle\(s\_\{k,h\},a\_\{k,h\},r\_\{k,h\},s^\{\\prime\}\_\{k,h\}\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\\times\[\-\\bar\{R\},\\bar\{R\}\]\\times\\mathcal\{S\}\.\(1\)Here,\(sk,h,ak,h\)\(s\_\{k,h\},a\_\{k,h\}\)is the sampled state–action pair,rk,hr\_\{k,h\}is the observed reward, andsk,h′s^\{\\prime\}\_\{k,h\}is the sampled successor state\. We use the following independent sampling model\.
###### Assumption 2\.
\(Observation Tuples\)The environment sequence is fixed independently of the observation noise\. Conditional on this sequence, the tuples are independent across\(k,h\)\(k,h\), and\(sk,h,ak,h\)\(s\_\{k,h\},a\_\{k,h\}\)is drawn fromνk\\nu\_\{k\}, whereνk\(s,a\)≥v\>0\\nu\_\{k\}\(s,a\)\\geq v\>0for every\(s,a\)∈𝒮×𝒜\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\. Given\(sk,h,ak,h\)=\(s,a\)\(s\_\{k,h\},a\_\{k,h\}\)=\(s,a\), the rewardrk,hr\_\{k,h\}has meanRk\(s,a\)R\_\{k\}\(s,a\)and the successor statesk,h′s^\{\\prime\}\_\{k,h\}has distribution𝒫k\(⋅∣s,a\)\\mathcal\{P\}\_\{k\}\(\\cdot\\mid s,a\)\. The constantsvvandR¯\\bar\{R\}are known\. The reward and next state within a tuple may be dependent\.
The sampling distributionsνk\\nu\_\{k\}may vary across deployments and be unknown, withv≤1/dv\\leq 1/d\. The bounds hold for fixed environment sequences and conditionally for exogenous random ones\. Under Assumption[2](https://arxiv.org/html/2611.21879#Thmassumption2), overlapping histories may be dependent because they share tuples\. Before observing tuple\(k,h\)\(k,h\), the learner computesπk,h\\pi\_\{k,h\}from retained past data and the firsthhtuples of deploymentkk\.
### II\-APolicy Values and Discounted Occupancies
Fix an initial distributionρ∈Δ\(𝒮\)\\rho\\in\\Delta\(\\mathcal\{S\}\)common to all deployments\. For a stationary policyπ\\pi, defineVkπ\(s\):=𝔼𝒫k,π\[∑t=0∞γtRk\(st,at\)∣s0=s\]V\_\{k\}^\{\\pi\}\(s\):=\\mathbb\{E\}\_\{\\mathcal\{P\}\_\{k\},\\pi\}\[\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{t=0\}^\{\\infty\}\\gamma^\{t\}R\_\{k\}\(s\_\{t\},a\_\{t\}\)\\mid s\_\{0\}=s\], where trajectories evolve underπ\\piin the fixed MDPℳk\\mathcal\{M\}\_\{k\}\. The expected return fromρ\\rhoand its optimal value areJkρ\(π\):=ρ⊤VkπJ\_\{k\}^\{\\rho\}\(\\pi\):=\\rho^\{\\top\}V\_\{k\}^\{\\pi\}andJkρ,∗:=maxπJkρ\(π\)J\_\{k\}^\{\\rho,\*\}:=\\max\_\{\\pi\}J\_\{k\}^\{\\rho\}\(\\pi\), respectively\. Sinceℳk\\mathcal\{M\}\_\{k\}is finite and discounted, a stationary deterministic optimal policyπk∗\\pi\_\{k\}^\{\*\}exists and satisfiesJkρ\(πk∗\)=Jkρ,∗J\_\{k\}^\{\\rho\}\(\\pi\_\{k\}^\{\*\}\)=J\_\{k\}^\{\\rho,\*\}\. To quantify visitation underπ\\pistarting froms0∼ρs\_\{0\}\\sim\\rho, define the normalized discounted occupancydρ,kπ\(s,a\):=\(1−γ\)∑t=0∞γtℙρ,𝒫k,π\(st=s,at=a\)d\_\{\\rho,k\}^\{\\pi\}\(s,a\):=\(1\-\\gamma\)\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{t=0\}^\{\\infty\}\\gamma^\{t\}\\mathbb\{P\}\_\{\\rho,\\mathcal\{P\}\_\{k\},\\pi\}\(s\_\{t\}=s,a\_\{t\}=a\)\. These visitation weights satisfy∑s,adρ,kπ\(s,a\)=1\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{s,a\}d\_\{\\rho,k\}^\{\\pi\}\(s,a\)=1and hence form a probability distribution on𝒮×𝒜\\mathcal\{S\}\\times\\mathcal\{A\}\.
###### Assumption 3\.
\(Occupancy Bound\)There exists a knownκ∈\[1,d\]\\kappa\\in\[1,d\]such that, for every deploymentkk, stationary policyπ\\pi, and\(s,a\)∈𝒮×𝒜\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\},dρ,kπ\(s,a\)≤κd\.d\_\{\\rho,k\}^\{\\pi\}\(s,a\)\\leq\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}\}\.
Assumption[3](https://arxiv.org/html/2611.21879#Thmassumption3)bounds discounted policy occupancies under𝒫k\\mathcal\{P\}\_\{k\}, separately from the sampling coverage in Assumption[2](https://arxiv.org/html/2611.21879#Thmassumption2)\. Since occupancies are probability distributions,κ=d\\kappa=dis always valid; smallerκ\\kappaimproves the guarantees under sparse changes\. Define the policy loss in deploymentkkbyℓkρ\(π\):=Jkρ,∗−Jkρ\(π\)\\ell\_\{k\}^\{\\rho\}\(\\pi\):=J\_\{k\}^\{\\rho,\*\}\-J\_\{k\}^\{\\rho\}\(\\pi\)\. The reward bound gives0≤ℓkρ\(π\)≤2R¯/\(1−γ\)0\\leq\\ell\_\{k\}^\{\\rho\}\(\\pi\)\\leq 2\\bar\{R\}/\(1\-\\gamma\)\. ForK≥1K\\geq 1deployments, define the average policy loss and its expectation by
ℒK,Hρ:=1KH∑k=0K−1∑h=0H−1ℓkρ\(πk,h\),ℛK,Hρ:=𝔼\[ℒK,Hρ\]\.\\mathcal\{L\}\_\{K,H\}^\{\\rho\}:=\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{KH\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{KH\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{KH\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{KH\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{KH\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{KH\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{KH\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{KH\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{KH\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{KH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{KH\}\}\}\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{k=0\}^\{K\-1\}\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{h=0\}^\{H\-1\}\\ell\_\{k\}^\{\\rho\}\(\\pi\_\{k,h\}\),\\hskip 2\.84526pt\\mathcal\{R\}\_\{K,H\}^\{\\rho\}:=\\mathbb\{E\}\[\\mathcal\{L\}\_\{K,H\}^\{\\rho\}\]\.\(2\)Each summand evaluatesπk,h\\pi\_\{k,h\}in the fixed MDPℳk\\mathcal\{M\}\_\{k\}from the common initial distributionρ\\rho\. Thus, the average includes the policy available at the start of each deployment and every policy computed during adaptation\. The expectation is over the observation randomness and any randomness in the environment sequence\.
###### Problem 1\.
Suppose Assumptions[1](https://arxiv.org/html/2611.21879#Thmassumption1)–[3](https://arxiv.org/html/2611.21879#Thmassumption3)hold\. Construct a causal learner that reuses past observations without knowing which model entries change\. BoundℛK,Hρ\\mathcal\{R\}\_\{K,H\}^\{\\rho\}for everyK≥1K\\geq 1\. For a fixed learner and deployment lengthHH, also boundJHρ:=lim supK→∞ℛK,Hρ,J\_\{H\}^\{\\rho\}:=\\limsup\_\{K\\to\\infty\}\\mathcal\{R\}\_\{K,H\}^\{\\rho\},with explicit dependence on the entry\-change fractionϵ\\epsilon\.
## IIIOur Proposed Algorithm
In this section, we develop an adaptive history estimator for reusing data across deployments\. A change to one reward entry or transition row need not invalidate past data for other components\. A short common history discards*useful observations for unchanged components*, while a long one can*bias estimates of changed components*\. We therefore select histories*separately*for each reward entry and transition row\. To choose histories without knowing change times, we use the fact that estimates of an unchanged component should agree up to sampling noise\. The confidence sets quantify this uncertainty, and we extend histories while their intersection remains nonempty\. The learner then fits a valid MDP within the selected intersections and computes a stationary optimal policy before the next observation\. We first define the candidate histories and their empirical estimates\.
■\\blacksquareCandidate Histories and Empirical Estimates\.Fix an integer history capB≥1B\\geq 1and a confidence parameterδ∈\(0,1\)\\delta\\in\(0,1\)\. The capBBlimits the number of completed deployments available for reuse\. Define
L:=log8\|𝒮\|\|𝒜\|\(B\+1\)\(H\+1\)δ,Λ:=\|𝒮\|log2\+L\.L:=\\log\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{8\|\\mc\{S\}\|\|\\mc\{A\}\|\(B\+1\)\(H\+1\)\}\{\\delta\}\}\},\\hskip 2\.84526pt\\Lambda:=\|\\mathcal\{S\}\|\\log 2\+L\.\(3\)The factorLLaccounts for simultaneous confidence bounds over histories, state–action pairs, and observation times;Λ\\Lambdaadditionally accounts for the dimension of transition rows\. At\(k,h\)\(k,h\), write\(∙\)≜⋃j=k−mk−1\{\(j,u\):0≤u<H\}\(\{\\color\[rgb\]\{0\.7,0,0\}\\bullet\}\)\\triangleq\{\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcup$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcup$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\bigcup$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\bigcup$\}\}\}\}\\displaylimits\}\_\{j=k\-m\}^\{k\-1\}\\\{\(j,u\):0\\leq u<H\\\}for the indices from the lastmmcompleted deployments\. Including the firsthhobservation indices from deploymentkkgives the candidate history as follows:
𝒲k,h\(m\)\\displaystyle\\mathcal\{W\}\_\{k,h\}^\{\(m\)\}:=\(∙\)∪\{\(k,u\):0≤u<h\},\\displaystyle:=\(\{\\color\[rgb\]\{0\.7,0,0\}\\bullet\}\)\\cup\\\{\(k,u\):0\\leq u<h\\\},\(4\)where0≤m≤min\{B,k\}0\\leq m\\leq\\min\\\{B,k\\\}\. All included observations precede\(k,h\)\(k,h\), withm=0m=0using only data from deploymentkk\. For each\(s,a\)∈𝒮×𝒜\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}, define the visit count
Nk,h\(m\)\(s,a\):=∑\(j,u\)∈𝒲k,h\(m\)𝟏\{\(sj,u,aj,u\)=\(s,a\)\}\.N\_\{k,h\}^\{\(m\)\}\(s,a\):=\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{\(j,u\)\\in\\mathcal\{W\}\_\{k,h\}^\{\(m\)\}\}\\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}\.\(5\)This count determines the number of observations contributing to the estimates for\(s,a\)\(s,a\)\. ForNk,h\(m\)\(s,a\)\>0N\_\{k,h\}^\{\(m\)\}\(s,a\)\>0, define the empirical reward mean
R¯k,h\(m\)\(s,a\):=∑\(j,u\)∈𝒲k,h\(m\)𝟏\{\(sj,u,aj,u\)=\(s,a\)\}rj,uNk,h\(m\)\(s,a\),\\overline\{R\}\_\{k,h\}^\{\(m\)\}\(s,a\):=\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\}\)=\(s,a\)\\\}r\_\{j,u\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\},\(6\)and, for eachs′∈𝒮s^\{\\prime\}\\in\\mathcal\{S\}, the empirical transition probability
𝒫¯k,h\(m\)\(s′∣s,a\):=∑\(j,u\)∈𝒲k,h\(m\)𝟏\{\(sj,u,aj,u,s′j,u\)=\(s,a,s′\)\}Nk,h\(m\)\(s,a\)\.\\overline\{\\mathcal\{P\}\}\_\{k,h\}^\{\(m\)\}\(s^\{\\prime\}\\mid s,a\):=\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{ \\sum\_\{\(j,u\)\\in\\mc W\_\{k,h\}^\{\(m\)\}\} \\mathbf\{1\}\\\{\(s\_\{j,u\},a\_\{j,u\},s'\_\{j,u\}\)=\(s,a,s'\)\\\}\}\{N\_\{k,h\}^\{\(m\)\}\(s,a\)\}\}\}\.\(7\)ForNk,h\(m\)\(s,a\)\>0N\_\{k,h\}^\{\(m\)\}\(s,a\)\>0, define the confidence radiibk,hR,\(m\)\(s,a\):=R¯\(2L/Nk,h\(m\)\(s,a\)\)1/2b\_\{k,h\}^\{R,\(m\)\}\(s,a\):=\\bar\{R\}\(2L/N\_\{k,h\}^\{\(m\)\}\(s,a\)\)^\{1/2\}andbk,hP,\(m\)\(s,a\):=\(2Λ/Nk,h\(m\)\(s,a\)\)1/2b\_\{k,h\}^\{P,\(m\)\}\(s,a\):=\(2\\Lambda/N\_\{k,h\}^\{\(m\)\}\(s,a\)\)^\{1/2\}\. The reward radius controls the absolute deviation of the empirical mean fromRk\(s,a\)R\_\{k\}\(s,a\), while the transition radius controls theℓ1\\ell\_\{1\}deviation of the empirical row from𝒫k\(⋅∣s,a\)\\mathcal\{P\}\_\{k\}\(\\cdot\\mid s,a\)\. These guarantees hold with high probability when the corresponding component remains unchanged throughout the candidate history\. Now, we define the reward confidence interval as
Ik,hR,\(m\)\(s,a\):=\{z∈\[−R¯,R¯\]:\|z−R¯k,h\(m\)\(s,a\)\|≤bk,hR,\(m\)\(s,a\)\}\.\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle I\_\{k,h\}^\{R,\(m\)\}\(s,a\):=\\big\\\{z\\in\[\-\\bar\{R\},\\bar\{R\}\]:\|z\-\\overline\{R\}\_\{k,h\}^\{\(m\)\}\(s,a\)\|\\leq b\_\{k,h\}^\{R,\(m\)\}\(s,a\)\\big\\\}\.$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle I\_\{k,h\}^\{R,\(m\)\}\(s,a\):=\\big\\\{z\\in\[\-\\bar\{R\},\\bar\{R\}\]:\|z\-\\overline\{R\}\_\{k,h\}^\{\(m\)\}\(s,a\)\|\\leq b\_\{k,h\}^\{R,\(m\)\}\(s,a\)\\big\\\}\.$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle I\_\{k,h\}^\{R,\(m\)\}\(s,a\):=\\big\\\{z\\in\[\-\\bar\{R\},\\bar\{R\}\]:\|z\-\\overline\{R\}\_\{k,h\}^\{\(m\)\}\(s,a\)\|\\leq b\_\{k,h\}^\{R,\(m\)\}\(s,a\)\\big\\\}\.$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle I\_\{k,h\}^\{R,\(m\)\}\(s,a\):=\\big\\\{z\\in\[\-\\bar\{R\},\\bar\{R\}\]:\|z\-\\overline\{R\}\_\{k,h\}^\{\(m\)\}\(s,a\)\|\\leq b\_\{k,h\}^\{R,\(m\)\}\(s,a\)\\big\\\}\.$\}\}\}\(8\)As in \([8](https://arxiv.org/html/2611.21879#S3.E8)\), we define the transition confidence set as
ℬk,hP,\(m\)\(s,a\):=\{p∈Δ\(𝒮\):‖p−𝒫¯k,h\(m\)\(⋅∣s,a\)‖1≤bk,hP,\(m\)\(s,a\)\}\.\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\begin\{aligned\} \\mathcal\{B\}\_\{k,h\}^\{P,\(m\)\}\(s,a\):=\\big\\\{p\\in\\Delta\(\\mathcal\{S\}\):\\left\\lVert p\-\\overline\{\\mathcal\{P\}\}\_\{k,h\}^\{\(m\)\}\(\\cdot\\mid s,a\)\\right\\rVert\_\{1\}\\leq b\_\{k,h\}^\{P,\(m\)\}\(s,a\)\\big\\\}\.\\end\{aligned\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\begin\{aligned\} \\mathcal\{B\}\_\{k,h\}^\{P,\(m\)\}\(s,a\):=\\big\\\{p\\in\\Delta\(\\mathcal\{S\}\):\\left\\lVert p\-\\overline\{\\mathcal\{P\}\}\_\{k,h\}^\{\(m\)\}\(\\cdot\\mid s,a\)\\right\\rVert\_\{1\}\\leq b\_\{k,h\}^\{P,\(m\)\}\(s,a\)\\big\\\}\.\\end\{aligned\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\begin\{aligned\} \\mathcal\{B\}\_\{k,h\}^\{P,\(m\)\}\(s,a\):=\\big\\\{p\\in\\Delta\(\\mathcal\{S\}\):\\left\\lVert p\-\\overline\{\\mathcal\{P\}\}\_\{k,h\}^\{\(m\)\}\(\\cdot\\mid s,a\)\\right\\rVert\_\{1\}\\leq b\_\{k,h\}^\{P,\(m\)\}\(s,a\)\\big\\\}\.\\end\{aligned\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\begin\{aligned\} \\mathcal\{B\}\_\{k,h\}^\{P,\(m\)\}\(s,a\):=\\big\\\{p\\in\\Delta\(\\mathcal\{S\}\):\\left\\lVert p\-\\overline\{\\mathcal\{P\}\}\_\{k,h\}^\{\(m\)\}\(\\cdot\\mid s,a\)\\right\\rVert\_\{1\}\\leq b\_\{k,h\}^\{P,\(m\)\}\(s,a\)\\big\\\}\.\\end\{aligned\}$\}\}\}\(9\)ForNk,h\(m\)\(s,a\)=0N\_\{k,h\}^\{\(m\)\}\(s,a\)=0, setIk,hR,\(m\)\(s,a\)=\[−R¯,R¯\]I\_\{k,h\}^\{R,\(m\)\}\(s,a\)=\[\-\\bar\{R\},\\bar\{R\}\]andℬk,hP,\(m\)\(s,a\)=Δ\(𝒮\)\\mathcal\{B\}\_\{k,h\}^\{P,\(m\)\}\(s,a\)=\\Delta\(\\mathcal\{S\}\), so the history imposes only the known reward range and transition stochasticity\.
Algorithm 1Adaptive History Model Learning1:Observations per deployment
HH; maximum number of retained past deployments
BB; confidence parameter
δ\\delta; discount factor
γ\\gamma; state and action spaces
𝒮,𝒜\\mathcal\{S\},\\mathcal\{A\}\.
2:Compute
L,ΛL,\\Lambdausing \([3](https://arxiv.org/html/2611.21879#S3.E3)\)\.
3:for
k=0,1,…k=0,1,\\ldotsdo
4:Reset the current\-deployment visit counts \([5](https://arxiv.org/html/2611.21879#S3.E5)\), and the reward sums and next\-state counts used in \([6](https://arxiv.org/html/2611.21879#S3.E6)\)–\([7](https://arxiv.org/html/2611.21879#S3.E7)\)\.
5:for
h=0,…,H−1h=0,\\ldots,H\-1do
6:Construct candidate confidence sets for all
\(s,a\)∈𝒮×𝒜\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}and
m=0,…,min\{B,k\}m=0,\\ldots,\\min\\\{B,k\\\}using \([6](https://arxiv.org/html/2611.21879#S3.E6)\)–\([9](https://arxiv.org/html/2611.21879#S3.E9)\), with the zero\-count convention\.
7:Form the confidence intersections using \([10](https://arxiv.org/html/2611.21879#S3.E10)\)\.
8:Select the history indices using \([11](https://arxiv.org/html/2611.21879#S3.E11)\)–\([12](https://arxiv.org/html/2611.21879#S3.E12)\)\.
9:Construct
R^k,h,𝒫^k,h\\widehat\{R\}\_\{k,h\},\\widehat\{\\mathcal\{P\}\}\_\{k,h\}using \([13](https://arxiv.org/html/2611.21879#S3.E13)\)–\([14](https://arxiv.org/html/2611.21879#S3.E14)\)\.
10:Output stationary optimal policy
πk,h\\pi\_\{k,h\}using \([15](https://arxiv.org/html/2611.21879#S3.E15)\)\.
11:Receive data tuple \([1](https://arxiv.org/html/2611.21879#S2.E1)\) and update statistics\.
12:endfor
13:Store the current summary and keep the latest
BB\.
14:endfor
■\\blacksquareAdaptive History Selection\.The reward mean and transition row at\(s,a\)∈𝒮×𝒜\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}may change at different boundaries, so we select their histories separately by intersecting confidence sets over nested windows:
Jk,hR,\(m\)\(s,a\):=⋂ℓ=0mIk,hR,\(ℓ\)\(s,a\),𝒥k,hP,\(m\)\(s,a\):=⋂ℓ=0mℬk,hP,\(ℓ\)\(s,a\)\.\\displaystyle\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle J\_\{k,h\}^\{R,\(m\)\}\(s,a\):=\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\bigcap$\}\}\}\}\\displaylimits\_\{\\ell=0\}^\{m\}I\_\{k,h\}^\{R,\(\\ell\)\}\(s,a\),\\hskip 2\.84526pt\\mathcal\{J\}\_\{k,h\}^\{P,\(m\)\}\(s,a\):=\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\bigcap$\}\}\}\}\\displaylimits\_\{\\ell=0\}^\{m\}\\mathcal\{B\}\_\{k,h\}^\{P,\(\\ell\)\}\(s,a\)\.$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle J\_\{k,h\}^\{R,\(m\)\}\(s,a\):=\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\bigcap$\}\}\}\}\\displaylimits\_\{\\ell=0\}^\{m\}I\_\{k,h\}^\{R,\(\\ell\)\}\(s,a\),\\hskip 2\.84526pt\\mathcal\{J\}\_\{k,h\}^\{P,\(m\)\}\(s,a\):=\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\bigcap$\}\}\}\}\\displaylimits\_\{\\ell=0\}^\{m\}\\mathcal\{B\}\_\{k,h\}^\{P,\(\\ell\)\}\(s,a\)\.$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle J\_\{k,h\}^\{R,\(m\)\}\(s,a\):=\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\bigcap$\}\}\}\}\\displaylimits\_\{\\ell=0\}^\{m\}I\_\{k,h\}^\{R,\(\\ell\)\}\(s,a\),\\hskip 2\.84526pt\\mathcal\{J\}\_\{k,h\}^\{P,\(m\)\}\(s,a\):=\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\bigcap$\}\}\}\}\\displaylimits\_\{\\ell=0\}^\{m\}\\mathcal\{B\}\_\{k,h\}^\{P,\(\\ell\)\}\(s,a\)\.$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle J\_\{k,h\}^\{R,\(m\)\}\(s,a\):=\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\bigcap$\}\}\}\}\\displaylimits\_\{\\ell=0\}^\{m\}I\_\{k,h\}^\{R,\(\\ell\)\}\(s,a\),\\hskip 2\.84526pt\\mathcal\{J\}\_\{k,h\}^\{P,\(m\)\}\(s,a\):=\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\bigcap$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\bigcap$\}\}\}\}\\displaylimits\_\{\\ell=0\}^\{m\}\\mathcal\{B\}\_\{k,h\}^\{P,\(\\ell\)\}\(s,a\)\.$\}\}\}\(10\)A nonempty intersection admits a common reward mean or transition row satisfying all constraints up tomm\. As the intersections shrink withmm, we select the largest indices for which they remain nonempty:
m^k,hR\(s,a\)\\displaystyle\\widehat\{m\}\_\{k,h\}^\{R\}\(s,a\):=max\{m:Jk,hR,\(m\)\(s,a\)≠∅\},\\displaystyle:=\\max\\\{m:J\_\{k,h\}^\{R,\(m\)\}\(s,a\)\\neq\\varnothing\\\},\(11\)m^k,hP\(s,a\)\\displaystyle\\widehat\{m\}\_\{k,h\}^\{P\}\(s,a\):=max\{m:𝒥k,hP,\(m\)\(s,a\)≠∅\},\\displaystyle:=\\max\\\{m:\\mathcal\{J\}\_\{k,h\}^\{P,\(m\)\}\(s,a\)\\neq\\varnothing\\\},\(12\)where both maxima range over0≤m≤min\{B,k\}0\\leq m\\leq\\min\\\{B,k\\\}\. The reward estimate is the midpoint of its selected interval:
R^k,h\(s,a\):=𝐦𝐢𝐝\[Jk,hR,\(m^k,hR\(s,a\)\)\(s,a\)\]\.\\widehat\{R\}\_\{k,h\}\(s,a\):=\\mathbf\{mid\}\\left\[J\_\{k,h\}^\{R,\(\\widehat\{m\}\_\{k,h\}^\{R\}\(s,a\)\)\}\(s,a\)\\right\]\.\(13\)This choice satisfies every reward confidence constraint in the selected prefix\. For transitions, let𝐮\\mathbf\{u\}be the uniform distribution on𝒮\\mathcal\{S\}and write\(∙\)≜𝒥k,hP,\(m^k,hP\(s,a\)\)\(s,a\)\(\{\\color\[rgb\]\{0,0,0\.8\}\\bullet\}\)\\triangleq\\mathcal\{J\}\_\{k,h\}^\{P,\(\\widehat\{m\}\_\{k,h\}^\{P\}\(s,a\)\)\}\(s,a\)for the selected confidence intersection\. Define
𝒫^k,h\(⋅∣s,a\):=argminp∈\(∙\)∥p−𝐮∥22\.\\widehat\{\\mathcal\{P\}\}\_\{k,h\}\(\\cdot\\mid s,a\):=\\argmin\_\{p\\in\(\{\\color\[rgb\]\{0,0,0\.8\}\\bullet\}\)\}\\lVert p\-\\mathbf\{u\}\\rVert\_\{2\}^\{2\}\.\(14\)The nonemptym=0m=0sets ensure that both selected indices are well defined\. The reward intersection is a compact interval, and the transition intersection is compact and convex, so the projection in \([14](https://arxiv.org/html/2611.21879#S3.E14)\) is unique\. Both estimates are measurable functions of observations available at\(k,h\)\(k,h\)\. Selection uses only confidence\-set consistency and requires no knowledge of change locations or magnitudes\.
■\\blacksquareComputing the Policy\.The estimatesR^k,h\\widehat\{R\}\_\{k,h\}and𝒫^k,h\\widehat\{\\mathcal\{P\}\}\_\{k,h\}define a fitted MDP at time\(k,h\)\(k,h\)\. To compute an optimal policy for this model, solve the Bellman optimality equation
V^k,h\(s\)\\displaystyle\\widehat\{V\}\_\{k,h\}\(s\)=maxa∈𝒜\{R^k,h\(s,a\)\+γ∑s′∈𝒮𝒫^k,h\(s′∣s,a\)V^k,h\(s′\)\}\.\\displaystyle=\\max\_\{a\\in\\mathcal\{A\}\}\\bigg\\\{\\widehat\{R\}\_\{k,h\}\(s,a\)\+\\gamma\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{s^\{\\prime\}\\in\\mathcal\{S\}\}\\widehat\{\\mathcal\{P\}\}\_\{k,h\}\(s^\{\\prime\}\\mid s,a\)\\widehat\{V\}\_\{k,h\}\(s^\{\\prime\}\)\\bigg\\\}\.\(15\)The fitted Bellman optimality operator is aγ\\gamma\-contraction with unique fixed pointV^k,h\\widehat\{V\}\_\{k,h\}\. Solving \([15](https://arxiv.org/html/2611.21879#S3.E15)\) yields a stationary deterministic optimal policyπk,h\\pi\_\{k,h\}for the fitted MDP\.This policy is computed before receiving tuple\(k,h\)\(k,h\), using retained summaries and the firsthhobservations of deploymentkk\. The newly received tuple then updates the current statistics\. Algorithm[1](https://arxiv.org/html/2611.21879#alg1)summarizes the procedure\.
Algorithm[1](https://arxiv.org/html/2611.21879#alg1)retains visit counts, reward sums, and successor counts for the latestBBcompleted deployments and the current one\. These summaries suffice for all candidate estimates and require𝒪\(\(B\+1\)\|𝒮\|d\)\\mathcal\{O\}\(\(B\+1\)\|\\mathcal\{S\}\|d\)storage, without retaining individual tuples\.
## IVMain Results
In this section, we present our main results for Algorithm[1](https://arxiv.org/html/2611.21879#alg1)\. We recall the average policy lossℒK,Hρ\\mathcal\{L\}\_\{K,H\}^\{\\rho\}and its expectationℛK,Hρ\\mathcal\{R\}\_\{K,H\}^\{\\rho\}, as defined in \([2](https://arxiv.org/html/2611.21879#S2.E2)\)\. In Theorem[1](https://arxiv.org/html/2611.21879#Thmtheorem1), we bound the expected average policy loss over finitely many deployments, and in Corollary[1](https://arxiv.org/html/2611.21879#Thmcorollary1)we provide the corresponding high\-probability bound\. Moreover, Theorem[2](https://arxiv.org/html/2611.21879#Thmtheorem2)establishes a long\-run tracking guarantee while keeping only𝒪\(ϵ−1\)\\mathcal\{O\}\(\\epsilon^\{\-1\}\)deployment summaries\.
###### Theorem 1\.
\(Finite\-deployment policy loss\)Suppose Assumptions[1](https://arxiv.org/html/2611.21879#Thmassumption1)\-[3](https://arxiv.org/html/2611.21879#Thmassumption3)hold\. Then, for everyK≥1K\\geq 1, Algorithm[1](https://arxiv.org/html/2611.21879#alg1), with an integerB≥1B\\geq 1andδ∈\(0,1\)\\delta\\in\(0,1\), satisfies
ℛK,Hρ≲R¯\(1−γ\)2\[LvH\(∙\+κϵ\)\+ΛvH\(∙\+κϑ\)\]\+R¯δ1−γ,\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\begin\{aligned\} \\hskip\-2\.84526pt\\mathcal\{R\}\_\{K,H\}^\{\\rho\}\\lesssim\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\\left\[\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{vH\}\}\\left\(\\bullet\+\\kappa\\epsilon\\right\)\}\+\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{vH\}\}\\left\(\\bullet\+\\kappa\\vartheta\\right\)\}\\right\]\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\\delta\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\\delta\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\\delta\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\\delta\}\{1\-\\gamma\}\},\\end\{aligned\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\begin\{aligned\} \\hskip\-2\.84526pt\\mathcal\{R\}\_\{K,H\}^\{\\rho\}\\lesssim\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\\left\[\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{vH\}\}\\left\(\\bullet\+\\kappa\\epsilon\\right\)\}\+\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{vH\}\}\\left\(\\bullet\+\\kappa\\vartheta\\right\)\}\\right\]\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\\delta\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\\delta\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\\delta\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\\delta\}\{1\-\\gamma\}\},\\end\{aligned\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\begin\{aligned\} \\hskip\-2\.84526pt\\mathcal\{R\}\_\{K,H\}^\{\\rho\}\\lesssim\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\\left\[\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{vH\}\}\\left\(\\bullet\+\\kappa\\epsilon\\right\)\}\+\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{vH\}\}\\left\(\\bullet\+\\kappa\\vartheta\\right\)\}\\right\]\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\\delta\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\\delta\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\\delta\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\\delta\}\{1\-\\gamma\}\},\\end\{aligned\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\begin\{aligned\} \\hskip\-2\.84526pt\\mathcal\{R\}\_\{K,H\}^\{\\rho\}\\lesssim\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{\(1\-\\gamma\)^2\}\}\\left\[\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{vH\}\}\\left\(\\bullet\+\\kappa\\epsilon\\right\)\}\+\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{vH\}\}\\left\(\\bullet\+\\kappa\\vartheta\\right\)\}\\right\]\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\\delta\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\\delta\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\\delta\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\\delta\}\{1\-\\gamma\}\},\\end\{aligned\}$\}\}\}\(16\)whereL,ΛL,\\Lambdaare defined in \([3](https://arxiv.org/html/2611.21879#S3.E3)\),\(∙\):=B−1\+K−1\(\\bullet\):=B^\{\-1\}\+K^\{\-1\}, andϑ:=min\{1,\|𝒮\|ϵ/2\}\\vartheta:=\\min\\\{1,\|\\mathcal\{S\}\|\\epsilon/2\\\}\. Here,KKis the number of deployments,HHis the number of observations per deployment,BBis the maximum number of past deployments retained for estimation, andv\>0v\>0is the uniform lower bound on the sampling probabilitiesνk\(s,a\)\\nu\_\{k\}\(s,a\)in Assumption[2](https://arxiv.org/html/2611.21879#Thmassumption2)\.
Discussion of Theorem[1](https://arxiv.org/html/2611.21879#Thmtheorem1)\.The bound in \([16](https://arxiv.org/html/2611.21879#S4.E16)\) separates the effects of initial learning, finite\-history estimation, and adaptation to sparse model changes\. The first two contributions decay asK−1/2K^\{\-1/2\}andB−1/2B^\{\-1/2\}, respectively, and both scale as\(vH\)−1/2\(vH\)^\{\-1/2\}up to logarithmic factors\. Sparse changes enter throughκϵ\\sqrt\{\\kappa\\epsilon\}for rewards andκϑ\\sqrt\{\\kappa\\vartheta\}for transitions, whereϑ=min\{1,\|𝒮\|ϵ/2\}\\vartheta=\\min\\\{1,\|\\mathcal\{S\}\|\\epsilon/2\\\}makes the dependence on the number of states explicit\. Intuitively, selective history reuse allows unchanged components to benefit from past observations while limiting the influence of outdated data\. For fixedBBandδ\\delta, the confidence factors are independent ofKK\.
###### Corollary 1\.
\(High\-probability policy loss\)Under the conditions of Theorem[1](https://arxiv.org/html/2611.21879#Thmtheorem1), fixK≥1K\\geq 1andα∈\(0,1\)\\alpha\\in\(0,1\)\. Run Algorithm[1](https://arxiv.org/html/2611.21879#alg1)withδ=α/K\\delta=\\alpha/K, and defineLα:=log\(8dK\(B\+1\)\(H\+1\)/α\)L\_\{\\alpha\}:=\\log\(8dK\(B\+1\)\(H\+1\)/\\alpha\)andΛα:=\|𝒮\|log2\+Lα\\Lambda\_\{\\alpha\}:=\|\\mathcal\{S\}\|\\log 2\+L\_\{\\alpha\}\. With probability at least1−α1\-\\alpha, the following bound holds:
ℒK,Hρ≲R¯1−γLα\(∙\+κϵ\)vH\+γR¯\(1−γ\)2Λα\(∙\+κϑ\)vH,\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\begin\{aligned\} \\mathcal\{L\}\_\{K,H\}^\{\\rho\}\\lesssim\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\}\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\},\\end\{aligned\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\begin\{aligned\} \\mathcal\{L\}\_\{K,H\}^\{\\rho\}\\lesssim\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\}\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\},\\end\{aligned\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\begin\{aligned\} \\mathcal\{L\}\_\{K,H\}^\{\\rho\}\\lesssim\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\}\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\},\\end\{aligned\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\begin\{aligned\} \\mathcal\{L\}\_\{K,H\}^\{\\rho\}\\lesssim\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\_\\alpha\(\\bullet\+\\kappa\\epsilon\)\}\{vH\}\}\}\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\_\\alpha\(\\bullet\+\\kappa\\vartheta\)\}\{vH\}\}\},\\end\{aligned\}$\}\}\}\(17\)where\(∙\)\(\\bullet\), and all remaining quantities defined in Theorem[1](https://arxiv.org/html/2611.21879#Thmtheorem1)\.
Lastly, we study persistent tracking with a learner whose parameters are independent ofKK\. The following theorem shows that retaining𝒪\(ϵ−1\)\\mathcal\{O\}\(\\epsilon^\{\-1\}\)deployment summaries suffices to control the long\-run expected average policy loss\.
###### Theorem 2\.
\(Persistent Tracking\)Under the conditions of Theorem[1](https://arxiv.org/html/2611.21879#Thmtheorem1), let0<ϵ≤10<\\epsilon\\leq 1\. ChooseB=⌈ϵ−1⌉B=\\lceil\\epsilon^\{\-1\}\\rceilandδ=ϵ/\(H\+1\)\\delta=\\epsilon/\(H\+1\), and defineLϵ:=log\(24d\(H\+1\)2/ϵ2\)L\_\{\\epsilon\}:=\\log\(24d\(H\+1\)^\{2\}/\\epsilon^\{2\}\)andΛϵ:=\|𝒮\|log2\+Lϵ\\Lambda\_\{\\epsilon\}:=\|\\mathcal\{S\}\|\\log 2\+L\_\{\\epsilon\}\. For everyK≥1K\\geq 1, the same learner satisfies
ℛK,Hρ≲R¯1−γLϵ\(K−1\+κϵ\)vH\+γR¯\(1−γ\)2Λϵ\(K−1\+κϑ\)vH\.\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\begin\{aligned\} \\mathcal\{R\}\_\{K,H\}^\{\\rho\}\\lesssim\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\}\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\}\.\\end\{aligned\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\begin\{aligned\} \\mathcal\{R\}\_\{K,H\}^\{\\rho\}\\lesssim\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\}\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\}\.\\end\{aligned\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\begin\{aligned\} \\mathcal\{R\}\_\{K,H\}^\{\\rho\}\\lesssim\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\}\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\}\.\\end\{aligned\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\begin\{aligned\} \\mathcal\{R\}\_\{K,H\}^\{\\rho\}\\lesssim\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\_\\epsilon\(K^\{\-1\}\+\\kappa\\epsilon\)\}\{vH\}\}\}\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{\(1\-\\gamma\)^2\}\}\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\_\\epsilon\(K^\{\-1\}\+\\kappa\\vartheta\)\}\{vH\}\}\}\.\\end\{aligned\}$\}\}\}\(18\)Therefore, we have
JHρ≲R¯1−γκvH\[ϵLϵ\+γϑΛϵ1−γ\]\.J\_\{H\}^\{\\rho\}\\lesssim\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\bar R\}\{1\-\\gamma\}\}\}\\sqrt\{\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{vH\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{vH\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{vH\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{vH\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{vH\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{vH\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{vH\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{vH\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{vH\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{vH\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{vH\}\}\}\}\\left\[\\sqrt\{\\epsilon L\_\{\\epsilon\}\}\+\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\sqrt\{\\vartheta\\Lambda\_\\epsilon\}\}\{1\-\\gamma\}\}\}\\right\]\.\(19\)
Discussion of Theorem[2](https://arxiv.org/html/2611.21879#Thmtheorem2)\.In \([16](https://arxiv.org/html/2611.21879#S4.E16)\), choosingB=⌈ϵ−1⌉B=\\lceil\\epsilon^\{\-1\}\\rceilgivesB−1≤ϵB^\{\-1\}\\leq\\epsilon, so theB−1B^\{\-1\}contributions are absorbed, up to absolute constants, into the terms involvingκϵ\\kappa\\epsilonandκϑ\\kappa\\vartheta\. Choosingδ=ϵ/\(H\+1\)\\delta=\\epsilon/\(H\+1\)makes the final termR¯ϵ/\(\(1−γ\)\(H\+1\)\)\\bar\{R\}\\epsilon/\(\(1\-\\gamma\)\(H\+1\)\), which is dominated by the reward\-change contribution\. As neither choice depends onKK, the same learner operates across arbitrarily many deployments while retaining only𝒪\(ϵ−1\)\\mathcal\{O\}\(\\epsilon^\{\-1\}\)deployment summaries\. AsK→∞K\\to\\infty, theK−1K^\{\-1\}contributions vanish\. When\|𝒮\|ϵ≤2\|\\mathcal\{S\}\|\\epsilon\\leq 2, substitutingϑ=\|𝒮\|ϵ/2\\vartheta=\|\\mathcal\{S\}\|\\epsilon/2into \([19](https://arxiv.org/html/2611.21879#S4.E19)\) yieldsJHρ=𝒪~\(ϵ/H\)J\_\{H\}^\{\\rho\}=\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{\\epsilon/H\}\)for fixed remaining problem parameters\.
## VNumerical Experiments
We consider an MDP with\|𝒮\|=50\|\\mathcal\{S\}\|=50,\|𝒜\|=4\|\\mathcal\{A\}\|=4,γ=0\.8\\gamma=0\.8, and uniform initial distributionρ\\rho\. Each state\-action pair has two fixed successors with probabilities\(p,1−p\)\(p,1\-p\), wherep∼Unif\[0\.15,0\.85\]p\\sim\\mathrm\{Unif\}\[0\.15,0\.85\]\. The rewards take values in\{−1,1\}\\\{\-1,1\\\}, with initial means uniform on\[−0\.10,0\.10\]\[\-0\.10,0\.10\]\. In addition, reward and transition changes occur within separate, fixed subsets, each containing20%20\\%of the state\-action pairs and they are unknown to the learner\. At each boundary,200ϵ200\\epsilonreward entries and200ϵ200\\epsilontransition rows are selected from their respective subsets and resampled\. Replacement reward means are uniform on\[−0\.65,0\.65\]\[\-0\.65,0\.65\], and transition probabilities are sampled as above\. We considerϵ∈\{0\.02,0\.005\}\\epsilon\\in\\\{0\.02,0\.005\\\}\.
We compare against*restart*, using only current deployment data,*full history*, pooling all available observations, and*shared history*, using the shortest history selected across all components as a common window for the entire MDP\. The proposed method selects histories separately for each reward entry and transition row\. All methods use identical observations and compute optimal policies in their fitted MDPs at common, geometrically spaced sample counts within each deployment\. Each policy’s loss in the true MDP is weighted by the number of observations for which it is held\. Results average5050independent runs\.
Fig\. 2:\(Top\)Evolution of the expected average policy loss𝔼\[ℒK,Hρ\]\\mathbb\{E\}\[\\mathcal\{L\}\_\{K,H\}^\{\\rho\}\]forϵ=0\.02\\epsilon=0\.02, with four reward entries and four transition rows changing per deployment boundary\.\(Bottom\)Results forϵ=0\.005\\epsilon=0\.005, with one reward entry and one transition row changing per boundary\. In both settings, the proposed method achieves the lowest average policy loss by the end of the experiment, while the loss of*full history*increases as deployments accumulate\. Over the final4040deployments, our method reduces average policy loss relative to*shared history*by28\.2%28\.2\\%forϵ=0\.02\\epsilon=0\.02and65\.2%65\.2\\%forϵ=0\.005\\epsilon=0\.005\. The insets show that reusing past observations also reduces the loss relative to*restart*early in each deployment\.
## VIProof of Main Results
We condition on an arbitrary admissible environment sequence under Assumption[2](https://arxiv.org/html/2611.21879#Thmassumption2)\. Lemma[1](https://arxiv.org/html/2611.21879#Thmlemma1)converts the entrywise budget into a bound on changed transition rows\. Lemmas[2](https://arxiv.org/html/2611.21879#Thmlemma2)and[3](https://arxiv.org/html/2611.21879#Thmlemma3)use confidence coverage on unchanged histories to bound the errors of the selected estimates\. Lemma[4](https://arxiv.org/html/2611.21879#Thmlemma4)controls their weighted average in terms of the total number of component changes, allowing data\-dependent weights\. Lemma[5](https://arxiv.org/html/2611.21879#Thmlemma5)then yields the policy loss bound in Theorem[1](https://arxiv.org/html/2611.21879#Thmtheorem1)\. All bounds are uniform over admissible sequences\.
### VI\-AFrom the Transition Entries to the Affected Rows
The following lemma converts the entrywise budget in Assumption[1](https://arxiv.org/html/2611.21879#Thmassumption1)into a bound on affected transition rows\.
###### Lemma 1\.
\(Affected transition rows\)Under Assumption[1](https://arxiv.org/html/2611.21879#Thmassumption1), the number of affected transition rows at each boundarykksatisfies\|𝒞kP\|≤\|ℰkP\|/2\|\\mathcal\{C\}\_\{k\}^\{P\}\|\\leq\|\\mathcal\{E\}\_\{k\}^\{P\}\|/2and, therefore,\|𝒞kP\|≤ϑd\|\\mathcal\{C\}\_\{k\}^\{P\}\|\\leq\\vartheta d\.
###### Proof\.
For each\(s,a\)∈𝒞kP\(s,a\)\\in\\mathcal\{C\}\_\{k\}^\{P\}, the difference𝒫k\+1\(⋅∣s,a\)−𝒫k\(⋅∣s,a\)\\mathcal\{P\}\_\{k\+1\}\(\\cdot\\mid s,a\)\-\\mathcal\{P\}\_\{k\}\(\\cdot\\mid s,a\)is nonzero and sums to zero, so it has both a positive and a negative entry\. Since each changed entry belongs to a unique row,2\|𝒞kP\|≤\|ℰkP\|≤ϵ\|𝒮\|d2\|\\mathcal\{C\}\_\{k\}^\{P\}\|\\leq\|\\mathcal\{E\}\_\{k\}^\{P\}\|\\leq\\epsilon\|\\mathcal\{S\}\|d\. Combining this with\|𝒞kP\|≤d\|\\mathcal\{C\}\_\{k\}^\{P\}\|\\leq dproves Lemma[1](https://arxiv.org/html/2611.21879#Thmlemma1)\. ∎
With the bound from Lemma[1](https://arxiv.org/html/2611.21879#Thmlemma1)on the number of transition rows that can change at each deployment boundary, we next turn to the statistical guarantees\. Lemma[2](https://arxiv.org/html/2611.21879#Thmlemma2)establishes simultaneous confidence coverage within each deployment and lower bounds on visit counts in sufficiently long windows\.
### VI\-BConcentration and Adaptive History Estimation
For each\(s,a\)∈𝒮×𝒜\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}and each candidate window \([4](https://arxiv.org/html/2611.21879#S3.E4)\), the reward coverage guarantee in \([8](https://arxiv.org/html/2611.21879#S3.E8)\) applies if the reward mean equals its current value throughout the window\. The transition coverage guarantee in \([9](https://arxiv.org/html/2611.21879#S3.E9)\) applies under the analogous condition for the transition row\. These conditions depend only on the underlying MDP sequence, hold vacuously for empty windows, and are used only in the analysis\.
###### Lemma 2\.
\(Concentration within a deployment\)For each deploymentkk, define𝒢k:=𝒢kR∩𝒢kP∩𝒢kN,\\mathcal\{G\}\_\{k\}:=\\mathcal\{G\}\_\{k\}^\{R\}\\cap\\mathcal\{G\}\_\{k\}^\{P\}\\cap\\mathcal\{G\}\_\{k\}^\{N\},where the three events are specified below as follows:
- •On𝒢kR\\mathcal\{G\}\_\{k\}^\{R\},Rk\(s,a\)∈Ik,hR,\(m\)\(s,a\)R\_\{k\}\(s,a\)\\in I\_\{k,h\}^\{R,\(m\)\}\(s,a\)wheneverRj\(s,a\)=Rk\(s,a\)R\_\{j\}\(s,a\)=R\_\{k\}\(s,a\)for all\(j,u\)∈𝒲k,h\(m\)\(j,u\)\\in\\mathcal\{W\}\_\{k,h\}^\{\(m\)\}\.
- •On𝒢kP\\mathcal\{G\}\_\{k\}^\{P\},𝒫k\(⋅∣s,a\)∈ℬk,hP,\(m\)\(s,a\)\\mathcal\{P\}\_\{k\}\(\\cdot\\mid s,a\)\\in\\mathcal\{B\}\_\{k,h\}^\{P,\(m\)\}\(s,a\)whenever𝒫j\(⋅∣s,a\)=𝒫k\(⋅∣s,a\)\\mathcal\{P\}\_\{j\}\(\\cdot\\mid s,a\)=\\mathcal\{P\}\_\{k\}\(\\cdot\\mid s,a\)for all\(j,u\)∈𝒲k,h\(m\)\(j,u\)\\in\\mathcal\{W\}\_\{k,h\}^\{\(m\)\}\.
- •On𝒢kN\\mathcal\{G\}\_\{k\}^\{N\},Nk,h\(m\)\(s,a\)≥v\(mH\+h\)2N\_\{k,h\}^\{\(m\)\}\(s,a\)\\geq\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{v\(mH\+h\)\}\{2\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{v\(mH\+h\)\}\{2\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{v\(mH\+h\)\}\{2\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{v\(mH\+h\)\}\{2\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{v\(mH\+h\)\}\{2\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{v\(mH\+h\)\}\{2\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{v\(mH\+h\)\}\{2\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{v\(mH\+h\)\}\{2\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{v\(mH\+h\)\}\{2\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{v\(mH\+h\)\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{v\(mH\+h\)\}\{2\}\}\}formH\+h≥8L/vmH\+h\\geq 8L/v\.
All requirements hold simultaneously over\(s,a\)∈𝒮×𝒜\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\},0≤h≤H0\\leq h\\leq H, and0≤m≤min\{B,k\}0\\leq m\\leq\\min\\\{B,k\\\}\. Thenℙ\(𝒢k\)≥1−δ\\mathbb\{P\}\(\\mathcal\{G\}\_\{k\}\)\\geq 1\-\\delta\.
###### Proof\.
Fix a candidate history𝒲k,h\(m\)\\mathcal\{W\}\_\{k,h\}^\{\(m\)\}from \([4](https://arxiv.org/html/2611.21879#S3.E4)\) and a state–action pair\(s,a\)∈𝒮×𝒜\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\. Condition on the sampled state–action pairs in this history, which fixes the countN:=Nk,h\(m\)\(s,a\)N:=N\_\{k,h\}^\{\(m\)\}\(s,a\)\. First supposeN\>0N\>0\. IfRj\(s,a\)=Rk\(s,a\)R\_\{j\}\(s,a\)=R\_\{k\}\(s,a\)for every\(j,u\)∈𝒲k,h\(m\)\(j,u\)\\in\\mathcal\{W\}\_\{k,h\}^\{\(m\)\}, then Assumption[2](https://arxiv.org/html/2611.21879#Thmassumption2)ensures that theNNrewards averaged in \([6](https://arxiv.org/html/2611.21879#S3.E6)\) are conditionally independent with common meanRk\(s,a\)R\_\{k\}\(s,a\)\. As each reward lies in\[−R¯,R¯\]\[\-\\bar\{R\},\\bar\{R\}\], Hoeffding’s inequality\[[21](https://arxiv.org/html/2611.21879#bib.bib2)\]yields the following:
ℙ\(\|R¯k,h\(m\)\(s,a\)−Rk\(s,a\)\|\>R¯2LN\)≤2e−L\.\\mathbb\{P\}\\\!\\left\(\|\\overline\{R\}\_\{k,h\}^\{\(m\)\}\(s,a\)\-R\_\{k\}\(s,a\)\|\>\\bar\{R\}\\sqrt\{\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}\}\}\\right\)\\leq 2e^\{\-L\}\.\(20\)AsRk\(s,a\)∈\[−R¯,R¯\]R\_\{k\}\(s,a\)\\in\[\-\\bar\{R\},\\bar\{R\}\], intersecting the confidence interval with this range preserves the coverage\.
For transitions, suppose𝒫j\(⋅∣s,a\)=p:=𝒫k\(⋅∣s,a\)\\mathcal\{P\}\_\{j\}\(\\cdot\\mid s,a\)=p:=\\mathcal\{P\}\_\{k\}\(\\cdot\\mid s,a\)for every\(j,u\)∈𝒲k,h\(m\)\(j,u\)\\in\\mathcal\{W\}\_\{k,h\}^\{\(m\)\}, and writep¯:=𝒫¯k,h\(m\)\(⋅∣s,a\)\\overline\{p\}:=\\overline\{\\mathcal\{P\}\}\_\{k,h\}^\{\(m\)\}\(\\cdot\\mid s,a\)for the empirical row in \([7](https://arxiv.org/html/2611.21879#S3.E7)\)\. Therefore, conditional on all sampled pairs\(sj,u,aj,u\)\(s\_\{j,u\},a\_\{j,u\}\)with\(j,u\)∈𝒲k,h\(m\)\(j,u\)\\in\\mathcal\{W\}\_\{k,h\}^\{\(m\)\}, Assumption[2](https://arxiv.org/html/2611.21879#Thmassumption2)ensures that theNNnext states corresponding to visits to\(s,a\)\(s,a\)are independent with common distributionpp\. For each fixed vectorσ∈\{−1,1\}\|𝒮\|\\sigma\\in\\\{\-1,1\\\}^\{\|\\mathcal\{S\}\|\}, letσ\(s′\)\\sigma\(s^\{\\prime\}\)denote its coordinate corresponding to states′∈𝒮s^\{\\prime\}\\in\\mathcal\{S\}\. TheNNtransformed observationsσ\(sj,u′\)\\sigma\(s^\{\\prime\}\_\{j,u\}\)are independent, lie in\[−1,1\]\[\-1,1\], and have common meanσ⊤p\\sigma^\{\\top\}p\. Their empirical mean is thenσ⊤p¯\\sigma^\{\\top\}\\overline\{p\}\. Hence, one\-sided Hoeffding inequality\[[21](https://arxiv.org/html/2611.21879#bib.bib2)\]yieldsℙ\(σ⊤\(p¯−p\)\>b\)≤e−Nb2/2\\mathbb\{P\}\(\\sigma^\{\\top\}\(\\overline\{p\}\-p\)\>b\)\\leq e^\{\-Nb^\{2\}/2\}for everyb\>0b\>0\. Moreover, we obtain∥p¯−p∥1=maxσ∈\{−1,1\}\|𝒮\|σ⊤\(p¯−p\)\\lVert\\overline\{p\}\-p\\rVert\_\{1\}=\\max\_\{\\sigma\\in\\\{\-1,1\\\}^\{\|\\mathcal\{S\}\|\}\}\\sigma^\{\\top\}\(\\overline\{p\}\-p\), with the maximum attained by selectingσ\(s′\)=−1\\sigma\(s^\{\\prime\}\)=\-1whenp¯\(s′\)<p\(s′\)\\overline\{p\}\(s^\{\\prime\}\)<p\(s^\{\\prime\}\)andσ\(s′\)=1\\sigma\(s^\{\\prime\}\)=1otherwise\. A union bound over the2\|𝒮\|2^\{\|\\mathcal\{S\}\|\}sign vectors, withb=2Λ/Nb=\\sqrt\{2\\Lambda/N\}, yields
ℙ\(∥p¯−p∥1\>2ΛN\)≤2\|𝒮\|e−Λ=e−L\.\\mathbb\{P\}\\\!\\left\(\\lVert\\overline\{p\}\-p\\rVert\_\{1\}\>\\sqrt\{\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}\}\}\\right\)\\leq 2^\{\|\\mathcal\{S\}\|\}e^\{\-\\Lambda\}=e^\{\-L\}\.\(21\)Asp∈Δ\(𝒮\)p\\in\\Delta\(\\mathcal\{S\}\), \([21](https://arxiv.org/html/2611.21879#S6.E21)\) gives coverage by the set in \([9](https://arxiv.org/html/2611.21879#S3.E9)\)\. ForN=0N=0, both coverage claims hold by construction\. Averaging over the sampled state–action pairs gives the same unconditional failure bounds\. For the visit\-count bound, setq:=mH\+hq:=mH\+h\. Thus, by Assumption[2](https://arxiv.org/html/2611.21879#Thmassumption2),NNis a sum ofqqindependent Bernoulli indicators with meanμ:=𝔼\[N\]=∑\(j,u\)∈𝒲k,h\(m\)νj\(s,a\)≥vq\\mu:=\\mathbb\{E\}\[N\]=\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{\(j,u\)\\in\\mathcal\{W\}\_\{k,h\}^\{\(m\)\}\}\\nu\_\{j\}\(s,a\)\\geq vq\. The Chernoff inequality\[[21](https://arxiv.org/html/2611.21879#bib.bib2), Theorem 3\.2\]then provides the following bound
ℙ\(N<vq/2\)≤ℙ\(N<μ/2\)≤e−μ/8≤e−vq/8\.\\mathbb\{P\}\(N<vq/2\)\\leq\\mathbb\{P\}\(N<\\mu/2\)\\leq e^\{\-\\mu/8\}\\leq e^\{\-vq/8\}\.\(22\)Hence, the count bound fails with probability at moste−Le^\{\-L\}wheneverq≥8L/vq\\geq 8L/v\. Together with the reward and transition bounds, this yields a combined failure probability of at most4e−L4e^\{\-L\}for each admissible\(\(s,a\)∈𝒮×𝒜,m,h\)\(\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\},m,h\)\.
As𝒢k\\mathcal\{G\}\_\{k\}requires these bounds simultaneously over at mostd\(B\+1\)\(H\+1\)d\(B\+1\)\(H\+1\)index choices, a union bound and \([3](https://arxiv.org/html/2611.21879#S3.E3)\) yieldℙ\(𝒢kc\)≤4d\(B\+1\)\(H\+1\)e−L=δ/2≤δ\\mathbb\{P\}\(\\mathcal\{G\}\_\{k\}^\{c\}\)\\leq 4d\(B\+1\)\(H\+1\)e^\{\-L\}=\\delta/2\\leq\\delta\. ∎
We use Lemma[2](https://arxiv.org/html/2611.21879#Thmlemma2)to bound estimation errors in terms of component age\. Forj∈\{R,P\}j\\in\\\{R,P\\\}, letτkj\(s,a\)\\tau\_\{k\}^\{j\}\(s,a\)be the largestm∈\{0,…,k\}m\\in\\\{0,\\ldots,k\\\}for which componentjjat\(s,a\)\(s,a\)is constant over deploymentsk−m,…,kk\-m,\\ldots,k\. Its age before\(k,h\)\(k,h\)isqk,hj\(s,a\):=τkj\(s,a\)H\+hq\_\{k,h\}^\{j\}\(s,a\):=\\tau\_\{k\}^\{j\}\(s,a\)H\+hobservation times\. Defineek,hR\(s,a\):=\|R^k,h\(s,a\)−Rk\(s,a\)\|e\_\{k,h\}^\{R\}\(s,a\):=\|\\widehat\{R\}\_\{k,h\}\(s,a\)\-R\_\{k\}\(s,a\)\|andek,hP\(s,a\):=‖𝒫^k,h\(⋅∣s,a\)−𝒫k\(⋅∣s,a\)‖1e\_\{k,h\}^\{P\}\(s,a\):=\\left\\lVert\\widehat\{\\mathcal\{P\}\}\_\{k,h\}\(\\cdot\\mid s,a\)\-\\mathcal\{P\}\_\{k\}\(\\cdot\\mid s,a\)\\right\\rVert\_\{1\}\. The history lengths are used only in the analysis and need not be known to the learner\.
###### Lemma 3\.
\(Adaptive History Error\)On𝒢k\\mathcal\{G\}\_\{k\}, the following bounds hold for every\(s,a\)∈𝒮×𝒜\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}and0≤h<H0\\leq h<H:
ek,hR\(s,a\)≤6R¯min\{1,Lv\(min\{B,τkR\(s,a\)\}H\+h\+1\)\}\.\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\hskip\-2\.84526pte\_\{k,h\}^\{R\}\(s,a\)\\leq 6\\bar\{R\}\\min\\left\\\{1,\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\}\\right\\\}\.$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\hskip\-2\.84526pte\_\{k,h\}^\{R\}\(s,a\)\\leq 6\\bar\{R\}\\min\\left\\\{1,\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\}\\right\\\}\.$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\hskip\-2\.84526pte\_\{k,h\}^\{R\}\(s,a\)\\leq 6\\bar\{R\}\\min\\left\\\{1,\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\}\\right\\\}\.$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\hskip\-2\.84526pte\_\{k,h\}^\{R\}\(s,a\)\\leq 6\\bar\{R\}\\min\\left\\\{1,\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{v\(\\min\\\{B,\\tau\_k^R\(s,a\)\\\}H\+h\+1\)\}\}\}\\right\\\}\.$\}\}\}\(23\)ek,hP\(s,a\)≤6min\{1,Λv\(min\{B,τkP\(s,a\)\}H\+h\+1\)\}\.\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\hskip\-5\.69054pte\_\{k,h\}^\{P\}\(s,a\)\\leq 6\\min\\left\\\{1,\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\}\\right\\\}\.$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\hskip\-5\.69054pte\_\{k,h\}^\{P\}\(s,a\)\\leq 6\\min\\left\\\{1,\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\}\\right\\\}\.$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\hskip\-5\.69054pte\_\{k,h\}^\{P\}\(s,a\)\\leq 6\\min\\left\\\{1,\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\}\\right\\\}\.$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\hskip\-5\.69054pte\_\{k,h\}^\{P\}\(s,a\)\\leq 6\\min\\left\\\{1,\\sqrt\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{v\(\\min\\\{B,\\tau\_k^P\(s,a\)\\\}H\+h\+1\)\}\}\}\\right\\\}\.$\}\}\}\(24\)We define
AR:=6R¯Lv,AP:=6Λv,aBj:=AjBH\+1,j∈\{R,P\}\.\\begin\{gathered\}A\_\{R\}:=6\\bar\{R\}\\sqrt\{\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{v\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{v\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{v\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{v\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{v\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{v\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{v\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{v\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{v\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{L\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{L\}\{v\}\}\}\},A\_\{P\}:=6\\sqrt\{\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{v\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{v\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{v\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{v\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{v\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{v\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{v\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{v\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{v\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\Lambda\}\{v\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\Lambda\}\{v\}\}\}\},a\_\{B\}^\{j\}:=\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{A\_j\}\{\\sqrt\{BH\+1\}\}\}\},j\\in\\\{R,P\\\}\.\\end\{gathered\}\(25\)Then, on the same event, forj∈\{R,P\}j\\in\\\{R,P\\\},
ek,hj\(s,a\)≤aBj\+Aj\(qk,hj\(s,a\)\+1\)−1/2\.e\_\{k,h\}^\{j\}\(s,a\)\\leq a\_\{B\}^\{j\}\+A\_\{j\}\(q\_\{k,h\}^\{j\}\(s,a\)\+1\)^\{\-1/2\}\.\(26\)
###### Proof\.
Fix\(s,a\)\(s,a\)andhh, and first consider rewards\. Setm∗:=min\{B,τkR\(s,a\)\}m\_\{\*\}:=\\min\\\{B,\\tau\_\{k\}^\{R\}\(s,a\)\\\}andq∗:=m∗H\+hq\_\{\*\}:=m\_\{\*\}H\+h\. By definition ofτkR\(s,a\)\\tau\_\{k\}^\{R\}\(s,a\), every candidate history with0≤m≤m∗0\\leq m\\leq m\_\{\*\}has reward meanRk\(s,a\)R\_\{k\}\(s,a\)throughout\. On𝒢k\\mathcal\{G\}\_\{k\}, Lemma[2](https://arxiv.org/html/2611.21879#Thmlemma2)therefore ensures that each corresponding interval containsRk\(s,a\)R\_\{k\}\(s,a\)\. Therefore, their intersectionJk,hR,\(m∗\)\(s,a\)J\_\{k,h\}^\{R,\(m\_\{\*\}\)\}\(s,a\)in \([10](https://arxiv.org/html/2611.21879#S3.E10)\) containsRk\(s,a\)R\_\{k\}\(s,a\)and is nonempty\. The selection rule \([11](https://arxiv.org/html/2611.21879#S3.E11)\) thus yieldsm^k,hR\(s,a\)≥m∗\\widehat\{m\}\_\{k,h\}^\{R\}\(s,a\)\\geq m\_\{\*\}\. By \([13](https://arxiv.org/html/2611.21879#S3.E13)\), the estimate lies in the selected intersection\. As these intersections are nested, bothR^k,h\(s,a\)\\widehat\{R\}\_\{k,h\}\(s,a\)andRk\(s,a\)R\_\{k\}\(s,a\)belong toIk,hR,\(m∗\)\(s,a\)I\_\{k,h\}^\{R,\(m\_\{\*\}\)\}\(s,a\)\. By writingN:=Nk,h\(m∗\)\(s,a\)N:=N\_\{k,h\}^\{\(m\_\{\*\}\)\}\(s,a\), the interval definition in \([8](https://arxiv.org/html/2611.21879#S3.E8)\), we have, forN\>0N\>0,
ek,hR\(s,a\)≤min\{2R¯,2R¯2LN\}\.e\_\{k,h\}^\{R\}\(s,a\)\\leq\\min\\left\\\{2\\bar\{R\},\\,2\\bar\{R\}\\sqrt\{\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2L\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2L\}\{N\}\}\}\}\\right\\\}\.\(27\)As the true reward mean and its estimate both lie in\[−R¯,R¯\]\[\-\\bar\{R\},\\bar\{R\}\], the boundek,hR\(s,a\)≤2R¯e\_\{k,h\}^\{R\}\(s,a\)\\leq 2\\bar\{R\}also holds whenN=0N=0\. Ifq∗≥8L/vq\_\{\*\}\\geq 8L/v, the count condition defining𝒢kN\\mathcal\{G\}\_\{k\}^\{N\}in Lemma[2](https://arxiv.org/html/2611.21879#Thmlemma2)impliesN≥vq∗/2N\\geq vq\_\{\*\}/2, as𝒢k⊆𝒢kN\\mathcal\{G\}\_\{k\}\\subseteq\\mathcal\{G\}\_\{k\}^\{N\}\. Hence,ek,hR\(s,a\)≤4R¯L/vq∗≤6R¯L/v\(q∗\+1\),e\_\{k,h\}^\{R\}\(s,a\)\\leq 4\\bar\{R\}\\sqrt\{L/vq\_\{\*\}\}\\leq 6\\bar\{R\}\\sqrt\{L/v\(q\_\{\*\}\+1\)\},where the last step usesq∗≥1q\_\{\*\}\\geq 1\. Combining this withek,hR\(s,a\)≤2R¯e\_\{k,h\}^\{R\}\(s,a\)\\leq 2\\bar\{R\}proves \([23](https://arxiv.org/html/2611.21879#S6.E23)\) whenq∗≥8L/vq\_\{\*\}\\geq 8L/v\. Ifq∗<8L/vq\_\{\*\}<8L/v, thenq∗\+1≤9L/vq\_\{\*\}\+1\\leq 9L/vbecauseL/v≥1L/v\\geq 1\. The right\-hand side of \([23](https://arxiv.org/html/2611.21879#S6.E23)\) is therefore at least2R¯2\\bar\{R\}, so the deterministic bound also covers this case, includingq∗=0q\_\{\*\}=0\. For transitions, setm∗:=min\{B,τkP\(s,a\)\}m\_\{\*\}:=\\min\\\{B,\\tau\_\{k\}^\{P\}\(s,a\)\\\}andq∗:=m∗H\+hq\_\{\*\}:=m\_\{\*\}H\+h\. The transition coverage in Lemma[2](https://arxiv.org/html/2611.21879#Thmlemma2)and the selection rule \([12](https://arxiv.org/html/2611.21879#S3.E12)\) similarly givem^k,hP\(s,a\)≥m∗\\widehat\{m\}\_\{k,h\}^\{P\}\(s,a\)\\geq m\_\{\*\}\. By the nesting in \([10](https://arxiv.org/html/2611.21879#S3.E10)\) and the estimator definition in \([14](https://arxiv.org/html/2611.21879#S3.E14)\), both the true and estimated rows belong toℬk,hP,\(m∗\)\(s,a\)\\mathcal\{B\}\_\{k,h\}^\{P,\(m\_\{\*\}\)\}\(s,a\)\. ForN:=Nk,h\(m∗\)\(s,a\)\>0N:=N\_\{k,h\}^\{\(m\_\{\*\}\)\}\(s,a\)\>0, the triangle inequality and the radius in \([9](https://arxiv.org/html/2611.21879#S3.E9)\) establish the following inequality:
ek,hP\(s,a\)≤min\{2,22ΛN\},e\_\{k,h\}^\{P\}\(s,a\)\\leq\\min\\left\\\{2,\\,2\\sqrt\{\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\\Lambda\}\{N\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\\Lambda\}\{N\}\}\}\}\\right\\\},\(28\)whereek,hP\(s,a\)≤2e\_\{k,h\}^\{P\}\(s,a\)\\leq 2follows because both rows are probability distributions\. Ifq∗≥8L/vq\_\{\*\}\\geq 8L/v, the count condition on𝒢kN\\mathcal\{G\}\_\{k\}^\{N\}in Lemma[2](https://arxiv.org/html/2611.21879#Thmlemma2)yeildsN≥vq∗/2N\\geq vq\_\{\*\}/2, and henceek,hP\(s,a\)≤4Λ/\(vq∗\)≤6Λ/\[v\(q∗\+1\)\]e\_\{k,h\}^\{P\}\(s,a\)\\leq 4\\sqrt\{\\Lambda/\(vq\_\{\*\}\)\}\\leq 6\\sqrt\{\\Lambda/\[v\(q\_\{\*\}\+1\)\]\}\. Together withek,hP\(s,a\)≤2e\_\{k,h\}^\{P\}\(s,a\)\\leq 2, this establishes \([24](https://arxiv.org/html/2611.21879#S6.E24)\) for this case\. Ifq∗<8L/vq\_\{\*\}<8L/v, thenq∗\+1≤9L/v≤9Λ/vq\_\{\*\}\+1\\leq 9L/v\\leq 9\\Lambda/v, so the right\-hand side of \([24](https://arxiv.org/html/2611.21879#S6.E24)\) is at least two\. The deterministic bound therefore also proves the claim in this case, including whenN=0N=0\.
Finally, fixj∈\{R,P\}j\\in\\\{R,P\\\}\. Whenτkj\(s,a\)<B\\tau\_\{k\}^\{j\}\(s,a\)<B, the corresponding bound in \([23](https://arxiv.org/html/2611.21879#S6.E23)\) or \([24](https://arxiv.org/html/2611.21879#S6.E24)\) yieldsek,hj\(s,a\)≤Aj/qk,hj\(s,a\)\+1e\_\{k,h\}^\{j\}\(s,a\)\\leq A\_\{j\}/\\sqrt\{q\_\{k,h\}^\{j\}\(s,a\)\+1\}\. Whenτkj\(s,a\)≥B\\tau\_\{k\}^\{j\}\(s,a\)\\geq B, it instead givesek,hj\(s,a\)≤Aj/BH\+h\+1≤aBje\_\{k,h\}^\{j\}\(s,a\)\\leq A\_\{j\}/\\sqrt\{BH\+h\+1\}\\leq a\_\{B\}^\{j\}, using \([25](https://arxiv.org/html/2611.21879#S6.E25)\)\. Both cases imply \([26](https://arxiv.org/html/2611.21879#S6.E26)\)\. ∎
On𝒢k\\mathcal\{G\}\_\{k\}, the confidence set indexed bymin\{B,τkj\(s,a\)\}\\min\\\{B,\\tau\_\{k\}^\{j\}\(s,a\)\\\}contains both the current component and, by the nesting in \([10](https://arxiv.org/html/2611.21879#S3.E10)\), the selected estimate, even when a longer history is selected\. Thus, the error bounds require neither change identification nor a minimum change magnitude\. After separatingaBja\_\{B\}^\{j\}in \([26](https://arxiv.org/html/2611.21879#S6.E26)\), Lemma[4](https://arxiv.org/html/2611.21879#Thmlemma4)controls the average ofAj/\(qk,hj\(s,a\)\+1\)1/2A\_\{j\}/\(q\_\{k,h\}^\{j\}\(s,a\)\+1\)^\{1/2\}through the total number of component changes\. Its pathwise bound holds for all normalized weights satisfying the occupancy constraint, including those obtained from policies learned from the same observations\.
### VI\-CAccumulation across Deployments
LetNchRN\_\{\\mathrm\{ch\}\}^\{R\}andNchPN\_\{\\mathrm\{ch\}\}^\{P\}denote the total numbers of changes to reward entries and transition rows, respectively, across deployment boundaries\. In particular,Nchj:=∑k=0K−2\|𝒞kj\|N\_\{\\mathrm\{ch\}\}^\{j\}:=\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{k=0\}^\{K\-2\}\|\\mathcal\{C\}\_\{k\}^\{j\}\|forj∈\{R,P\}j\\in\\\{R,P\\\}, with empty sums equal to zero\. Assumption[1](https://arxiv.org/html/2611.21879#Thmassumption1)and Lemma[1](https://arxiv.org/html/2611.21879#Thmlemma1)giveNchR≤ϵd\(K−1\)N\_\{\\mathrm\{ch\}\}^\{R\}\\leq\\epsilon d\(K\-1\)andNchP≤ϑd\(K−1\)N\_\{\\mathrm\{ch\}\}^\{P\}\\leq\\vartheta d\(K\-1\)\. Each component remains constant between changes\.
###### Lemma 4\.
\(Weighted Accumulation of Errors\)LetT:=KHT:=KHandA≥0A\\geq 0\. Consider a component process with agesqk,h\(s,a\)q\_\{k,h\}\(s,a\)as defined above andNchN\_\{\\mathrm\{ch\}\}component changes\. Suppose the nonnegative errors satisfyfk,h\(s,a\)≤A\(qk,h\(s,a\)\+1\)−1/2,f\_\{k,h\}\(s,a\)\\leq A\(q\_\{k,h\}\(s,a\)\+1\)^\{\-1/2\},and the weights satisfy
∑s,awk,h\(s,a\)=1,0≤wk,h\(s,a\)≤κd\.\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{s,a\}w\_\{k,h\}\(s,a\)=1,\\quad 0\\leq w\_\{k,h\}\(s,a\)\\leq\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa\}\{d\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa\}\{d\}\}\}\.\(29\)Then, we have
1T∑k=0K−1∑h=0H−1∑s,awk,h\(s,a\)fk,h\(s,a\)≤2AT\+2AκNchdT\.\\displaystyle\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{T\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{T\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{T\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{T\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{T\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{T\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{T\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{T\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{T\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{T\}\}\}\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{k=0\}^\{K\-1\}\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{h=0\}^\{H\-1\}\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{s,a\}w\_\{k,h\}\(s,a\)f\_\{k,h\}\(s,a\)\\leq\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2A\}\{\\sqrt T\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2A\}\{\\sqrt T\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2A\}\{\\sqrt T\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2A\}\{\\sqrt T\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2A\}\{\\sqrt T\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2A\}\{\\sqrt T\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2A\}\{\\sqrt T\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2A\}\{\\sqrt T\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2A\}\{\\sqrt T\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2A\}\{\\sqrt T\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2A\}\{\\sqrt T\}\}\}\+2A\\sqrt\{\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\kappa N\_\{\\mathrm\{ch\}\}\}\{dT\}\}\}\}\.\(30\)
###### Proof\.
Reindex time byt=kH\+ht=kH\+h\. Letbt:=A/t\+1b\_\{t\}:=A/\\sqrt\{t\+1\}andzt\(s,a\):=max\{ft\(s,a\)−bt,0\}z\_\{t\}\(s,a\):=\\max\\\{f\_\{t\}\(s,a\)\-b\_\{t\},\\,0\\\}\. Sinceft\(s,a\)≤bt\+zt\(s,a\)f\_\{t\}\(s,a\)\\leq b\_\{t\}\+z\_\{t\}\(s,a\)and the weights sum to one, the contribution ofbtb\_\{t\}to the weighted average is at mostT−1∑tbt≤2A/TT^\{\-1\}\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{t\}b\_\{t\}\\leq 2A/\\sqrt\{T\}\. Before the first change of\(s,a\)\(s,a\), we haveqt\(s,a\)=tq\_\{t\}\(s,a\)=t, sozt\(s,a\)=0z\_\{t\}\(s,a\)=0\. In each interval beginning at a component change, the age starts at zero and increases by one per time step\. Hencezt\(s,a\)\>uz\_\{t\}\(s,a\)\>uimpliesqt\(s,a\)\+1<A2/u2q\_\{t\}\(s,a\)\+1<A^\{2\}/u^\{2\}, which can occur at mostA2/u2A^\{2\}/u^\{2\}times per interval\. Summing over theNchN\_\{\\mathrm\{ch\}\}such intervals and using the weight constraints givesT−1∑t,s,awt\(s,a\)𝟏\{zt\(s,a\)\>u\}≤min\{1,κNchA2/\(dTu2\)\}T^\{\-1\}\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{t,s,a\}w\_\{t\}\(s,a\)\\mathbf\{1\}\\\{z\_\{t\}\(s,a\)\>u\\\}\\leq\\min\\\{1,\\kappa N\_\{\\mathrm\{ch\}\}A^\{2\}/\(dTu^\{2\}\)\\\}\. Integrating overu\>0u\>0bounds the weighted average ofztz\_\{t\}by2AκNch/\(dT\)2A\\sqrt\{\\kappa N\_\{\\mathrm\{ch\}\}/\(dT\)\}\. Adding the two contributions proves the claim\. ∎
The proof uses only the error bound onfk,h\(s,a\)f\_\{k,h\}\(s,a\)and the weight constraints in \([29](https://arxiv.org/html/2611.21879#S6.E29)\)\. Its conclusion therefore holds for every realization satisfying these conditions\.
### VI\-DFrom Model Error to Policy Loss
The following lemma bounds the loss in the true MDP of a policy optimal for the estimated model by a weighted sum of reward and transition errors\. Under Assumption[3](https://arxiv.org/html/2611.21879#Thmassumption3), the resulting occupancy weights satisfy \([29](https://arxiv.org/html/2611.21879#S6.E29)\), allowing us to apply Lemma[4](https://arxiv.org/html/2611.21879#Thmlemma4)\.
###### Lemma 5\.
\(Policy comparison for an estimated model\)Fix a deploymentkk\. Let\(𝒫^,R^\)\(\\widehat\{\\mathcal\{P\}\},\\widehat\{R\}\)be an estimated model on the same state and action spaces, satisfying𝒫^\(⋅∣s,a\)∈Δ\(𝒮\)\\widehat\{\\mathcal\{P\}\}\(\\cdot\\mid s,a\)\\in\\Delta\(\\mathcal\{S\}\)and\|R^\(s,a\)\|≤R¯\|\\widehat\{R\}\(s,a\)\|\\leq\\bar\{R\}for every\(s,a\)\(s,a\)\. Letπ^\\widehat\{\\pi\}be an optimal policy for this model\. Define the reward and transition errors byeR\(s,a\):=\|Rk\(s,a\)−R^\(s,a\)\|e\_\{R\}\(s,a\):=\|R\_\{k\}\(s,a\)\-\\widehat\{R\}\(s,a\)\|andeP\(s,a\):=‖𝒫k\(⋅∣s,a\)−𝒫^\(⋅∣s,a\)‖1e\_\{P\}\(s,a\):=\\left\\lVert\\mathcal\{P\}\_\{k\}\(\\cdot\\mid s,a\)\-\\widehat\{\\mathcal\{P\}\}\(\\cdot\\mid s,a\)\\right\\rVert\_\{1\}, respectively\. Then
ℓkρ\(π^\)\\displaystyle\\ell\_\{k\}^\{\\rho\}\(\\widehat\{\\pi\}\)≤21−γ∑s,aw\(s,a\)⋅\[eR\(s,a\)\+γR¯1−γeP\(s,a\)\],\\displaystyle\\leq\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\}\{1\-\\gamma\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\}\{1\-\\gamma\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\}\{1\-\\gamma\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{2\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{2\}\{1\-\\gamma\}\}\}\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{s,a\}w\(s,a\)\\cdot\\left\[e\_\{R\}\(s,a\)\+\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\}e\_\{P\}\(s,a\)\\right\],\(31\)wherew\(s,a\):=12\[dρ,kπk∗\(s,a\)\+dρ,kπ^\(s,a\)\]\.w\(s,a\):=\\mathchoice\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{2\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{2\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{2\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{2\}\}$\}\}\}\}\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{2\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{2\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{2\}\}$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{2\}\}$\}\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{2\}\}\}\{\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{2\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{2\}\}\}\\left\[d\_\{\\rho,k\}^\{\\pi\_\{k\}^\{\*\}\}\(s,a\)\+d\_\{\\rho,k\}^\{\\widehat\{\\pi\}\}\(s,a\)\\right\]\.Under Assumption[3](https://arxiv.org/html/2611.21879#Thmassumption3), these weights satisfy \([29](https://arxiv.org/html/2611.21879#S6.E29)\)\.
###### Proof\.
For any stationary policyπ\\pi, letV^π\\widehat\{V\}^\{\\pi\}be its value in the fitted MDP and setJ^ρ\(π\):=ρ⊤V^π\\widehat\{J\}^\{\\rho\}\(\\pi\):=\\rho^\{\\top\}\\widehat\{V\}^\{\\pi\}\. Subtracting the Bellman equations and expanding the true\-model resolvent givesJkρ\(π\)−J^ρ\(π\)=\(1−γ\)−1∑s,adρ,kπ\(s,a\)\[\(Rk−R^\)\(s,a\)\+γ⟨\(𝒫k−𝒫^\)\(⋅∣s,a\),V^π⟩\]J\_\{k\}^\{\\rho\}\(\\pi\)\-\\widehat\{J\}^\{\\rho\}\(\\pi\)=\(1\-\\gamma\)^\{\-1\}\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{s,a\}d\_\{\\rho,k\}^\{\\pi\}\(s,a\)\\big\[\(R\_\{k\}\-\\widehat\{R\}\)\(s,a\)\+\\gamma\\langle\(\\mathcal\{P\}\_\{k\}\-\\widehat\{\\mathcal\{P\}\}\)\(\\cdot\\mid s,a\),\\widehat\{V\}^\{\\pi\}\\rangle\\big\]\. Using∥V^π∥∞≤R¯/\(1−γ\)\\lVert\\widehat\{V\}^\{\\pi\}\\rVert\_\{\\infty\}\\leq\\bar\{R\}/\(1\-\\gamma\)yields the following bound:
\|Jkρ\(π\)−J^ρ\(π\)\|≤11−γ∑s,adρ,kπ\(s,a\)\[eR\(s,a\)\+γR¯1−γeP\(s,a\)\]\.\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\|J\_\{k\}^\{\\rho\}\(\\pi\)\-\\widehat\{J\}^\{\\rho\}\(\\pi\)\|\\leq\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{1\-\\gamma\}\}\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{s,a\}d\_\{\\rho,k\}^\{\\pi\}\(s,a\)\\left\[e\_\{R\}\(s,a\)\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}e\_\{P\}\(s,a\)\\right\]\.$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\|J\_\{k\}^\{\\rho\}\(\\pi\)\-\\widehat\{J\}^\{\\rho\}\(\\pi\)\|\\leq\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{1\-\\gamma\}\}\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{s,a\}d\_\{\\rho,k\}^\{\\pi\}\(s,a\)\\left\[e\_\{R\}\(s,a\)\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}e\_\{P\}\(s,a\)\\right\]\.$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\|J\_\{k\}^\{\\rho\}\(\\pi\)\-\\widehat\{J\}^\{\\rho\}\(\\pi\)\|\\leq\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{1\-\\gamma\}\}\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{s,a\}d\_\{\\rho,k\}^\{\\pi\}\(s,a\)\\left\[e\_\{R\}\(s,a\)\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}e\_\{P\}\(s,a\)\\right\]\.$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\|J\_\{k\}^\{\\rho\}\(\\pi\)\-\\widehat\{J\}^\{\\rho\}\(\\pi\)\|\\leq\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{1\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{1\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{1\}\{1\-\\gamma\}\}\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{s,a\}d\_\{\\rho,k\}^\{\\pi\}\(s,a\)\\left\[e\_\{R\}\(s,a\)\+\\mathchoice\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{0\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{1\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}\{\\genfrac\{\}\{\}\{\}\{2\}\{\\gamma\\bar R\}\{1\-\\gamma\}\}e\_\{P\}\(s,a\)\\right\]\.$\}\}\}\(32\)SinceJ^ρ\(πk∗\)≤J^ρ\(π^\)\\widehat\{J\}^\{\\rho\}\(\\pi\_\{k\}^\{\*\}\)\\leq\\widehat\{J\}^\{\\rho\}\(\\widehat\{\\pi\}\), the policy loss is bounded by the sum of the absolute return errors forπk∗\\pi\_\{k\}^\{\*\}andπ^\\widehat\{\\pi\}\. Applying \([32](https://arxiv.org/html/2611.21879#S6.E32)\) to both policies gives \([31](https://arxiv.org/html/2611.21879#S6.E31)\) with their average occupancyw\(s,a\)w\(s,a\)\. Normalization and Assumption[3](https://arxiv.org/html/2611.21879#Thmassumption3)give \([29](https://arxiv.org/html/2611.21879#S6.E29)\)\. ∎
###### ∙\\bulletProof of Theorem[1](https://arxiv.org/html/2611.21879#Thmtheorem1)\.
SetT:=KHT:=KH, and take the weightswk,h\(s,a\)w\_\{k,h\}\(s,a\)from Lemma[5](https://arxiv.org/html/2611.21879#Thmlemma5), satisfying \([29](https://arxiv.org/html/2611.21879#S6.E29)\)\. Forj∈\{R,P\}j\\in\\\{R,P\\\}, definefk,hj\(s,a\):=\(ek,hj\(s,a\)−aBj\)\+𝟏𝒢kf\_\{k,h\}^\{j\}\(s,a\):=\(e\_\{k,h\}^\{j\}\(s,a\)\-a\_\{B\}^\{j\}\)\_\{\+\}\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{k\}\}\. Leveraging Lemma[3](https://arxiv.org/html/2611.21879#Thmlemma3), we get0≤fk,hj\(s,a\)≤Aj/qk,hj\(s,a\)\+10\\leq f\_\{k,h\}^\{j\}\(s,a\)\\leq A\_\{j\}/\\sqrt\{q\_\{k,h\}^\{j\}\(s,a\)\+1\}for every realization\. Sinceek,hj\(s,a\)𝟏𝒢k≤aBj\+fk,hj\(s,a\)e\_\{k,h\}^\{j\}\(s,a\)\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{k\}\}\\leq a\_\{B\}^\{j\}\+f\_\{k,h\}^\{j\}\(s,a\), weight normalization and Lemma[4](https://arxiv.org/html/2611.21879#Thmlemma4)yieldT−1∑k,h∑s,awk,h\(s,a\)ek,hj\(s,a\)𝟏𝒢k≤DjT^\{\-1\}\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{k,h\}\\mathop\{\\mathord\{\\mathchoice\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\displaystyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\textstyle\\sum$\}\}\{\\raise 0\.49991pt\\hbox\{$\\scriptstyle\\sum$\}\}\}\}\\displaylimits\_\{s,a\}w\_\{k,h\}\(s,a\)e\_\{k,h\}^\{j\}\(s,a\)\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{k\}\}\\leq D\_\{j\}, whereDj:=aBj\+2Aj/T\+2AjκNchj/\(dT\)D\_\{j\}:=a\_\{B\}^\{j\}\+2A\_\{j\}/\\sqrt\{T\}\+2A\_\{j\}\\sqrt\{\\kappa N\_\{\\mathrm\{ch\}\}^\{j\}/\(dT\)\}\. Apply \([31](https://arxiv.org/html/2611.21879#S6.E31)\) on𝒢k\\mathcal\{G\}\_\{k\}and the loss cap2R¯/\(1−γ\)2\\bar\{R\}/\(1\-\\gamma\)on𝒢kc\\mathcal\{G\}\_\{k\}^\{c\}\. Averaging and taking expectations, usingℙ\(𝒢kc\)≤δ\\mathbb\{P\}\(\\mathcal\{G\}\_\{k\}^\{c\}\)\\leq\\deltafrom Lemma[2](https://arxiv.org/html/2611.21879#Thmlemma2), gives𝔼\[ℒK,Hρ\]≤2DR/\(1−γ\)\+2γR¯DP/\(1−γ\)2\+2R¯δ/\(1−γ\)\\mathbb\{E\}\[\\mathcal\{L\}\_\{K,H\}^\{\\rho\}\]\\leq 2D\_\{R\}/\(1\-\\gamma\)\+2\\gamma\\bar\{R\}D\_\{P\}/\(1\-\\gamma\)^\{2\}\+2\\bar\{R\}\\delta/\(1\-\\gamma\)\. Assumption[1](https://arxiv.org/html/2611.21879#Thmassumption1)and Lemma[1](https://arxiv.org/html/2611.21879#Thmlemma1)implyNchR≤ϵd\(K−1\)N\_\{\\mathrm\{ch\}\}^\{R\}\\leq\\epsilon d\(K\-1\)andNchP≤ϑd\(K−1\)N\_\{\\mathrm\{ch\}\}^\{P\}\\leq\\vartheta d\(K\-1\)\. Substituting these bounds and \([25](https://arxiv.org/html/2611.21879#S6.E25)\) intoDjD\_\{j\}, then applying Cauchy–Schwarz, yieldsDR≤CR¯L\(∙\+κϵ\)/\(vH\)D\_\{R\}\\leq C\\bar\{R\}\\sqrt\{L\(\\bullet\+\\kappa\\epsilon\)/\(vH\)\}andDP≤CΛ\(∙\+κϑ\)/\(vH\)D\_\{P\}\\leq C\\sqrt\{\\Lambda\(\\bullet\+\\kappa\\vartheta\)/\(vH\)\}, where∙:=B−1\+K−1\\bullet:=B^\{\-1\}\+K^\{\-1\}andCCis an absolute constant\. Inserting these estimates proves \([16](https://arxiv.org/html/2611.21879#S4.E16)\)\. ∎
###### ∙\\bulletProof of Theorem[2](https://arxiv.org/html/2611.21879#Thmtheorem2)\.
The choiceB=⌈ϵ−1⌉B=\\lceil\\epsilon^\{\-1\}\\rceilgivesB−1≤ϵB^\{\-1\}\\leq\\epsilonandB\+1≤3/ϵB\+1\\leq 3/\\epsilon\. Withδ=ϵ/\(H\+1\)\\delta=\\epsilon/\(H\+1\), \([3](https://arxiv.org/html/2611.21879#S3.E3)\) therefore impliesL≤LϵL\\leq L\_\{\\epsilon\}andΛ≤Λϵ\\Lambda\\leq\\Lambda\_\{\\epsilon\}\. Asκ≥1\\kappa\\geq 1andϑ≥ϵ/2\\vartheta\\geq\\epsilon/2, we also haveB−1\+κϵ≤2κϵB^\{\-1\}\+\\kappa\\epsilon\\leq 2\\kappa\\epsilonandB−1\+κϑ≤3κϑB^\{\-1\}\+\\kappa\\vartheta\\leq 3\\kappa\\vartheta\. Substituting these estimates into the separate reward and transition bounds established in the proof of Theorem[1](https://arxiv.org/html/2611.21879#Thmtheorem1)gives \([18](https://arxiv.org/html/2611.21879#S4.E18)\), after absorbing the additive failure term into the reward term usingδ=ϵ/\(H\+1\)≤κϵLϵ/\(vH\)\\delta=\\epsilon/\(H\+1\)\\leq\\sqrt\{\\kappa\\epsilon L\_\{\\epsilon\}/\(vH\)\}\. Both parameter choices are independent ofKK, so the same learner retains𝒪\(ϵ−1\)\\mathcal\{O\}\(\\epsilon^\{\-1\}\)deployment summaries for every horizon\. Takinglim supK→∞\\limsup\_\{K\\to\\infty\}in \([18](https://arxiv.org/html/2611.21879#S4.E18)\) proves \([19](https://arxiv.org/html/2611.21879#S4.E19)\)\. ∎
## VIIConclusion
We studied RL in discounted MDPs with sparse changes in reward and transition entries between deployments\. We proposed an approach for the learner that uses confidence sets to select how much past history to pool separately for each reward mean and transition row\. Under independent sampling and0<\|𝒮\|ϵ≤20<\|\\mathcal\{S\}\|\\epsilon\\leq 2, we demonstrated that retaining𝒪\(ϵ−1\)\\mathcal\{O\}\(\\epsilon^\{\-1\}\)deployment summaries suffices to achieve a long\-run expected average policy loss of𝒪~\(ϵ/H\)\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{\\epsilon/H\}\)\.
## References
- \[1\]A\. Rahimi\-Kalahroudi, J\. Rajendran, I\. Momennejad, H\. van Seijen, and S\. Chandar\(2023\)Replay buffer with local forgetting for adapting to local environment changes in deep model\-based reinforcement learning\.InProceedings of The 2nd Conference on Lifelong Learning Agents,Vol\.232,pp\. 21–42\.Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p1.1),[§I](https://arxiv.org/html/2611.21879#S1.p5.1)\.
- \[2\]W\. C\. Cheung, D\. Simchi\-Levi, and R\. Zhu\(2020\)Reinforcement learning for non\-stationary Markov decision processes: the blessing of \(More\) optimism\.InProceedings of the 37th International Conference on Machine Learning,pp\. 1843–1854\.Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p1.1),[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[3\]R\. Ortner, P\. Gajane, and P\. Auer\(2020\)Variational regret bounds for reinforcement learning\.InProceedings of The 35th Uncertainty in Artificial Intelligence Conference,Vol\.115,pp\. 81–90\.Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[4\]C\. Wei and H\. Luo\(2021\)Non\-stationary reinforcement learning without prior knowledge: an optimal black\-box approach\.InProceedings of Thirty Fourth Conference on Learning Theory,Vol\.134,pp\. 4300–4354\.Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[5\]R\. Alami, M\. Mahfoud, and E\. Moulines\(2023\)Restarted Bayesian online change\-point detection for non\-stationary Markov decision processes\.InProceedings of The 2nd Conference on Lifelong Learning Agents,Vol\.232,pp\. 715–744\.Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[6\]R\. Caruana\(1997\)Multitask learning\.Machine Learning28,pp\. 41–75\.External Links:[Document](https://dx.doi.org/10.1023/A%3A1007379606734)Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[7\]J\. Baxter\(2000\)A model of inductive bias learning\.Journal of Artificial Intelligence Research12,pp\. 149–198\.External Links:[Document](https://dx.doi.org/10.1613/jair.731)Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[8\]N\. Tripuraneni, C\. Jin, and M\. Jordan\(2021\)Provable meta\-learning of linear representations\.InProceedings of the 38th International Conference on Machine Learning,Vol\.139,pp\. 10434–10443\.External Links:[Link](https://proceedings.mlr.press/v139/tripuraneni21a.html)Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[9\]T\. T\. Zhang, K\. Kang, B\. D\. Lee, C\. Tomlin, S\. Levine, S\. Tu, and N\. Matni\(2023\)Multi\-task imitation learning for linear dynamical systems\.InLearning for Dynamics and Control Conference,pp\. 586–599\.Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[10\]L\. F\. Toso, D\. Zhan, J\. Anderson, and H\. Wang\(2024\)Meta\-learning linear quadratic regulators: A policy gradient MAML approach for model\-free LQR\.InProceedings of the 6th Annual Learning for Dynamics & Control Conference,Vol\.242,pp\. 902–915\.External Links:[Link](https://proceedings.mlr.press/v242/toso24a.html)Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[11\]S\. M\. Richards, N\. Azizan, J\. Slotine, and M\. Pavone\(2023\)Control\-oriented meta\-learning\.The International Journal of Robotics Research42\(10\),pp\. 777–797\.External Links:[Document](https://dx.doi.org/10.1177/02783649231165085),[Link](https://arxiv.org/abs/2204.06716)Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[12\]L\. F\. Toso, H\. Wang, and J\. Anderson\(2024\)Asynchronous heterogeneous linear quadratic regulator design\.InIEEE 63rd Conference on Decision and Control,External Links:[Link](https://arxiv.org/abs/2404.09061)Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[13\]M\. Al\-Shedivat, T\. Bansal, Y\. Burda, I\. Sutskever, I\. Mordatch, and P\. Abbeel\(2018\)Continuous adaptation via meta\-learning in nonstationary and competitive environments\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=Sk2u1g-0-)Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[14\]A\. Nagabandi, I\. Clavera, S\. Liu, R\. S\. Fearing, P\. Abbeel, S\. Levine, and C\. Finn\(2019\)Learning to adapt in dynamic, real\-world environments through meta\-reinforcement learning\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=HyztsoC5Y7)Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[15\]A\. Nagabandi, C\. Finn, and S\. Levine\(2019\)Deep online learning via meta\-learning: continual adaptation for model\-based RL\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=HyxAfnA5tm)Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[16\]Z\. Bing, D\. Lerch, K\. Huang, and A\. Knoll\(2023\)Meta\-reinforcement learning in non\-stationary and dynamic environments\.IEEE Transactions on Pattern Analysis and Machine Intelligence45\(3\),pp\. 3476–3491\.External Links:[Document](https://dx.doi.org/10.1109/TPAMI.2022.3185549)Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[17\]J\. Tobin, R\. Fong, A\. Ray, J\. Schneider, W\. Zaremba, and P\. Abbeel\(2017\)Domain randomization for transferring deep neural networks from simulation to the real world\.InIEEE/RSJ International Conference on Intelligent Robots and Systems,External Links:[Link](https://arxiv.org/abs/1703.06907)Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[18\]X\. B\. Peng, M\. Andrychowicz, W\. Zaremba, and P\. Abbeel\(2018\)Sim\-to\-real transfer of robotic control with dynamics randomization\.InIEEE International Conference on Robotics and Automation,pp\. 3803–3810\.External Links:[Link](https://arxiv.org/abs/1710.06537)Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[19\]F\. Ramos, R\. Possas, and D\. Fox\(2019\)BayesSim: adaptive domain randomization via probabilistic inference for robotics simulators\.InProceedings of Robotics: Science and Systems,External Links:[Link](https://www.roboticsproceedings.org/rss15/p29.html)Cited by:[§I](https://arxiv.org/html/2611.21879#S1.p4.1)\.
- \[20\]R\. S\. Sutton and A\. G\. Barto\(2018\)Reinforcement learning: an introduction\.MIT press\.Cited by:[§II](https://arxiv.org/html/2611.21879#S2.p1.1)\.
- \[21\]F\. Chung and L\. Lu\(2006\)Concentration inequalities and martingale inequalities: a survey\.Internet mathematics3\(1\),pp\. 79–127\.Cited by:[§VI\-B](https://arxiv.org/html/2611.21879#S6.SS2.p2.1.1),[§VI\-B](https://arxiv.org/html/2611.21879#S6.SS2.p3.1.1),[§VI\-B](https://arxiv.org/html/2611.21879#S6.SS2.p3.2.1)\.相似文章
Δ-Mem:大型语言模型的高效在线记忆
提出 delta-Mem,一种轻量级在线记忆机制,利用紧凑状态矩阵并通过增量规则学习进行更新,以提升冻结大型语言模型的长上下文性能,无需全量微调或上下文扩展。
基于模型的强化学习的摊销低秩适应
本文介绍CLAW,一种使用超网络生成世界模型低秩适配器的方法,能够在有限的测试时数据下实现基于模型的强化学习中的高效在线适应。
学会记住什么:面向长时域语言代理的基于约束优化的可观测性安全记忆保留
本文将为长时域语言代理的记忆保留公式化为一个约束随机优化问题,提出了OSL-MR框架,该框架通过混合评分启发式强制实施可观测性安全学习。实验表明,在严格记忆预算下,该方法始终优于现有的启发式基线。
并行流形引导:通过残差能量塑形实现大型关联记忆的高效适应
本文提出H-Res,一种通过塑形关联记忆的能量景观来适应大型Transformer模型的方法,无需修改权重或添加提示,保留了记忆容量,且性能优于LoRA。
通过学习MDP实现安全强化学习的自适应概率性防护
本文介绍了一种用于安全强化学习的自适应概率性防护,其中防护是通过在线学习的MDP模型计算的,随着模型变得更精确而自适应。