REVIEW 3 major objections 4 minor 59 references
Hyper: Hyperparameter Robust Efficient Exploration in Reinforcement Learning
T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read This paper claims that splitting each episode into a repositioning phase and an exploration phase makes curiosity-driven reinforcement learning sample-efficient and largely insensitive to the curiosity coefficient.
desk verdict The empirical recipe is plausible and the warm-up analysis is nice, but the central 'any p' sample-complexity theorem has a dropped 1/p factor that breaks the stated guarantee. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the repositioning-and-exploration mechanism. In each episode a length $L_k$ is drawn from a bounded geometric distribution with parameter $p$; the first $L_k$ steps follow the exploitation policy, and the remaining $H - L_k$ steps follow the curiosity-driven exploration policy. In the provable version the exploration policy is built from an optimistic UCB value function and a pessimistic lower-bound value function on a linear MDP, whose transition and reward are linear in a known feature map $\phi$. The proof's sample-complexity bound follows because policy weights change only on episodes with $L_k = 0$, so the expected number of episodes between updates is $1/p$, which inflates the regret by at most $1/p$. In the practical version the same two-phase structure is used with neural-network value functions, a decay schedule for $p$, and per-step updates.
What would settle it
Run the neural Hyper algorithm exactly as in the paper but replace per-step updates with updates only on episodes with $L_k=0$ and freeze $p$; if final performance in a sparse-reward maze or locomotion task changes by more than run-to-run variance, the theorem's preconditions are doing real work. Conversely, a single environment with a narrow proper-$\beta$ window where Hyper still collapses for large $\beta$ would refute the robustness claim.
Extended reading notes
Core claim
The central discovery claimed is that a repositioning-and-exploration cycle decouples task learning from curiosity exploration: before exploring, the agent follows its current exploitation policy for a geometrically distributed number of steps, then switches to the exploration policy for the rest of the episode. This makes the exploration policy start from states that the exploitation policy judges promising, so the exploration bonus cannot dominate the task reward even when $\beta$ is large. The theoretical version maintains optimistic and pessimistic Q-functions with UCB-style bonuses, and it updates its weights only on episodes whose repositioning length is zero. Theorem B.1 states that with any fixed truncation probability $p \in (0,1)$, this Linear-UCB-Hyper finds an $\epsilon$-optimal exploitation policy in $\widetilde{O}(d^3 H^4/\epsilon^2)$ steps with high probability. The paper reads this as showing that Hyper is simultaneously sample-efficient and robust to the curiosity coefficient, the two properties that usually trade against each other.
Load-bearing premise
The proof needs the geometric repositioning length to be drawn with a fixed probability $p$ and the value-function weights to be updated only on episodes that skip repositioning entirely, whereas the version tested in the experiments decays $p$ and updates after every step; if that mismatch is not repaired, the stated sample complexity does not cover the algorithm that produced the reported results.
Editorial extensions
If this is right
- If Theorem B.1 is right, curiosity-driven exploration can be made robust to $\beta$ without sacrificing sample efficiency, so practitioners can set $\beta$ large to encourage exploration and rely on the repositioning phase to keep exploitation stable.
- The decoupling claim implies that exploitation learning can be trained without intrinsic rewards while still using exploration data, as long as repositioning aligns the two data distributions, which directly addresses the distribution-shift failure of simple decoupled agents.
- Because the mechanism does not require resettable environments, it transfers the idea of returning to promising states, previously only practical when episodes can be reset, to general non-resettable reinforcement learning settings.
- The theorem gives an explicit polynomial sample bound of $\widetilde{O}(d^3 H^4/\epsilon^2)$ for linear MDPs, so the method is certified to be sample-efficient in the worst case, not merely empirically.
- The bounded geometric distribution prevents probability mass from piling up at the full horizon, keeping the repositioning phase useful in environments with short episodes.
Reading between the lines
- The proof and the evaluated algorithm are not the same object: Theorem B.1 requires a fixed $p$ and updates only on episodes with $L_k=0$, while the practical algorithm decays $p$ and updates every step. If that gap is not closed, the sample-complexity guarantee should be attributed to a restricted variant, and the robustness evidence for the practical method remains empirical.
- A natural testable extension is to run the neural version exactly as described in the paper but freeze $p$ and update only after full-exploration episodes; if performance barely changes, the mismatch is benign, and if it collapses, the theorem's precondition is genuinely load-bearing.
- The bounded geometric distribution is behaving like a temporally extended option that moves the agent to a promising region before exploring, so one could connect Hyper to option-based exploration and ask whether learning the switch policy, rather than fixing $p$, improves robustness further.
- The theory's dependence on $\beta$ is hidden in constants: the bonus scale enters only as a logarithmic factor in the confidence bound, so the robustness claim is asymptotic, while the practical gain is that large $\beta$ no longer destabilizes training, which the proof does not quantify.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes Hyper, a two-policy exploration algorithm that interleaves a repositioning phase, driven by an exploitation policy, with a curiosity-driven exploration phase, with the goal of making curiosity-based RL robust to the intrinsic-reward coefficient beta. The theoretical section claims a provably efficient version, Linear-UCB-Hyper, with sample complexity O~(d^3 H^4 / epsilon^2) for any truncation probability p in (0,1) under linear MDP assumptions, and the empirical section evaluates the practical version (Algorithm 2), with TD3 and Disagreement, on navigation and locomotion tasks, reporting better beta-robustness than baselines.
Significance. If the theorem were correct, the paper would make a valuable contribution by combining decoupled exploitation/exploration with a provable sample-efficiency guarantee that is robust to the key hyperparameter p, and the empirical robustness analysis would be a useful practical addition. The paper also contains a clear exposition of the beta-sensitivity problem and a reasonable experimental design with multiple environments and baselines. However, the theoretical guarantee is the paper's central advertised contribution, and the supplied proof has a load-bearing gap in the treatment of the truncation probability p. The empirical results are suggestive but do not compensate for this, because the evaluated Algorithm 2 differs from the provable Algorithm 1 in update cadence and p schedule. The paper is not in a publishable state as it stands.
major comments (3)
- [Appendix B, Theorem B.14 (last display)] The proof drops the 1/p factor introduced at Eq. (33). After bounding the sum over fully-exploratory episodes by C' * sqrt(d^3 H^3 T iota^2), the paper concludes total regret <= (C'/p) * sqrt(d^3 H^3 T iota^2) = O~(sqrt(d^3 H^3 T iota^2)). This equality is false as an asymptotic statement for arbitrary p in (0,1): p is an algorithm hyperparameter, not a fixed constant, and carrying 1/p through the regret-to-PAC conversion gives O~(d^3 H^4 / (p^2 epsilon^2)) total steps, which can be arbitrarily worse as p -> 0. Theorem B.1's p-independent claim therefore does not follow from the supplied proof.
- [Appendix B, Lemmas B.8-B.9 and Theorem B.14] The symbol p is used simultaneously as the geometric truncation probability and as the confidence parameter: Lemma B.8 states P(E) >= 1 - p/2 with p the truncation probability, while Theorem B.14 concludes 'with probability at least 1 - delta' and defines beta using log(2dT/delta). The proof never relates the geometric p to the confidence delta, so the high-probability statement of Theorem B.1 is not well-formed for arbitrary p. The two roles of p must be separated before the theorem can be evaluated.
- [Section 4 and Algorithm 2] The paper claims that Algorithm 1 and Algorithm 2 'differ only in function approximation,' but they also differ in a way that matters for the proof: the theoretical analysis (Eq. (32)-(33)) requires policy weights to be updated only on episodes with L_k = 0 and uses a fixed geometric p, whereas Algorithm 2 updates the policies at every environment step and linearly decays p (lines 14-20). The theorem therefore does not cover the algorithm that is actually evaluated in the experiments, so the empirical results cannot be interpreted as validating the theoretical efficiency claim.
minor comments (4)
- [Section 4, Theorem 4.2] The informal theorem in the main text is too vague: it states only 'polynomially' and omits the dependence on p, which is the central quantity in question. The formal statement should appear in the main text or be referenced with its exact p-dependence.
- [Algorithm 1, line 25] The assignment for the pessimistic weight uses 'checkQ*_{h+1}' which appears to be a typo; it should be the maximum over actions of the pessimistic Q function, matching Algorithm 3.
- [Appendix B, Lemma B.6 proof] The proof refers to 'Lemma B.1' when bounding the elliptic potential; the referenced lemma does not exist in the appendix. The citation should be to Lemma C.1 or C.2.
- [Appendix B, Eq. (47)] The derivation from H beta iota sqrt(2 d K p) to the final C' sqrt(d^3 H^3 T iota^2) involves an unchecked exponent in H: with T = K H, the displayed expression should be checked carefully, since the powers of H appear inconsistent across the displayed inequalities.
Circularity Check
No material circularity: Hyper's proof adapts standard LSVI-UCB analysis and its empirical claims are benchmark comparisons, not derivations from the method's own outputs.
full rationale
The paper's central theoretical claim (Theorem B.1 / Theorem B.14) is derived by adapting the standard LSVI-UCB machinery of Jin et al. (2020), with realizability, optimism, pessimism, covering-number, and self-normalized concentration lemmas stated and proved in the appendix. The linear MDP assumption is attributed to [22,17], one of which is the authors' own prior work, but this is a standard definition used as a premise rather than a conclusion smuggled in; it does not encode Hyper's efficiency or robustness. No fitted parameter is renamed as a prediction: the theoretical constants β, β′, and λ are chosen by closed-form expressions before the bound, and the empirical β-sensitivity curves are measurements against TD3, Curiosity, and Decouple baselines, not outputs of Hyper's own analysis. The paper even concedes that traditional curiosity algorithms achieve the same worst-case bound, so the theoretical contribution is not inflated into a circular prediction. The flagged 1/p issue in the proof (Equations 31-33 versus the final Theorem B.14 statement) is a quantitative correctness/mismatch concern rather than a circular one: the proof does not assume the conclusion it is trying to establish, it simply appears to drop a factor when converting regret to PAC sample complexity. Similarly, the mismatch between provable Algorithm 1 and empirical Algorithm 2 is an assumption-fidelity issue, not circularity. Overall, the derivation chain is self-contained and externally benchmarked, so no circular step is exhibited.
Assumptions & free parameters
free parameters (4)
- truncation probability p =
fixed p in theory, decayed from 0.01 to 0.001 in locomotion experiments
- intrinsic reward coefficient beta =
1.0 in experiments; c*d*H*sqrt(log(2dT/delta)) in theory
- pessimistic bonus coefficient beta_prime =
c_prime*d*H*sqrt(log(2dT/delta)) in theory
- regularization lambda =
1
assumptions (4)
- domain assumption Linear MDP realizability (Assumption B.2): transitions and rewards are linear in a known feature map phi, with bounded weights.
- domain assumption Fixed geometric restart structure with update only on full exploratory episodes.
- standard math Standard concentration and covering-number lemmas from Jin et al. 2020 and Abbasi-Yadkori et al. 2011.
- ad hoc to paper Bounded geometric sampling of repositioning length.
Cite this review
Pith. "Pith review of Hyper: Hyperparameter Robust Efficient Exploration in Reinforcement Learning." pith.science (2026). https://pith.science/paper/ES5ETX4W
@misc{pith2026241203767,
author = {Pith},
title = {Pith review of: Hyper: Hyperparameter Robust Efficient Exploration in Reinforcement Learning},
year = {2026},
howpublished = {\url{https://pith.science/paper/ES5ETX4W}},
note = {Machine review of arXiv:2412.03767}
}
read the original abstract
The exploration \& exploitation dilemma poses significant challenges in reinforcement learning (RL). Recently, curiosity-based exploration methods achieved great success in tackling hard-exploration problems. However, they necessitate extensive hyperparameter tuning on different environments, which heavily limits the applicability and accessibility of this line of methods. In this paper, we characterize this problem via analysis of the agent behavior, concluding the fundamental difficulty of choosing a proper hyperparameter. We then identify the difficulty and the instability of the optimization when the agent learns with curiosity. We propose our method, hyperparameter robust exploration (\textbf{Hyper}), which extensively mitigates the problem by effectively regularizing the visitation of the exploration and decoupling the exploitation to ensure stable training. We theoretically justify that \textbf{Hyper} is provably efficient under function approximation setting and empirically demonstrate its appealing performance and robustness in various environments.
Figures
Figures from the paper (6 more)
Reference graph
Works this paper leans on
-
[1]
Playing atari with deep reinforcement learning
V olodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013
arXiv 2013
-
[2]
Human-level control through deep reinforcement learning
V olodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529–533, 2015
2015
-
[3]
Mastering the game of go with deep neural networks and tree search
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484–489, 2016
2016
-
[4]
Mastering the game of go without human knowledge
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354–359, 2017
2017
-
[5]
Dota 2 with large scale deep reinforcement learning
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemysław D˛ ebiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv:1912.06680, 2019
arXiv 1912
-
[6]
Alphastar: An evolutionary computation perspective
Kai Arulkumaran, Antoine Cully, and Julian Togelius. Alphastar: An evolutionary computation perspective. In Proceedings of the genetic and evolutionary computation conference companion, pages 314–315, 2019
work page 2019
-
[7]
Unifying count-based exploration and intrinsic motivation
Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. Advances in neural information processing systems, 29, 2016
2016
-
[8]
Curiosity-driven exploration by self- supervised prediction
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self- supervised prediction. In International conference on machine learning, pages 2778–2787. PMLR, 2017. 10 PRIME AI paper
work page 2017
Show all 59 references
-
[9]
Count-based exploration with neural density models
Georg Ostrovski, Marc G Bellemare, Aäron Oord, and Rémi Munos. Count-based exploration with neural density models. In International conference on machine learning, pages 2721–2730. PMLR, 2017
2017
-
[10]
Exploration by random network distillation
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint arXiv:1810.12894, 2018
2018 arXiv
-
[11]
Count-based exploration with the successor representation
Marlos C Machado, Marc G Bellemare, and Michael Bowling. Count-based exploration with the successor representation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5125–5133, 2020
2020
-
[12]
Self-supervised exploration via disagreement
Deepak Pathak, Dhiraj Gandhi, and Abhinav Gupta. Self-supervised exploration via disagreement. InInternational conference on machine learning, pages 5062–5071. PMLR, 2019
2019
-
[13]
Using confidence bounds for exploitation-exploration trade-offs
Peter Auer. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3(Nov):397–422, 2002
2002
-
[14]
Minimax regret bounds for reinforcement learning
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263–272. PMLR, 2017
2017
-
[15]
Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018
2018
-
[16]
Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746–10756. PMLR, 2020
2020
-
[17]
Provably efficient reinforcement learning with linear function approximation
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137–2143. PMLR, 2020
2020
-
[18]
Decoupling exploration and exploitation in reinforcement learning
Lukas Schäfer, Filippos Christianos, Josiah Hanna, and Stefano V Albrecht. Decoupling exploration and exploitation in reinforcement learning. In ICML 2021 Workshop on Unsupervised Reinforcement Learning, 2021
2021
-
[19]
Decoupled exploration and exploitation policies for sample-efficient reinforcement learning
William F Whitney, Michael Bloesch, Jost Tobias Springenberg, Abbas Abdolmaleki, Kyunghyun Cho, and Martin Riedmiller. Decoupled exploration and exploitation policies for sample-efficient reinforcement learning. arXiv preprint arXiv:2101.09458, 2021
2021 arXiv
-
[20]
A markovian decision process
Richard Bellman. A markovian decision process. Journal of mathematics and mechanics, pages 679–684, 1957
1957
-
[21]
Q-learning
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8:279–292, 1992
1992
-
[22]
Sample-optimal parametric q-learning using linearly additive features
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In Interna- tional Conference on Machine Learning, pages 6995–7004. PMLR, 2019
2019
-
[23]
Addressing function approximation error in actor-critic methods
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In International conference on machine learning, pages 1587–1596. PMLR, 2018
2018
-
[24]
D4rl: Datasets for deep data-driven reinforcement learning
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.07219, 2020
2004 arXiv
-
[25]
Mujoco: A physics engine for model-based control
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, pages 5026–5033. IEEE, 2012
2012
-
[26]
On the likelihood that one unknown probability exceeds another in view of the evidence of two samples
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285–294, 1933
1933
-
[27]
Intrinsic motivation systems for autonomous mental development
Pierre-Yves Oudeyer, Frdric Kaplan, and Verena V Hafner. Intrinsic motivation systems for autonomous mental development. IEEE transactions on evolutionary computation, 11(2):265–286, 2007
2007
-
[28]
# exploration: A study of count-based exploration for deep reinforcement learning
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAI Xi Chen, Yan Duan, John Schulman, Filip DeTurck, and Pieter Abbeel. # exploration: A study of count-based exploration for deep reinforcement learning. Advances in neural information processing systems, 30, 2017
2017
-
[29]
Dora the explorer: Directed outreaching reinforcement action-selection
Leshem Choshen, Lior Fox, and Yonatan Loewenstein. Dora the explorer: Directed outreaching reinforcement action-selection. arXiv preprint arXiv:1804.04012, 2018
2018 arXiv
-
[30]
Go-explore: a new approach for hard-exploration problems
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: a new approach for hard-exploration problems. arXiv preprint arXiv:1901.10995, 2019
1901 arXiv
-
[31]
Bayesian reinforcement learning: A survey
Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, Aviv Tamar, et al. Bayesian reinforcement learning: A survey. Foundations and Trends® in Machine Learning, 8(5-6):359–483, 2015
2015
-
[32]
Noisy networks for exploration
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, et al. Noisy networks for exploration. arXiv preprint arXiv:1706.10295, 2017. 11 PRIME AI paper
2017 arXiv
-
[33]
Deep exploration via bootstrapped dqn
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29, 2016
2016
-
[34]
Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181–211, 1999
1999
-
[35]
The option-critic architecture
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017
2017
-
[36]
Temporally-extended {\epsilon}-greedy exploration
Will Dabney, Georg Ostrovski, and André Barreto. Temporally-extended {\epsilon}-greedy exploration. arXiv preprint arXiv:2006.01782, 2020
2006 arXiv
-
[37]
Redeeming intrinsic rewards via constrained optimization
Eric Chen, Zhang-Wei Hong, Joni Pajarinen, and Pulkit Agrawal. Redeeming intrinsic rewards via constrained optimization. Advances in Neural Information Processing Systems, 35:4996–5008, 2022
2022
-
[38]
Lesson: learning to integrate exploration strategies for reinforcement learning via an option framework
Woojun Kim, Jeonghye Kim, and Youngchul Sung. Lesson: learning to integrate exploration strategies for reinforcement learning via an option framework. arXiv preprint arXiv:2310.03342, 2023
2023 arXiv
-
[39]
Decoupling exploration and exploitation for meta- reinforcement learning without sacrifices
Evan Z Liu, Aditi Raghunathan, Percy Liang, and Chelsea Finn. Decoupling exploration and exploitation for meta- reinforcement learning without sacrifices. In International conference on machine learning, pages 6925–6935. PMLR, 2021
2021
-
[40]
Improved algorithms for linear stochastic bandits
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011. 12 PRIME AI paper A Implementation & Experiment Details A.1 Implementation of Agents We implement Hyper, Decou...
2011
-
[41]
healthy reward
intrinsic reward model for every environmental step using 25% of data of each batch to prevent the intrinsic reward from shrinking too fast following [10]. In the locomotion experiments, we set the truncation probability p to be 0.01 initially, and decay to 0.001, as we discus...
-
[42]
− V πk 1 (sk 1) i , is at most ˜O √ d3H 3T , where p is the parameter of geometric distribution. Proof. For simplicity, we use the notation: ˆπk h(s, ·) = arg max a∈A ˆQk h(s, ·) πk h(s, ·) = arg max a∈A Qk h(s, ·) 22 PRIME AI paper We also denote I = {k ∈ [K], Lk = 0}, an ind...
-
[43]
− V πk 1 (sk 1) # ≤ E " KX k=1 ˆV k 1 (sk
-
[44]
− ˇV k 1 (sk 1) # (31) = E " KX k=1 ˆV ⌊k⌋ 1 (sk
-
[45]
− ˇV ⌊k⌋ 1 (sk 1) # (32) = 1 p · X k∈I ˆV k 1 (sk
-
[46]
And further, X k∈I ˆV k 1 (sk
(33) where the first step is the direct result of Lemmas B.12 and B.13, the second and the third steps are due to the construction of our algorithm, where we do not update weights until a full exploratory episode happens, and the expected interval of such event happening is 1 ...
-
[47]
= X k∈I ˆQk 1(sk 1, ak
-
[48]
− ˇQk 1(sk 1, a′k 1 ) (34) ≤ X k∈I ˆQk 1(sk 1, ak
-
[49]
(35) = X k∈I n ∆k h(sk 1, ak
-
[50]
− ˇV k 2 (sk 2)|sk 1, ak 1 io (36) ≤ X k∈I β q ϕ(sk 1, ak 1)⊤ Λk h −1 ϕ(sk 1, ak
-
[51]
+ β′ q ϕ(sk 1, ak 1)⊤ Λk h −1 ϕ(sk 1, ak 1) + E h ˆV k 2 (sk
-
[52]
− ˇV k 2 (sk 2)|sk 1, ak 1 io (37) = X k∈I β q ϕ(sk 1, ak 1)⊤ Λk h −1 ϕ(sk 1, ak 1) | {z } bk 1 + β′ q ϕ(sk 1, ak 1)⊤ Λk h −1 ϕ(sk 1, ak 1) | {z } b′k 1 (38) + E h ˆV k 2 (sk
-
[53]
− ˇV k 2 (sk 2)|sk 1, ak 1 i − ( ˆV k 2 (sk
-
[54]
− ˇV k 2 (sk 2)) | {z } ζk 2 +( ˆV k 2 (sk
-
[55]
− ˇV k 2 (sk 2)) (39) = X k∈I h ˆV k 2 (sk
-
[56]
By recursively applying Equation
+ bk 1 + b′k 1 + ζ k 2 i (40) where, a ∈ arg maxa∈A ˆQk 1(sk 1, ·) and a′ ∈ arg maxa′∈A ˇQk 1(sk 1, ·). By recursively applying Equation. (34), we have, X k∈I ˆV k 1 (sk
-
[57]
≤ X k∈I HX h=1 bk h + X k∈I HX h=1 b′k h + X k∈I HX h=1 ζ k h (41) (42) We now bound each terms, for the first term in Equation (41), by Lemma C.2 and C.3: 23 PRIME AI paper X k∈I HX h=1 bk h = X k∈I HX h=1 β q ϕ(sk h, ak h)⊤ Λk h −1 ϕ(sk h, ak h) (43) ≤ HX h=1 p Kp · "X k∈I β...
-
[58]
Hence, the total regret is given by: KX k=1 ˆV k 1 (sk
≤ Hβι p Kp + Hβ ′ι p Kp + 2H √ KHι = C ′ · √ d3H 3T ι2 for some absolute constant C ′. Hence, the total regret is given by: KX k=1 ˆV k 1 (sk
-
[59]
And equivalently, we conclude that our algorithm obtains ϵ-optimal policy with ˜O( d3H 4 ϵ2 ) samples with probability at least 1 − δ
≤ C ′ p · √ d3H 3T ι2 = ˜O( √ d3H 3T ι2) This concludes that the total pseudo regret of policy π over K episode is given by ˜O( √ d3H 3T ι2). And equivalently, we conclude that our algorithm obtains ϵ-optimal policy with ˜O( d3H 4 ϵ2 ) samples with probability at least 1 − δ. ...
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.