The Sample Complexity of Policy Learning with Mu-Resets

# The Sample Complexity of Policy Learning with 𝜇-Resets
Source: [https://arxiv.org/html/2608.07772](https://arxiv.org/html/2608.07772)
\\undefine@key

newfloatplacement\\undefine@keynewfloatname\\undefine@keynewfloatfileext\\undefine@keynewfloatwithin

\(August 7, 2026\)

###### Abstract

We study policy\-based reinforcement learning under theμ\\mu\-resets interaction protocol of Kakade and Langford\[[5](https://arxiv.org/html/2608.07772#bib.bib5)\]\. This interaction protocol enables the learner to sample trajectories from a given exploratory reset distributionμ\\mu, in addition to the starting distribution\. We resolve the question raised by\[[6](https://arxiv.org/html/2608.07772#bib.bib6)\]on the role of policy realizability for the sample complexity of this problem\. Critically, the dependence on horizonHHis governed by the notion of coverage assumed of the reset distribution\. Under bounded all\-policy concentrability, we show aexp⁡\(Ω​\(H\)\)\\exp\(\\Omega\(H\)\)sample complexity lower bound; with bounded pushforward concentrability, we show the dependence on horizon is tightly characterized asexp⁡\(Θ​\(H\)\)\\exp\(\\Theta\(\\sqrt\{H\}\)\)\.

## 1Introduction

Kakade and Langford’s influential paper\[[5](https://arxiv.org/html/2608.07772#bib.bib5)\]introduced theμ\\mu\-resets interaction protocol for reinforcement learning \(RL\)\.

###### Definition 1\(μ\\mu\-Resets\)\.

The learner is given online sampling access to an exploratory reset distributionμ\\muover states\. The learner can either roll out trajectories from the initial state distribution or from the reset distributionμ\\mu\.

In this paper, we study the sample complexity of policy learning under theμ\\mu\-resets interaction protocol: given a policy classΠ\\Pi, how many trajectories does one need to collect in order to find a near\-optimal policyπ^\\widehat\{\\pi\}satisfyingVπ^≥maxπ∈Π⁡Vπ−εV^\{\{\\widehat\{\\pi\}\}\}\\geq\\max\_\{\\pi\\in\\Pi\}V^\{\\pi\}\-\\varepsilon?

Two classical algorithms have been proposed for this setting: Conservative Policy Iteration\[[5](https://arxiv.org/html/2608.07772#bib.bib5)\]for discounted, infinite\-horizon RL and Policy Search by Dynamic Programming \(PSDP\)\[[1](https://arxiv.org/html/2608.07772#bib.bib1)\]for finite\-horizon RL\. Both require a particularly stringent assumption on the representational capacity ofΠ\\Picalled*policy completeness*\. Under policy completeness, their sample complexities are polynomial in the relevant problem parameters\. Informally, policy completeness requires that the policy class is closed under the policy improvement operator\. A priori, it is unclear if this assumption is fundamentally necessary, or just needed to get the analysis to work\.

Quick aside on notation\.In the remainder of the paper, we focus on episodic, finite\-horizon RL over MDPsM=\(𝒳,𝒜,H,P,R,d1\)M=\(\\mathcal\{X\},\\mathcal\{A\},H,P,R,d\_\{1\}\)with \(large, but finite\) layered state space𝒳=⨆h=1H𝒳h\\mathcal\{X\}=\\bigsqcup\_\{h=1\}^\{H\}\\mathcal\{X\}\_\{h\}, action set𝒜\\mathcal\{A\}with cardinality\|𝒜\|=A\\lvert\\mathcal\{A\}\\rvert=A, horizonHH, transition functionPP, bounded rewardsRR, and initial state distributiond1d\_\{1\}\. Hence, the exploratory reset distributionμ=\{μh\}h=1H\\mu=\\\{\\mu\_\{h\}\\\}\_\{h=1\}^\{H\}consists of distributionsμh∈Δ​\(𝒳h\)\\mu\_\{h\}\\in\\Delta\(\\mathcal\{X\}\_\{h\}\)\. We assumeμ1=d1\\mu\_\{1\}=d\_\{1\}\(only making the learner’s job harder\); in every round of interaction, the learner picks a reset layerh∈\[H\]h\\in\[H\]and roll out a trajectory fromμh\\mu\_\{h\}\. We assume the cumulative reward∑hrh\\sum\_\{h\}r\_\{h\}in every trajectory is bounded in\[0,1\]\[0,1\]\.

\[[6](https://arxiv.org/html/2608.07772#bib.bib6)\]study the sample complexity of policy learning withμ\\mu\-resets without the assumption of policy completeness\. In the agnostic policy learning setting, they show an information\-theoretic sample complexity lower bound ofexp⁡\(Ω​\(H\)\)\\exp\(\\Omega\(H\)\)\. However, they left open the setting where the policy class satisfies*realizability*\(that the optimal policyπ⋆∈Π\\pi^\{\\star\}\\in\\Pi\)\. Policy realizability is implied by policy completeness but is a much weaker \(and arguably more natural\) assumption\. Unfortunately, the aforementionedexp⁡\(Ω​\(H\)\)\\exp\(\\Omega\(H\)\)lower bound crucially requires the non\-realizability ofΠ\\Pi\.\[[6](https://arxiv.org/html/2608.07772#bib.bib6)\]additionally show that with bounded pushforward concentrability \(to be defined below\), PSDP achievesexp⁡\(Θ​\(H\)\)\\exp\(\\Theta\(H\)\)sample complexity under policy realizability via a new upper bound analysis and algorithm\-dependent lower bound for PSDP\. In an information\-theoretic sense, the sample complexity of RL underμ\\mu\-resets with policy realizability has remained completely open\.

### Our results\.

We characterize the sample complexity of RL underμ\\mu\-resets when the policy class is realizable\. We first list three well\-studied coverage conditions which can be used to characterize the quality of the reset distributionμ\\mu\.111Throughout we use the convention that1/0=∞1/0=\\infty\.In what follows, we usedhπ​\(⋅\)∈Δ​\(𝒳h\)d^\{\\pi\}\_\{h\}\(\\cdot\)\\in\\Delta\(\\mathcal\{X\}\_\{h\}\)to denote the policy occupancy measure\.

###### Definition 2\(Policy\-class concentrability\)\.

The policy\-class concentrability coefficient is

C𝖼𝗈𝗇𝖼​\(μ;Π,M\):=maxπ∈Π⁡maxh∈\[H\]⁡‖dhπμh‖∞\.C\_\{\\mathsf\{conc\}\}\(\\mu;\\Pi,M\):=\\max\_\{\\pi\\in\\Pi\}\\max\_\{h\\in\[H\]\}\\left\\\|\\frac\{d\_\{h\}^\{\\pi\}\}\{\\mu\_\{h\}\}\\right\\\|\_\{\\infty\}\.

###### Definition 3\(All\-policy concentrability\)\.

LetΠall\\Pi\_\{\\mathrm\{all\}\}denote the set of all Markov policies onMM\. The all\-policy concentrability coefficient is

C𝖺𝗅𝗅​\(μ;M\):=maxπ∈Πall⁡maxh∈\[H\]⁡‖dhπμh‖∞\.C\_\{\\mathsf\{all\}\}\(\\mu;M\):=\\max\_\{\\pi\\in\\Pi\_\{\\mathrm\{all\}\}\}\\max\_\{h\\in\[H\]\}\\left\\\|\\frac\{d\_\{h\}^\{\\pi\}\}\{\\mu\_\{h\}\}\\right\\\|\_\{\\infty\}\.

###### Definition 4\(Pushforward concentrability\)\.

The pushforward concentrability coefficient is

C𝗉𝗎𝗌𝗁\(μ;M\):=maxh∈\[H−1\]maxx∈𝒳h,a∈𝒜∥P\(⋅∣x,a\)μh\+1∥∞\.C\_\{\\mathsf\{push\}\}\(\\mu;M\):=\\max\_\{h\\in\[H\-1\]\}\\max\_\{x\\in\\mathcal\{X\}\_\{h\},\\,a\\in\\mathcal\{A\}\}\\left\\\|\\frac\{P\(\\cdot\\mid x,a\)\}\{\\mu\_\{h\+1\}\}\\right\\\|\_\{\\infty\}\.

It is straightforward from the definitions to show thatC𝖼𝗈𝗇𝖼​\(μ;Π,M\)≤C𝖺𝗅𝗅​\(μ;M\)≤C𝗉𝗎𝗌𝗁​\(μ;M\)C\_\{\\mathsf\{conc\}\}\(\\mu;\\Pi,M\)\\leq C\_\{\\mathsf\{all\}\}\(\\mu;M\)\\leq C\_\{\\mathsf\{push\}\}\(\\mu;M\)\. When clear from the context, we writeC𝖼𝗈𝗇𝖼C\_\{\\mathsf\{conc\}\},C𝖺𝗅𝗅C\_\{\\mathsf\{all\}\}, andC𝗉𝗎𝗌𝗁C\_\{\\mathsf\{push\}\}\.

Our main results are stated below and summarized in[Table1](https://arxiv.org/html/2608.07772#S1.T1)\.

C𝖼𝗈𝗇𝖼C\_\{\\mathsf\{conc\}\}C𝖺𝗅𝗅C\_\{\\mathsf\{all\}\}C𝗉𝗎𝗌𝗁C\_\{\\mathsf\{push\}\}Policy Completeness✓\[[1](https://arxiv.org/html/2608.07772#bib.bib1)\],see also\[Thm\. 1 of[6](https://arxiv.org/html/2608.07772#bib.bib6)\]⟹\\Longrightarrow✓⟹\\Longrightarrow✓Policy Realizability✗⟸\\Longleftarrow✗Thm\.[1](https://arxiv.org/html/2608.07772#Thmtheorem1)✗⋆Thms\.[2](https://arxiv.org/html/2608.07772#Thmtheorem2)–[3](https://arxiv.org/html/2608.07772#Thmtheorem3)Agnostic✗⟸\\Longleftarrow✗⟸\\Longleftarrow✗\[Thm\. 3 of[6](https://arxiv.org/html/2608.07772#bib.bib6)\]Table 1:Sample complexity underμ\\mu\-resets\. Rows denote the different representational assumptions onΠ\\Pi; columns denote coverage assumptions on the resetμ\\mu\. A✓denotespoly​\(C,A,H​log⁡\|Π\|,ε−1\)\\mathrm\{poly\}\(C,A,H\\log\\lvert\\Pi\\rvert,\\varepsilon^\{\-1\}\)sample complexity \(whereC∈\{C𝖼𝗈𝗏,C𝖺𝗅𝗅,C𝗉𝗎𝗌𝗁\}C\\in\\\{C\_\{\\mathsf\{cov\}\},C\_\{\\mathsf\{all\}\},C\_\{\\mathsf\{push\}\}\\\}\), while✗denotes aexp⁡\(Ω​\(H\)\)\\exp\(\\Omega\(H\)\)lower bound\. The starred entry is insteadexp⁡\(Θ​\(H\)\)\\exp\(\\Theta\(\\sqrt\{H\}\)\)for constantAAandC𝗉𝗎𝗌𝗁C\_\{\\mathsf\{push\}\}\. Arrows show implications of upper and lower bounds to weaker statements\.###### Theorem 1\(Lower bound forC𝖺𝗅𝗅C\_\{\\mathsf\{all\}\}\)\.

For any sufficiently largeH∈ℕH\\in\\mathbb\{N\}, there exists a policy classΠ\\Piof size2H2^\{H\}; a family of MDPsℳ\\mathcal\{M\}over a state space of size2O​\(H\)2^\{O\(H\)\}, binary action space, and horizonHH; and known reset distributionμ\\mu; such that everyM∈ℳM\\in\\mathcal\{M\}satisfies \(i\)Π\\Piis realizable, and \(ii\)μ\\musatisfiesC𝖺𝗅𝗅​\(μ;M\)≤4C\_\{\\mathsf\{all\}\}\(\\mu;M\)\\leq 4\. Any proper deterministic algorithm that returns a1/81/8\-optimal policy with constant probability must sample at least2Ω​\(H\)2^\{\\Omega\(H\)\}trajectories for some MDP inℳ\\mathcal\{M\}\.

Thus, if we assume the reset has boundedC𝖺𝗅𝗅C\_\{\\mathsf\{all\}\}, we still require the stringent policy completeness assumption in order to get sample\-efficient learning, and realizability doesn’t buy us anything\.

Next, we turn to the assumption of bounded pushforward concentrability of the resetμ\\mu\.

###### Theorem 2\(Upper bound forC𝗉𝗎𝗌𝗁C\_\{\\mathsf\{push\}\}\)\.

LetMMbe an MDP and supposeΠ\\Piis a realizable class of policies\. Furthermore, suppose the reset distributionsμ\\musatisfy pushforward concentrability with parameterC𝗉𝗎𝗌𝗁C\_\{\\mathsf\{push\}\}\. Then for everyε,δ∈\(0,1\)\\varepsilon,\\delta\\in\(0,1\), there is an algorithm usingμ\\mu\-resets that, with probability at least1−δ1\-\\delta, returns anε\\varepsilon\-optimal policyπ^\\widehat\{\\pi\}using at most

O​\(\(A​C𝗉𝗎𝗌𝗁\)2​H​H3/2ε2​log⁡H​\|Π\|δ\)trajectories\.O\\left\(\\frac\{\(AC\_\{\\mathsf\{push\}\}\)^\{2\\sqrt\{H\}\}H^\{3/2\}\}\{\\varepsilon^\{2\}\}\\log\\frac\{H\\lvert\\Pi\\rvert\}\{\\delta\}\\right\)\\quad\\mathrm\{trajectories\.\}

###### Theorem 3\(Lower bound forC𝗉𝗎𝗌𝗁C\_\{\\mathsf\{push\}\}\)\.

For any sufficiently largeH∈ℕH\\in\\mathbb\{N\}, there exists a policy classΠ\\Piof size2H2^\{\\sqrt\{H\}\}; a family of MDPsℳ\\mathcal\{M\}over a state space of size2O​\(H\)2^\{O\(\\sqrt\{H\}\)\}, binary action space, and horizonHH; and a known reset distributionμ\\mu; such that everyM∈ℳM\\in\\mathcal\{M\}satisfies \(i\)Π\\Piis realizable, and \(ii\)μ\\musatisfiesC𝗉𝗎𝗌𝗁​\(μ;M\)≤8C\_\{\\mathsf\{push\}\}\(\\mu;M\)\\leq 8\. Any proper deterministic algorithm that returns a1/81/8\-optimal policy with constant probability must sample at least2Ω​\(H\)2^\{\\Omega\(\\sqrt\{H\}\)\}trajectories for some MDP inℳ\\mathcal\{M\}\.

[Theorem3](https://arxiv.org/html/2608.07772#Thmtheorem3)can be viewed as an information\-theoretic strengthening of the algorithmic lower bound of\[Theorem 8,[6](https://arxiv.org/html/2608.07772#bib.bib6)\]that additionally builds inH\\sqrt\{H\}\-length combination locks into the construction\.

Although these bounds remain exponential, together[Theorem2](https://arxiv.org/html/2608.07772#Thmtheorem2)and[3](https://arxiv.org/html/2608.07772#Thmtheorem3)show that bounded pushforward concentrability changes the horizon dependence fromexp⁡\(Θ​\(H\)\)\\exp\(\\Theta\(H\)\)toexp⁡\(Θ​\(H\)\)\\exp\(\\Theta\(\\sqrt\{H\}\)\)\. This comparison has three consequences\. First, realizability yields an exponential improvement over the agnostic setting, where\[Theorem 3 of[6](https://arxiv.org/html/2608.07772#bib.bib6)\]prove a2Ω​\(H\)2^\{\\Omega\(H\)\}lower bound\. Second, PSDP requiresexp⁡\(Θ​\(H\)\)\\exp\(\\Theta\(H\)\)samples under the same realizability and pushforward assumptions\[Theorems 6 and 8 of[6](https://arxiv.org/html/2608.07772#bib.bib6)\], and is therefore suboptimal\. Third, our results give a quantitative separation between all\-policy and pushforward concentrability, analogous to separations known in offline RL\[[2](https://arxiv.org/html/2608.07772#bib.bib2);[4](https://arxiv.org/html/2608.07772#bib.bib4);[8](https://arxiv.org/html/2608.07772#bib.bib8)\]\.

### Statement of AI Use\.

Results were obtained via GPT 5\.6 Pro, with assistance from Charlie Hou and Xuchen You\. We used GPT 5\.6 Sol Codex to aid in writing and presentation\.

## 2Lower Bound under All\-Policy Concentrability

In this section, we sketch the proof of[Theorem1](https://arxiv.org/html/2608.07772#Thmtheorem1)\. We first describe the construction and then explain why reset access does not help\. We omit the formal information\-theoretic arguments, which follow the standard analysis for rich\-observation combination locks\[[7](https://arxiv.org/html/2608.07772#bib.bib7);[3](https://arxiv.org/html/2608.07772#bib.bib3);[6](https://arxiv.org/html/2608.07772#bib.bib6)\]\.

### Lower bound construction\.

We use a variant of the rich\-observation combination lock, which is essentially a Block MDP with enormous decoder class\. See[Figure1](https://arxiv.org/html/2608.07772#S2.F1)for an illustration\. For simplicity, assume thatHHis even\. We let𝒜=\{0,1\}\\mathcal\{A\}=\\\{0,1\\\}and define the policy class to be open\-loop policies:

Π=\{π:πh​\(x\)≡ah​for every​x∈𝒳h,\(a1,…,aH\)∈\{0,1\}H\},thus,​\|Π\|=2H\.\\Pi=\\left\\\{\\pi:\\pi\_\{h\}\(x\)\\equiv a\_\{h\}\\ \\text\{for every \}x\\in\\mathcal\{X\}\_\{h\},\\ \(a\_\{1\},\\ldots,a\_\{H\}\)\\in\\\{0,1\\\}^\{H\}\\right\\\},\\quad\\text\{thus, \}\\lvert\\Pi\\rvert=2^\{H\}\.Each MDP instance is parameterized by an optimal policyπ⋆∈Π\\pi^\{\\star\}\\in\\Pi\. Its firstH/2H/2actions determine the value from the initial state; its actions from layerH/2\+1H/2\+1through layerH−1H\-1serve only to mask information in reset trajectories\. The final action is irrelevant\.

Every layer has four latent states: a good statesh𝖦s\_\{h\}^\{\\mathsf\{G\}\}, a bad statesh𝖡s\_\{h\}^\{\\mathsf\{B\}\}, a verifier statesh𝖵s\_\{h\}^\{\\mathsf\{V\}\}, and a neutral statesh𝖭s\_\{h\}^\{\\mathsf\{N\}\}\. The initial latent state iss1𝖦s\_\{1\}^\{\\mathsf\{G\}\}\. In the first half of the MDP, the good–bad and verifier–neutral pairs form two combination locks\. The optimal action keeps the learner on the good or verifier track, whereas an incorrect action transits the learner fromsh𝖦s\_\{h\}^\{\\mathsf\{G\}\}tosh\+1𝖡s\_\{h\+1\}^\{\\mathsf\{B\}\}and fromsh𝖵s\_\{h\}^\{\\mathsf\{V\}\}tosh\+1𝖭s\_\{h\+1\}^\{\\mathsf\{N\}\}\. In the second half, the good/neutral states advance under either action, while the verifier and bad states form a new “poison” combination lock\. Formally, for everyh∈\[H−1\]h\\in\[H\-1\], the latent dynamicsP𝗅𝖺𝗍P\_\{\\mathsf\{lat\}\}are

P𝗅𝖺𝗍\(⋅∣sh𝖦,a\)\\displaystyle P\_\{\\mathsf\{lat\}\}\(\\cdot\\mid s\_\{h\}^\{\\mathsf\{G\}\},a\)=\{δsh\+1𝖦a=πh⋆​and​h≤H/2,δsh\+1𝖦h\>H/2,δsh\+1𝖡otherwise,\\displaystyle=P𝗅𝖺𝗍\(⋅∣sh𝖡,a\)\\displaystyle\\qquad P\_\{\\mathsf\{lat\}\}\(\\cdot\\mid s\_\{h\}^\{\\mathsf\{B\}\},a\)=δsh\+1𝖡,\\displaystyle=\\delta\_\{s\_\{h\+1\}^\{\\mathsf\{B\}\}\},P𝗅𝖺𝗍\(⋅∣sh𝖵,a\)\\displaystyle P\_\{\\mathsf\{lat\}\}\(\\cdot\\mid s\_\{h\}^\{\\mathsf\{V\}\},a\)=\{δsh\+1𝖵a=πh⋆,δsh\+1𝖭a≠πh⋆​and​h≤H/2,δsh\+1𝖡a≠πh⋆​and​h\>H/2,\\displaystyle=P𝗅𝖺𝗍\(⋅∣sh𝖭,a\)\\displaystyle P\_\{\\mathsf\{lat\}\}\(\\cdot\\mid s\_\{h\}^\{\\mathsf\{N\}\},a\)=δsh\+1𝖭\.\\displaystyle=\\delta\_\{s\_\{h\+1\}^\{\\mathsf\{N\}\}\}\.
![Refer to caption](https://arxiv.org/html/2608.07772v1/x1.png)Figure 1:Construction used for proof of Theorem[1](https://arxiv.org/html/2608.07772#Thmtheorem1)\.Rewards are nonzero only in the final layer:

R𝗅𝖺𝗍​\(s,a\)=\{1s=sH𝖵,12s∈\{sH𝖦,sH𝖭\},0otherwise\.R\_\{\\mathsf\{lat\}\}\(s,a\)=\\begin\{cases\}1&s=s\_\{H\}^\{\\mathsf\{V\}\},\\\\ \\frac\{1\}\{2\}&s\\in\\\{s\_\{H\}^\{\\mathsf\{G\}\},s\_\{H\}^\{\\mathsf\{N\}\}\\\},\\\\ 0&\\text\{otherwise\}\.\\end\{cases\}With the latent dynamics fully specified, we can define the set of Block MDP instances which are parameterized by optimal policyπ⋆∈Π\\pi^\{\\star\}\\in\\Piand decoderϕ∈Φ\\phi\\in\\Phi, asℳ=\{Mπ⋆,ϕ:π⋆∈Π,ϕ∈Φ\}\\mathcal\{M\}=\\\{M\_\{\\pi^\{\\star\},\\phi\}:\\pi^\{\\star\}\\in\\Pi,\\ \\phi\\in\\Phi\\\}\. To define the decoder class, we use the standard idea from\[[7](https://arxiv.org/html/2608.07772#bib.bib7);[6](https://arxiv.org/html/2608.07772#bib.bib6)\]: for every layer let𝒳h\\mathcal\{X\}\_\{h\}be a large \(observed\) state space of sizem=2c​Hm=2^\{cH\}for some sufficiently largec\>0c\>0and defineΦ\\Phito be the set of all possible decodersϕ:𝒳→𝒮\\phi:\\mathcal\{X\}\\to\\mathcal\{S\}which assign equal number of \(observed\) states to every latent state\. A transition tos∈𝒮hs\\in\\mathcal\{S\}\_\{h\}emits an observation according to the emission functionψ​\(s\)=Unif​\(\{x∈𝒳h:ϕ​\(x\)=s\}\)\\psi\(s\)=\\mathrm\{Unif\}\\bigl\(\\\{x\\in\\mathcal\{X\}\_\{h\}:\\phi\(x\)=s\\\}\\bigr\)\.

Finally, the reset distributionμ\\muis defined as:

μh,ϕ=\{ψ​\(s1𝖦\),h=1,14​ψ​\(sh𝖦\)\+14​ψ​\(sh𝖡\)\+14​ψ​\(sh𝖵\)\+14​ψ​\(sh𝖭\),2≤h≤H/2,12​ψ​\(sh𝖦\)\+12​ψ​\(sh𝖡\),H/2<h≤H\.\\mu\_\{h,\\phi\}=\\begin\{cases\}\\psi\(s\_\{1\}^\{\\mathsf\{G\}\}\),&h=1,\\\\ \\frac\{1\}\{4\}\\psi\(s\_\{h\}^\{\\mathsf\{G\}\}\)\+\\frac\{1\}\{4\}\\psi\(s\_\{h\}^\{\\mathsf\{B\}\}\)\+\\frac\{1\}\{4\}\\psi\(s\_\{h\}^\{\\mathsf\{V\}\}\)\+\\frac\{1\}\{4\}\\psi\(s\_\{h\}^\{\\mathsf\{N\}\}\),&2\\leq h\\leq H/2,\\\\ \\frac\{1\}\{2\}\\psi\(s\_\{h\}^\{\\mathsf\{G\}\}\)\+\\frac\{1\}\{2\}\\psi\(s\_\{h\}^\{\\mathsf\{B\}\}\),&H/2<h\\leq H\.\\end\{cases\}That is, the first state is emitted from the good state; for the other layers in the first half, the reset is uniform over all four latent states; the second\-half resets are uniform over the good and bad states\. It is clear that for everyπ⋆∈Π\\pi^\{\\star\}\\in\\Piandϕ∈Φ\\phi\\in\\Phi,

C𝖺𝗅𝗅​\(μϕ;Mπ⋆,ϕ\)≤4\.C\_\{\\mathsf\{all\}\}\(\\mu\_\{\\phi\};M\_\{\\pi^\{\\star\},\\phi\}\)\\leq 4\.Lastly, one can also check thatπ⋆\\pi^\{\\star\}is optimal under these dynamics from any state, and it achieves value of1/21/2from the starting distributionμ1\\mu\_\{1\}\.

### Why doesn’t reset access allow sample\-efficient learning of the optimal policy?

Fix an instanceMπ⋆,ϕM\_\{\\pi^\{\\star\},\\phi\}\. The large decoder classΦ\\Phihas statistical complexitylog⁡\|Φ\|\\log\\lvert\\Phi\\rvertwhich is exponential inHH\. With high probability, every observed state is a fresh, nonrepeated observation\. Thus, transition data fromMπ⋆,ϕM\_\{\\pi^\{\\star\},\\phi\}leaks essentially no information about the underlyingπ⋆\\pi^\{\\star\}, and the learner is forced to learnπ⋆\\pi^\{\\star\}from reward observations\.

Observe that a trajectory from the initial distribution only achieves positive reward iff the firstH/2H/2actions exactly matchπ⋆\\pi^\{\\star\}, thus requiring2Ω​\(H\)2^\{\\Omega\(H\)\}samples to learn\. Therefore, the learner must also try to utilize the trajectories rolled out from resets\. We next argue that this is also doomed to fail:

- •Rolling out from resetsh\>H/2h\>H/2are useless \- no matter what policy the learner plays, they will see rewards of1/21/2and0equally often\.
- •Rolling out from resets2≤h≤H/22\\leq h\\leq H/2is a more delicate case\. Fix any partial policyπh:H−1∈\{0,1\}H−h\\pi\_\{h:H\-1\}\\in\\\{0,1\\\}^\{H\-h\}, and letZZbe the random variable representing the reward we observe by sampling a stateUnif​\(𝒳h\)\\mathrm\{Unif\}\(\\mathcal\{X\}\_\{h\}\)then rolling out withπh:H−1\\pi\_\{h:H\-1\}\. Then ifπh:H≠πh:H⋆\\pi\_\{h:H\}\\neq\\pi^\{\\star\}\_\{h:H\}, thenZZis1/21/2or0with equal probability\. Also, ifπh:H=πh:H⋆\\pi\_\{h:H\}=\\pi^\{\\star\}\_\{h:H\}, thenZZis 1 with probability1/41/4,1/21/2with probability1/21/2, and0with probability1/41/4\. This calculation elucidates the role of the “poison” combination lock: it effectively prevents the learner from just doing backwards induction from layerH/2H/2because this will only work if the learner already knows poison suffixπH/2:H−1⋆\\pi^\{\\star\}\_\{H/2:H\-1\}\(which itself can only be randomly guessed with exponentially small probability\)\.

Thus, together with the initial distribution argument, we have argued that there is no way for the learner to use2O​\(H\)2^\{O\(H\)\}samples to properly identifyπ⋆\\pi^\{\\star\}given a random instance fromℳ\\mathcal\{M\}\.

## 3Upper Bound under Pushforward Concentrability

In this section, we prove our main upper bound usingBlockPSDP, a blockwise variant of PSDP whose pseudocode is given in[Algorithm1](https://arxiv.org/html/2608.07772#alg1)\.

### Algorithm\.

Fix a number of blocksK∈\[H\]K\\in\[H\]and letL=H/KL=H/K\. We may assume thatLLis an integer; otherwise, we can pad the last block\. For eachk∈\[K\]k\\in\[K\], set

𝗌𝗍𝖺𝗋𝗍k=1\+\(k−1\)​L,𝖡𝗅𝗈𝖼𝗄k=\{𝗌𝗍𝖺𝗋𝗍k,…,k​L\}\.\\mathsf\{start\}\_\{k\}=1\+\(k\-1\)L,\\qquad\\mathsf\{Block\}\_\{k\}=\\\{\\mathsf\{start\}\_\{k\},\\ldots,kL\\\}\.The algorithm works backward over these blocks\. At blockkk, it explores uniformly until the end of the block and then follows the suffix already learned on later blocks\. Here∘\\circdenotes layerwise concatenation of partial policies\. We writeΠh\\Pi\_\{h\}for the restriction ofΠ\\Pito layerhh, andΠ𝖡𝗅𝗈𝖼𝗄k\\Pi\_\{\\mathsf\{Block\}\_\{k\}\}for its restriction to𝖡𝗅𝗈𝖼𝗄k\\mathsf\{Block\}\_\{k\}\.

Algorithm 1BlockPSDP1:Reset distributions

μ=\{μh\}h∈\[H\]\\mu=\\\{\\mu\_\{h\}\\\}\_\{h\\in\[H\]\}, policy class

Π\\Pi, number of blocks

KK, and sample size

nn\.

2:for

k=K,…,1k=K,\\ldots,1do

3:Initialize dataset

𝒟k=∅\\mathcal\{D\}\_\{k\}=\\varnothing\.

4:for

nntimesdo

5:Sample

x𝗌𝗍𝖺𝗋𝗍k∼μ𝗌𝗍𝖺𝗋𝗍kx\_\{\\mathsf\{start\}\_\{k\}\}\\sim\\mu\_\{\\mathsf\{start\}\_\{k\}\}and

a𝖡𝗅𝗈𝖼𝗄k∼Unif​\(𝒜L\)a\_\{\\mathsf\{Block\}\_\{k\}\}\\sim\\mathrm\{Unif\}\(\\mathcal\{A\}^\{L\}\), generating

τk=\(xh,ah\)h∈𝖡𝗅𝗈𝖼𝗄k\\tau\_\{k\}=\(x\_\{h\},a\_\{h\}\)\_\{h\\in\\mathsf\{Block\}\_\{k\}\}\.

6:Let

vk≔∑h=𝗌𝗍𝖺𝗋𝗍kHrhv\_\{k\}\\coloneqq\\sum\_\{h=\\mathsf\{start\}\_\{k\}\}^\{H\}r\_\{h\}be the return from executing

a𝖡𝗅𝗈𝖼𝗄k∘π^𝗌𝗍𝖺𝗋𝗍k\+1:Ha\_\{\\mathsf\{Block\}\_\{k\}\}\\circ\\widehat\{\\pi\}\_\{\\mathsf\{start\}\_\{k\+1\}:H\}from

x𝗌𝗍𝖺𝗋𝗍kx\_\{\\mathsf\{start\}\_\{k\}\}\.

7:Set

𝒟k←𝒟k∪\{\(τk,vk\)\}\\mathcal\{D\}\_\{k\}\\leftarrow\\mathcal\{D\}\_\{k\}\\cup\\\{\(\\tau\_\{k\},v\_\{k\}\)\\\}\.

8:Call policy optimization oracle:

π^𝖡𝗅𝗈𝖼𝗄k∈argmaxπ𝖡𝗅𝗈𝖼𝗄k∈Π𝖡𝗅𝗈𝖼𝗄kALn​∑\(τk,vk\)∈𝒟k𝟙​\{ah=πh​\(xh\)​∀h∈𝖡𝗅𝗈𝖼𝗄k\}​vk\\widehat\{\\pi\}\_\{\\mathsf\{Block\}\_\{k\}\}\\in\\displaystyle\\operatorname\*\{argmax\}\_\{\\pi\_\{\\mathsf\{Block\}\_\{k\}\}\\in\\Pi\_\{\\mathsf\{Block\}\_\{k\}\}\}\\frac\{A^\{L\}\}\{n\}\\sum\_\{\(\\tau\_\{k\},v\_\{k\}\)\\in\\mathcal\{D\}\_\{k\}\}\\mathbbm\{1\}\\left\\\{a\_\{h\}=\\pi\_\{h\}\(x\_\{h\}\)\\ \\forall h\\in\\mathsf\{Block\}\_\{k\}\\right\\\}\\,v\_\{k\}\.

9:Set

π^𝗌𝗍𝖺𝗋𝗍k:H←π^𝖡𝗅𝗈𝖼𝗄k∘π^𝗌𝗍𝖺𝗋𝗍k\+1:H\\widehat\{\\pi\}\_\{\\mathsf\{start\}\_\{k\}:H\}\\leftarrow\\widehat\{\\pi\}\_\{\\mathsf\{Block\}\_\{k\}\}\\circ\\widehat\{\\pi\}\_\{\\mathsf\{start\}\_\{k\+1\}:H\}\.

10:return

π^1:H\\widehat\{\\pi\}\_\{1:H\}\.

Recall that PSDP learns the policy via resets one layer at a time\. Under pushforward concentrability, its error can amplify by a factor ofC𝗉𝗎𝗌𝗁C\_\{\\mathsf\{push\}\}at each layer\[[6](https://arxiv.org/html/2608.07772#bib.bib6)\]\. The key idea ofBlockPSDPis to learnLLconsecutive layers at once by importance sampling trajectories that explore uniformly within a block\. This costsALA^\{L\}in sample complexity, but error amplification occurs only across theK−1K\-1boundaries between theK=H/LK=H/Lblocks\. Balancing these two terms gives the desired sample complexity\.

### Proof of[Theorem2](https://arxiv.org/html/2608.07772#Thmtheorem2)\.

The analysis has two steps: estimation within each block and error propagation across block boundaries\.

### Importance sampling guarantee\.

Fix a blockkk, and suppose we have constructedπ^𝗌𝗍𝖺𝗋𝗍k\+1:H\\widehat\{\\pi\}\_\{\\mathsf\{start\}\_\{k\+1\}:H\}\. Forπ𝖡𝗅𝗈𝖼𝗄k∈Π𝖡𝗅𝗈𝖼𝗄k\\pi\_\{\\mathsf\{Block\}\_\{k\}\}\\in\\Pi\_\{\\mathsf\{Block\}\_\{k\}\}, define

Jk​\(π𝖡𝗅𝗈𝖼𝗄k\)=𝔼x∼μ𝗌𝗍𝖺𝗋𝗍k⁡\[V𝗌𝗍𝖺𝗋𝗍kπ𝖡𝗅𝗈𝖼𝗄k∘π^𝗌𝗍𝖺𝗋𝗍k\+1:H​\(x\)\]\.J\_\{k\}\(\\pi\_\{\\mathsf\{Block\}\_\{k\}\}\)=\\operatorname\{\\mathbb\{E\}\}\_\{x\\sim\\mu\_\{\\mathsf\{start\}\_\{k\}\}\}\\left\[V\_\{\\mathsf\{start\}\_\{k\}\}^\{\\,\\pi\_\{\\mathsf\{Block\}\_\{k\}\}\\circ\\widehat\{\\pi\}\_\{\\mathsf\{start\}\_\{k\+1\}:H\}\}\(x\)\\right\]\.The empirical objective in[Algorithm1](https://arxiv.org/html/2608.07772#alg1)is the standard trajectory importance sampling estimate forJk​\(π𝖡𝗅𝗈𝖼𝗄k\)J\_\{k\}\(\\pi\_\{\\mathsf\{Block\}\_\{k\}\}\)\. Standard concentration for importance sampling\[[3](https://arxiv.org/html/2608.07772#bib.bib3)\]implies that for anyη∈\(0,1\]\\eta\\in\(0,1\], as long as

n≥c​ALη2​log⁡2​\|Π\|δ,n\\geq c\\frac\{A^\{L\}\}\{\\eta^\{2\}\}\\log\\frac\{2\\lvert\\Pi\\rvert\}\{\\delta\},\(1\)for some sufficiently largec\>0c\>0, then, with probability at least1−δ1\-\\delta,

Jk​\(π^𝖡𝗅𝗈𝖼𝗄k\)≥Jk​\(π𝖡𝗅𝗈𝖼𝗄k⋆\)−η\.J\_\{k\}\\bigl\(\\widehat\{\\pi\}\_\{\\mathsf\{Block\}\_\{k\}\}\\bigr\)\\geq J\_\{k\}\\bigl\(\\pi^\{\\star\}\_\{\\mathsf\{Block\}\_\{k\}\}\\bigr\)\-\\eta\.\(2\)
###### Lemma 1\(Error propagation\)\.

Fork∈\[K\]k\\in\[K\], let

ek=𝔼x∼μ𝗌𝗍𝖺𝗋𝗍k⁡\[V𝗌𝗍𝖺𝗋𝗍kπ⋆​\(x\)−V𝗌𝗍𝖺𝗋𝗍kπ^𝗌𝗍𝖺𝗋𝗍k:H​\(x\)\]\.e\_\{k\}=\\operatorname\{\\mathbb\{E\}\}\_\{x\\sim\\mu\_\{\\mathsf\{start\}\_\{k\}\}\}\\left\[V\_\{\\mathsf\{start\}\_\{k\}\}^\{\\pi^\{\\star\}\}\(x\)\-V\_\{\\mathsf\{start\}\_\{k\}\}^\{\\widehat\{\\pi\}\_\{\\mathsf\{start\}\_\{k\}:H\}\}\(x\)\\right\]\.On the event \([2](https://arxiv.org/html/2608.07772#S3.E2)\),

eK≤η,ek≤η\+C𝗉𝗎𝗌𝗁​ek\+1for​k<K\.e\_\{K\}\\leq\\eta,\\qquad e\_\{k\}\\leq\\eta\+C\_\{\\mathsf\{push\}\}e\_\{k\+1\}\\quad\\text\{for \}k<K\.\(3\)

###### Proof\.

Fork<Kk<K, letνk\+1\\nu\_\{k\+1\}denote the distribution ofx𝗌𝗍𝖺𝗋𝗍k\+1x\_\{\\mathsf\{start\}\_\{k\+1\}\}obtained by drawingx𝗌𝗍𝖺𝗋𝗍k∼μ𝗌𝗍𝖺𝗋𝗍kx\_\{\\mathsf\{start\}\_\{k\}\}\\sim\\mu\_\{\\mathsf\{start\}\_\{k\}\}and executingπ𝖡𝗅𝗈𝖼𝗄k⋆\\pi^\{\\star\}\_\{\\mathsf\{Block\}\_\{k\}\}\. Then

ek\\displaystyle e\_\{k\}=Jk​\(π𝖡𝗅𝗈𝖼𝗄k⋆\)−Jk​\(π^𝖡𝗅𝗈𝖼𝗄k\)\+𝔼x∼νk\+1⁡\[V𝗌𝗍𝖺𝗋𝗍k\+1π⋆​\(x\)−V𝗌𝗍𝖺𝗋𝗍k\+1π^𝗌𝗍𝖺𝗋𝗍k\+1:H​\(x\)\]⏟continuation gap\\displaystyle=J\_\{k\}\\bigl\(\\pi^\{\\star\}\_\{\\mathsf\{Block\}\_\{k\}\}\\bigr\)\-J\_\{k\}\\bigl\(\\widehat\{\\pi\}\_\{\\mathsf\{Block\}\_\{k\}\}\\bigr\)\+\\underbrace\{\\operatorname\{\\mathbb\{E\}\}\_\{x\\sim\\nu\_\{k\+1\}\}\\left\[V\_\{\\mathsf\{start\}\_\{k\+1\}\}^\{\\pi^\{\\star\}\}\(x\)\-V\_\{\\mathsf\{start\}\_\{k\+1\}\}^\{\\widehat\{\\pi\}\_\{\\mathsf\{start\}\_\{k\+1\}:H\}\}\(x\)\\right\]\}\_\{\\text\{continuation gap\}\}≤η\+𝔼x∼νk\+1⁡\[V𝗌𝗍𝖺𝗋𝗍k\+1π⋆​\(x\)−V𝗌𝗍𝖺𝗋𝗍k\+1π^𝗌𝗍𝖺𝗋𝗍k\+1:H​\(x\)\]\\displaystyle\\leq\\eta\+\\operatorname\{\\mathbb\{E\}\}\_\{x\\sim\\nu\_\{k\+1\}\}\\left\[V\_\{\\mathsf\{start\}\_\{k\+1\}\}^\{\\pi^\{\\star\}\}\(x\)\-V\_\{\\mathsf\{start\}\_\{k\+1\}\}^\{\\widehat\{\\pi\}\_\{\\mathsf\{start\}\_\{k\+1\}:H\}\}\(x\)\\right\]≤η\+C𝗉𝗎𝗌𝗁​ek\+1\.\\displaystyle\\leq\\eta\+C\_\{\\mathsf\{push\}\}e\_\{k\+1\}\.The last line uses pushforward concentrability as well as the optimality ofπ⋆\\pi^\{\\star\}, which ensures that the continuation gap between policies is pointwise nonnegative\. For the last block there is no continuation gap, so we have

eK=JK​\(π𝖡𝗅𝗈𝖼𝗄K⋆\)−JK​\(π^𝖡𝗅𝗈𝖼𝗄K\)≤η\.e\_\{K\}=J\_\{K\}\\bigl\(\\pi^\{\\star\}\_\{\\mathsf\{Block\}\_\{K\}\}\\bigr\)\-J\_\{K\}\\bigl\(\\widehat\{\\pi\}\_\{\\mathsf\{Block\}\_\{K\}\}\\bigr\)\\leq\\eta\.∎

### Final guarantee\.

At every block let the number of rollouts be

n=O​\(AL​C𝗉𝗎𝗌𝗁2​\(K−1\)​K2ε2​log⁡2​\|Π\|δ\)\.n=O\\left\(\\frac\{A^\{L\}C\_\{\\mathsf\{push\}\}^\{2\(K\-1\)\}K^\{2\}\}\{\\varepsilon^\{2\}\}\\log\\frac\{2\\lvert\\Pi\\rvert\}\{\\delta\}\\right\)\.Then by the importance sampling guarantee,[Lemma1](https://arxiv.org/html/2608.07772#Thmlemma1), and a union bound, with probability at least1−K​δ1\-K\\delta,Vπ⋆−Vπ^1:H=e1≤εV^\{\\pi^\{\\star\}\}\-V^\{\\widehat\{\\pi\}\_\{1:H\}\}=e\_\{1\}\\leq\\varepsilon\. For simplicity, takeK=L=HK=L=\\sqrt\{H\}and assume these quantities are integers\. Replacingδ\\deltabyδ/K\\delta/Kgives success probability at least1−δ1\-\\deltaand

n​K=O​\(\(A​C𝗉𝗎𝗌𝗁\)2​H​H3/2ε2​log⁡H​\|Π\|δ\)\.nK=O\\left\(\\frac\{\(AC\_\{\\mathsf\{push\}\}\)^\{2\\sqrt\{H\}\}H^\{3/2\}\}\{\\varepsilon^\{2\}\}\\log\\frac\{H\\lvert\\Pi\\rvert\}\{\\delta\}\\right\)\.This completes the proof of[Theorem2](https://arxiv.org/html/2608.07772#Thmtheorem2)\.

## 4Lower Bound under Pushforward Concentrability

In this section, we sketch the proof of[Theorem3](https://arxiv.org/html/2608.07772#Thmtheorem3)\. We first describe the construction and then explain why reset access does not help\. As in[Section2](https://arxiv.org/html/2608.07772#S2), we omit the formal information\-theoretic argument, which follows from a standard random\-decoder analysis and the reward identity below\. We useKKblocks of lengthLL, so thatH=K​LH=KL\. For the lower bound, takeK=L=HK=L=\\sqrt\{H\}and assume these quantities are integers\.

### Lower bound construction\.

We use a recursive rich\-observation combination lock; see[Figure2](https://arxiv.org/html/2608.07772#S4.F2)for an illustration\. Again let𝒜=\{0,1\}\\mathcal\{A\}=\\\{0,1\\\}\. Partition the horizon into𝖡𝗅𝗈𝖼𝗄1,…,𝖡𝗅𝗈𝖼𝗄K\\mathsf\{Block\}\_\{1\},\\ldots,\\mathsf\{Block\}\_\{K\}, where

𝖡𝗅𝗈𝖼𝗄k:=\{\(k−1\)​L\+1,…,k​L\},k∈\[K\]\.\\mathsf\{Block\}\_\{k\}:=\\\{\(k\-1\)L\+1,\\ldots,kL\\\},\\qquad k\\in\[K\]\.An MDP instance is parameterized by a hidden keyθ=\(θ1,…,θL\)∈\{0,1\}L\\theta=\(\\theta\_\{1\},\\ldots,\\theta\_\{L\}\)\\in\\\{0,1\\\}^\{L\}\. The policy class consists of open\-loop policies which repeat the same length\-LLaction sequence in every block\. Namely, for anyϑ∈\{0,1\}L\\vartheta\\in\\\{0,1\\\}^\{L\}, define the policyπϑ\\pi^\{\\vartheta\}as

πhϑ​\(x\)=ϑℓwhen​h=\(k−1\)​L\+ℓ,\\pi\_\{h\}^\{\\vartheta\}\(x\)=\\vartheta\_\{\\ell\}\\qquad\\text\{when \}h=\(k\-1\)L\+\\ell,and letΠ=\{πϑ:ϑ∈\{0,1\}L\}\\Pi=\\\{\\pi^\{\\vartheta\}:\\vartheta\\in\\\{0,1\\\}^\{L\}\\\}\. Thus,\|Π\|=2L=2H\\lvert\\Pi\\rvert=2^\{L\}=2^\{\\sqrt\{H\}\}\. We design the MDP instance so thatπ⋆=πθ\\pi^\{\\star\}=\\pi^\{\\theta\}\.

Every layer has four latent states: a real statesh𝖱s\_\{h\}^\{\\mathsf\{R\}\}, a decoy statesh𝖣s\_\{h\}^\{\\mathsf\{D\}\}, a one statesh1s\_\{h\}^\{1\}, and a zero statesh0s\_\{h\}^\{0\}\. The initial latent state iss1𝖱s\_\{1\}^\{\\mathsf\{R\}\}\. Forp∈\[0,1\]p\\in\[0,1\], define

𝖢𝗈𝗅𝗅𝖾𝖼𝗍h\+1​\(p\):=p​δsh\+11\+\(1−p\)​δsh\+10,pk:=4−k,k∈\[K\]\.\\mathsf\{Collect\}\_\{h\+1\}\(p\):=p\\delta\_\{s\_\{h\+1\}^\{1\}\}\+\(1\-p\)\\delta\_\{s\_\{h\+1\}^\{0\}\},\\qquad p\_\{k\}:=4^\{\-k\},\\quad k\\in\[K\]\.We now describe the dynamics\. Fixh=\(k−1\)​L\+ℓ∈\[H−1\]h=\(k\-1\)L\+\\ell\\in\[H\-1\]\.

- •The one and zero states progress to their respective next states under either action: P𝗅𝖺𝗍\(⋅∣sh1,a\)=δsh\+11,P𝗅𝖺𝗍\(⋅∣sh0,a\)=δsh\+10\.P\_\{\\mathsf\{lat\}\}\(\\cdot\\mid s\_\{h\}^\{1\},a\)=\\delta\_\{s\_\{h\+1\}^\{1\}\},\\qquad P\_\{\\mathsf\{lat\}\}\(\\cdot\\mid s\_\{h\}^\{0\},a\)=\\delta\_\{s\_\{h\+1\}^\{0\}\}\.
- •In every block, the real–zero pair forms a combination lock\. From a real state, the correct actionθℓ\\theta\_\{\\ell\}advances to the next real state, while a wrong action moves to the zero state\. At the end of a nonfinal blockkk, the correct action transitions to𝖢𝗈𝗅𝗅𝖾𝖼𝗍​\(pk\)\\mathsf\{Collect\}\(p\_\{k\}\)\. Thus, P𝗅𝖺𝗍\(⋅∣sh𝖱,a\)=\{δsh\+1𝖱a=θℓ,ℓ<L,𝖢𝗈𝗅𝗅𝖾𝖼𝗍h\+1​\(pk\)k<K,a=θL,ℓ=L,δsh\+10otherwise\.P\_\{\\mathsf\{lat\}\}\(\\cdot\\mid s\_\{h\}^\{\\mathsf\{R\}\},a\)=\\begin\{cases\}\\delta\_\{s\_\{h\+1\}^\{\\mathsf\{R\}\}\}&a=\\theta\_\{\\ell\},\\ \\ell<L,\\\\ \\mathsf\{Collect\}\_\{h\+1\}\(p\_\{k\}\)&k<K,\\ a=\\theta\_\{L\},\\ \\ell=L,\\\\ \\delta\_\{s\_\{h\+1\}^\{0\}\}&\\text\{otherwise\}\.\\end\{cases\}
- •The decoy states prevent the learner from discovering the key by working in the opposite direction\. In a nonfinal blockkk, a wrong action transitions to𝖢𝗈𝗅𝗅𝖾𝖼𝗍​\(pk\+1\)\\mathsf\{Collect\}\(p\_\{k\+1\}\)\. Correct actions advance along the decoy track, and completing the block moves to a real state at the start of blockk\+1k\+1\. In the final block, either action moves to the zero state\. Formally, P𝗅𝖺𝗍\(⋅∣sh𝖣,a\)=\{𝖢𝗈𝗅𝗅𝖾𝖼𝗍h\+1​\(pk\+1\)k<K,a≠θℓ,δsh\+1𝖣k<K,a=θℓ,ℓ<L,δsh\+1𝖱k<K,a=θL,ℓ=L,δsh\+10k=K\.P\_\{\\mathsf\{lat\}\}\(\\cdot\\mid s\_\{h\}^\{\\mathsf\{D\}\},a\)=\\begin\{cases\}\\mathsf\{Collect\}\_\{h\+1\}\(p\_\{k\+1\}\)&k<K,\\ a\\neq\\theta\_\{\\ell\},\\\\ \\delta\_\{s\_\{h\+1\}^\{\\mathsf\{D\}\}\}&k<K,\\ a=\\theta\_\{\\ell\},\\ \\ell<L,\\\\ \\delta\_\{s\_\{h\+1\}^\{\\mathsf\{R\}\}\}&k<K,\\ a=\\theta\_\{L\},\\ \\ell=L,\\\\ \\delta\_\{s\_\{h\+1\}^\{0\}\}&k=K\.\\end\{cases\}

All rewards before layerHHare zero\. At layerHH, the two nonzero reward distributions are

RH​\(s,a\)=\{1s=sH1,Ber​\(pK\)s=sH𝖱,a=θL\.R\_\{H\}\(s,a\)=\\begin\{cases\}1&s=s\_\{H\}^\{1\},\\\\ \\mathrm\{Ber\}\(p\_\{K\}\)&s=s\_\{H\}^\{\\mathsf\{R\}\},\\ a=\\theta\_\{L\}\.\\end\{cases\}Every other terminal state\-action pair receives reward zero\.

We realize these dynamics as a rich\-observation Block MDP using the same decoder and emission construction as in[Section2](https://arxiv.org/html/2608.07772#S2)\. Letm=2c​Hm=2^\{c\\sqrt\{H\}\}for a sufficiently large constantc\>0c\>0\. For eachh≥2h\\geq 2, let\|𝒳h\|=8​m\\lvert\\mathcal\{X\}\_\{h\}\\rvert=8m, and let the decoderϕ\\phipartition𝒳h\\mathcal\{X\}\_\{h\}into the preimages ofsh𝖱,sh𝖣,sh0,sh1s\_\{h\}^\{\\mathsf\{R\}\},s\_\{h\}^\{\\mathsf\{D\}\},s\_\{h\}^\{0\},s\_\{h\}^\{1\}with respective sizesm,4​m,2​m,mm,4m,2m,m\. A transition to a latent state emits uniformly from its preimage\. This defines the familyMθ,ϕM\_\{\\theta,\\phi\}, indexed by the hidden keyθ\\thetaand the decoderϕ\\phi\.

We takeμ1\\mu\_\{1\}to be the initial distribution andμh=Unif​\(𝒳h\)\\mu\_\{h\}=\\mathrm\{Unif\}\(\\mathcal\{X\}\_\{h\}\)for everyh≥2h\\geq 2\. IfX∼μhX\\sim\\mu\_\{h\}andS=ϕ​\(X\)S=\\phi\(X\), then

ℙ⁡\(S=sh𝖱\)=18,ℙ⁡\(S=sh𝖣\)=12,ℙ⁡\(S=sh0\)=14,ℙ⁡\(S=sh1\)=18\.\\operatorname\{\\mathbb\{P\}\}\(S=s\_\{h\}^\{\\mathsf\{R\}\}\)=\\frac\{1\}\{8\},\\qquad\\operatorname\{\\mathbb\{P\}\}\(S=s\_\{h\}^\{\\mathsf\{D\}\}\)=\\frac\{1\}\{2\},\\qquad\\operatorname\{\\mathbb\{P\}\}\(S=s\_\{h\}^\{0\}\)=\\frac\{1\}\{4\},\\qquad\\operatorname\{\\mathbb\{P\}\}\(S=s\_\{h\}^\{1\}\)=\\frac\{1\}\{8\}\.
![Refer to caption](https://arxiv.org/html/2608.07772v1/x2.png)Figure 2:Construction used for proof of Theorem[3](https://arxiv.org/html/2608.07772#Thmtheorem3)\.From this, it is immediate that every instance satisfies

C𝗉𝗎𝗌𝗁​\(μ;Mθ,ϕ\)≤8\.C\_\{\\mathsf\{push\}\}\(\\mu;M\_\{\\theta,\\phi\}\)\\leq 8\.Also,πθ\\pi^\{\\theta\}is optimal from every state\. At a real state, it plays the unique rewarding suffix\. At a decoy state in a nonfinal blockkk, it completes the current suffix and the next block, obtaining valuepk\+1p\_\{k\+1\}\. A deviation while the process remains on the decoy track immediately transitions to𝖢𝗈𝗅𝗅𝖾𝖼𝗍​\(pk\+1\)\\mathsf\{Collect\}\(p\_\{k\+1\}\), while completing the current block leads to a real state whose value is at mostpk\+1p\_\{k\+1\}\. In the final block, every policy has value zero from a decoy state, and actions do not affect the value from the one and zero states\. Consequently,

Vπθ=p1=14,Vπϑ=0for every​ϑ≠θ\.V^\{\\pi^\{\\theta\}\}=p\_\{1\}=\\frac\{1\}\{4\},\\qquad V^\{\\pi^\{\\vartheta\}\}=0\\quad\\text\{for every \}\\vartheta\\neq\\theta\.

### Why doesn’t reset access allow sample\-efficient learning of the optimal policy?

Fix an instanceMθ,ϕM\_\{\\theta,\\phi\}\. As in[Section2](https://arxiv.org/html/2608.07772#S2), the large random decoder ensures that transition observations leak essentially no information aboutθ\\theta, so the learner is forced to use reward observations\.

Similar to the lower bound in[Section2](https://arxiv.org/html/2608.07772#S2), online trajectories from the initial state distributionμ1\\mu\_\{1\}require2Ω​\(L\)2^\{\\Omega\(L\)\}samples to guess the keyθ\\theta\. We next explain why reset trajectories do not allow the learner to recover the key one bit at a time\.

Fix a reset layerh=\(k−1\)​L\+ℓ≥2h=\(k\-1\)L\+\\ell\\geq 2in a nonfinal blockk<Kk<Kand an action sequence through the end of blockk\+1k\+1\. Let

I\\displaystyle I=𝟙​\{ah:k​L=θℓ:L\},\\displaystyle=\\mathbbm\{1\}\\left\\\{a\_\{h:kL\}=\\theta\_\{\\ell:L\}\\right\\\},\(action matches the remaining suffix of𝖡𝗅𝗈𝖼𝗄k\),\\displaystyle\\text\{\(action matches the remaining suffix of $\\mathsf\{Block\}\_\{k\}$\)\},J\\displaystyle J=𝟙​\{ak​L\+1:\(k\+1\)​L=θ\},\\displaystyle=\\mathbbm\{1\}\\left\\\{a\_\{kL\+1:\(k\+1\)L\}=\\theta\\right\\\},\(action matchesθin𝖡𝗅𝗈𝖼𝗄k\+1\)\.\\displaystyle\\text\{\(action matches $\\theta$ in $\\mathsf\{Block\}\_\{k\+1\}$\)\}\.The rewards are either zero or one, so we compute the probability of the reward being 1:

ℙ⁡\(rH=1\)\\displaystyle\\operatorname\{\\mathbb\{P\}\}\\left\(r\_\{H\}=1\\right\)=18⏟from​sh1\+pk8​I⏟from​sh𝖱\+pk\+12​\(1−I\+I​J\)⏟from​sh𝖣\\displaystyle=\\underbrace\{\\frac\{1\}\{8\}\}\_\{\\text\{from \}s\_\{h\}^\{1\}\}\+\\underbrace\{\\frac\{p\_\{k\}\}\{8\}I\}\_\{\\text\{from \}s\_\{h\}^\{\\mathsf\{R\}\}\}\+\\underbrace\{\\frac\{p\_\{k\+1\}\}\{2\}\(1\-I\+IJ\)\}\_\{\\text\{from \}s\_\{h\}^\{\\mathsf\{D\}\}\}=18\+pk8​\(1\+I​J\),\\displaystyle=\\frac\{1\}\{8\}\+\\frac\{p\_\{k\}\}\{8\}\(1\+IJ\),since​pk\+1=14​pk\.\\displaystyle\\text\{since \}p\_\{k\+1\}=\\frac\{1\}\{4\}p\_\{k\}\.Therefore, every action sequence except the one matching the remaining suffix of𝖡𝗅𝗈𝖼𝗄k\\mathsf\{Block\}\_\{k\}and all of𝖡𝗅𝗈𝖼𝗄k\+1\\mathsf\{Block\}\_\{k\+1\}produces the same reward law\. This is the essential recursive poisoning property: pushforward coverage places reset mass on the next\-block real state, and the decoy at that block poisons the new signal again at a scale four times smaller\.

What about in the final block? A reset reaches the real state with probability1/81/8, so the gap between the correct and incorrect final actions ispK/8p\_\{K\}/8\. Thus, standard hypothesis testing bounds requireΩ​\(pK−2\)=2Ω​\(K\)\\Omega\(p\_\{K\}^\{\-2\}\)=2^\{\\Omega\(K\)\}samples to identifyθL\\theta\_\{L\}\.

Combining the two sources of information gives a2Ω​\(min⁡\{K,L\}\)2^\{\\Omega\(\\min\\\{K,L\\\}\)\}trajectory lower bound\. TakingK=L=HK=L=\\sqrt\{H\}yields the claimed2Ω​\(H\)2^\{\\Omega\(\\sqrt\{H\}\)\}lower bound\.

## References

- BKSN \[03\]J\. A\. Bagnell, S\. M\. Kakade, J\. G\. Schneider, and A\. Y\. Ng\.Policy search by dynamic programming\.In*Advances in Neural Information Processing Systems 16*, pages 831–838, 2003\.
- FKSX \[22\]D\. J\. Foster, A\. Krishnamurthy, D\. Simchi\-Levi, and Y\. Xu\.Offline reinforcement learning: Fundamental barriers for value function approximation\.In*Proceedings of the 35th Conference on Learning Theory*, volume 178 of*Proceedings of Machine Learning Research*, page 3489, 2022\.Full version: arXiv:2111\.10919\.
- JLR\+ \[23\]Z\. Jia, G\. Li, A\. Rakhlin, A\. Sekhari, and N\. Srebro\.When is agnostic reinforcement learning statistically tractable?In*Advances in Neural Information Processing Systems 36*, 2023\.
- JRSW \[24\]Z\. Jia, A\. Rakhlin, A\. Sekhari, and C\.\-Y\. Wei\.Offline reinforcement learning: Role of state aggregation and trajectory data\.In*Proceedings of the 37th Conference on Learning Theory*, volume 247 of*Proceedings of Machine Learning Research*, pages 2644–2719, 2024\.
- KL \[02\]S\. M\. Kakade and J\. Langford\.Approximately optimal approximate reinforcement learning\.In*Proceedings of the 19th International Conference on Machine Learning*, pages 267–274, 2002\.
- KLS \[25\]A\. Krishnamurthy, G\. Li, and A\. Sekhari\.The role of environment access in agnostic reinforcement learning\.In*Proceedings of the 38th Conference on Learning Theory*, volume 291 of*Proceedings of Machine Learning Research*, pages 3405–3406, 2025\.Full version: arXiv:2504\.05405\.
- SDM\+ \[21\]A\. Sekhari, C\. Dann, M\. Mohri, Y\. Mansour, and K\. Sridharan\.Agnostic reinforcement learning with low\-rank MDPs and rich observations\.In*Advances in Neural Information Processing Systems 34*, 2021\.
- XJ \[21\]T\. Xie and N\. Jiang\.Batch value\-function approximation with only realizability\.In*Proceedings of the 38th International Conference on Machine Learning*, volume 139 of*Proceedings of Machine Learning Research*, pages 11404–11413, 2021\.