Pith. sign in

REVIEW 4 major objections 5 minor 56 references

Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learning

T0 review · 4 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that a simple max-uncertainty sampling rule gives near-optimal sample complexity for kernel-based reward-free reinforcement learning.

desk verdict A genuinely useful independence-based confidence interval and a clean generative-model analysis, but the headline claim 'without restrictive assumptions' is undercut by Assumption 3, which fails for simple Matérn MDPs as stated. read the letter →

arxiv 2502.07715 v2 pith:HWVB5FCC submitted 2025-02-11 cs.LG

Aya Kayal , Sattar Vakili , Laura Toni , Alberto Bernacchia This is my paper · ORCID
classification cs.LG MSC 68Q3268T05
keywords reward-freereinforcementlearningkernelridgeregressionsamplecomplexityoptimisticclosurepolynomialeigendecaygenerativemodelonlineexplorationMercereigenvalues
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks how many samples are enough, when rewards are hidden, to later design a near-optimal policy in kernel-based reinforcement learning. It claims that a simple rule—query the state-action pair with largest kernel-ridge uncertainty—achieves near-optimal sample complexity for a broad class of kernels, including Matérn and neural tangent kernels, both with and without a generative model. The argument rests on new confidence intervals that exploit the statistical independence of the collected samples, avoiding the inflated bounds that biased adaptive sampling causes. If correct, it gives rates of order $\widetilde{O}((H^3/\epsilon)^{2+2/(p-1)})$ samples, and only $H$ times more episodes online, and it matches lower bounds in the degenerate bandit case.

What carries the argument

The load-bearing object is the confidence interval in Theorem 1 for kernel ridge regression on functions of the form $f(z) = \mathbb{E}_{s'\sim P(\cdot|z)}[V(s')]$, when $f$ and $V$ lie in two reproducing kernel Hilbert spaces and the query points are independent of the transition noise. The bound splits the Mercer expansion of $V$ into a low-rank part handled by standard confidence bounds and a tail part controlled by $\sqrt{n \sum_{m>M} \lambda_m}$, yielding $\beta(\delta)=O((H/\tau)\sqrt{d\log(NH/\delta)})$ under polynomial eigendecay. Feeding this $\beta$ into optimistic least-squares value iteration, with exploration rules that select maximum-uncertainty points so that each observation remains unbiased, reduces the suboptimality gap to the information-gain rate $\sqrt{\Gamma(N)/N}$, from which the sample complexities follow.

What would settle it

Take a two-state MDP with horizon $H$, a Matérn kernel, and transition probabilities satisfying Assumptions 1 and 2, run Algorithm 2, and compute the RKHS norm of the optimistic value functions it constructs. If for any $H$ the norm exceeds the fixed constant $c_v$ from Assumption 3, the inductive arguments in Theorems 2 and 3 fail; a concrete counterexample would determine whether optimistic closure is automatically inherited from the kernel's universal approximation property or must be imposed.

Watch

Extended reading notes

Core claim

On its own terms, the paper proves that under Assumptions 1, 2 and 3, the policy returned by the least-squares value iteration planning phase is $\epsilon$-optimal with probability at least $1-\delta$, whether the samples come from the generative-model explorer or the online explorer. For kernels whose Mercer eigenvalues decay as $\gamma_m = O(m^{-p})$, the generative explorer needs $N = \widetilde{O}((H^3/\epsilon)^{2+2/(p-1)})$ samples per step and the online explorer needs $NH$ episodes, the extra $H$ being the price of staying on the Markovian trajectory. The central quantitative claim is that this $1/\epsilon$-scaling is order optimal: for a Matérn kernel of smoothness $\nu$ in dimension $d$, the bound becomes $\widetilde{O}(H(H^3/\epsilon)^{2+d/\nu})$, which matches the known $\Omega((1/\epsilon)^{2+d/\nu})$ lower bound in the $H=1$ bandit case.

Load-bearing premise

Every optimistic value function the algorithm constructs during exploration and planning must stay inside a smooth function space with norm bounded by a fixed constant, no matter how the horizon grows.

Editorial extensions

If this is right

  • Kernels with polynomial eigendecay, such as Matérn and neural tangent kernels, now have finite non-vacuous reward-free sample guarantees, whereas earlier results only cover exponential eigendecay.
  • Dropping the generative-model requirement costs exactly a factor of $H$ in exploration episodes, so online reward-free exploration is not intrinsically harder than the generative-model version.
  • The new confidence interval can be reused wherever unbiased regression samples are available, including offline RL and infinite-horizon planning with a generative model.
  • The $1/\epsilon$ dependence is order optimal for Matérn kernels in the $H=1$ bandit limit, so further improvement would require exploiting horizon-dependent structure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The experiments show a greedy max-variance heuristic performing close to Algorithm 3; a formal guarantee for that heuristic would make deployment simpler, but it is not established here.
  • The optimistic-closure assumption is a condition on the algorithm's own iterates rather than on the true MDP, and the paper notes it can be relaxed to value functions $\epsilon$-away from the class at the price of an approximation error.
  • The appendix states that time and space complexity are not analyzed; the total cost of kernel-matrix inversion is quartic in $N$, so sparse approximations are a natural next step for large-scale use.
  • Because the speedup comes from unbiasedness, any exploration scheme that certifies unbiased samples—for example by resetting or by collecting one clean sample per episode—should inherit near-optimal rates.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies reward-free reinforcement learning with kernel-based function approximation. It proposes two exploration algorithms, one with a generative model (Algorithm 2) and one online (Algorithm 3), together with a planning algorithm (Algorithm 1), and it states a new confidence bound for kernel ridge regression with independent samples (Theorem 1 and Corollary 1). The main advertised results are sample complexity bounds under Assumptions 1-3: for kernels with polynomial eigendecay gamma_m = O(m^{-p}), it claims N = \tilde O((H^3/epsilon)^{2+2/(p-1)}) samples in the generative setting and N H = \tilde O(H (H^3/epsilon)^{2+2/(p-1)}) episodes online. The paper also reports simulations on squared-exponential and Mat\'ern kernels.

Significance. If the results held as stated, they would be a useful contribution: the algorithms are simple, they avoid the domain-partitioning machinery of Vakili et al. (2024), and the sample complexities would match the epsilon-dependence of known bandit lower bounds for Mat\'ern kernels. Theorem 1 is a potentially reusable confidence interval for kernel ridge regression under independent, unbiased samples, and the appendices contain detailed proofs and experimental code. However, the central claims are conditional on an unverified closure assumption, and the displayed theorem statements contain scaling errors that make them false as written. A revision that honestly restricts the claims to the closure assumption and corrects the technical statements could yield a valuable conditional contribution.

major comments (4)
  1. [Section 4.2, Assumption 3 and Eq. (16)]
  2. [Section 4.1, Corollary 1, and Appendix B, Lemma 3]
  3. [Section 4.2, Theorem 3, Eq. (17)]
  4. [Abstract and Section 4.2, Theorem 2]
minor comments (5)
  1. [Section 4.2, Eq. (16)]
  2. [Assumption 2]
  3. [Section 3.2.2]
  4. [Appendix B, Lemma 3]
  5. [Table 1]

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the sample-complexity theorems are conditional on explicit assumptions and do not reduce to fitted values or to load-bearing self-citations.

full rationale

The central derivation is Theorem 1 (confidence bounds) used through Corollary 1 to prove Theorems 2 and 3. Theorem 1 is a direct Mercer-decomposition bound on |f - hat_f_n|: the deterministic part is bounded by Lemma 1 (Proposition 1 of Vakili et al. 2021a), and the noise part by Hoeffding plus an eigendecay tail. Corollary 1 adds a standard discretization argument and Lemma 2 (Lemma 5 of Vakili and Olkhovskaya 2023) to bound the RKHS norm of the predictor. These two cited lemmas are co-authored prior-work results, but they are standard kernel ridge regression facts used as tools; they are not equivalent to the paper's reward-free RL sample-complexity claim, so this is not load-bearing circularity. Theorems 2 and 3 substitute Assumption 1 and Assumption 3 into Corollary 1 and then apply the standard elliptical-potential summation of Lemma 6 (Srinivas et al. 2010). Assumption 3 is explicitly stated as an assumption and attributed to Chowdhury and Oliveira 2023; the paper does not pretend to derive it. The skeptical objection that Assumption 3 can fail for Matérn or NT kernels attacks the truth of a premise, not the circularity of the derivation: if the premise fails, the theorems are inapplicable, but the proof is still conditional and non-circular. No fitted parameter is disguised as a prediction: experimental beta tuning appears only in Appendix E.3 and does not enter the theorem statements, whose beta expressions are derived from the confidence bounds. Thus the claimed results do not reduce by construction to their inputs, and the only mild issue is minor tool-level self-citation, giving a low score.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The sample-complexity theorems rely on Assumptions 1-3 and standard kernel spectral facts; no new physical or mathematical entities are introduced. The proof truncation level M in Theorem 1 is a proof device, not a fitted constant. In experiments, tau and beta are chosen by hand, with beta tuned to the best grid value; these do not enter the theoretical sample complexity as fitted quantities.

free parameters (2)
  • regularization parameter tau = 0.01 for SE kernel; 0.5 for Matérn kernels in experiments
    Kernel ridge regression regularization; chosen by hand for experiments and fixed in the theory. It affects the confidence width beta and all bounds, but is a standard hyperparameter, not fitted to the target result.
  • confidence multiplier beta = 0.1 in experiments (tuned over grid {0.1, 1, 10, 100})
    In the empirical section, beta is tuned per algorithm to the best value found on the grid. The theorems specify a theoretical beta, so the tuned value is an experimental hyperparameter rather than a fitted constant used in the derivations.
assumptions (5)
  • domain assumption Assumption 1: P_h(s | ·, ·) in H_k and ||P_h(s | ·, ·)||_{H_k} <= 1 for all s in S and h in [H].
    Realizability of transition densities in the RKHS; needed for the confidence interval and value-function bounds. Stated in Section 2.3.
  • domain assumption Assumption 2: For each n, a discretization Z of Z exists with f(z) - f([z]) <= 1/n for ||f|| <= B1 and |Z| <= c B1^d n^d.
    Used to extend pointwise confidence bounds to uniform bounds over continuous domains. Stated as mild and holding for typical kernels; Section 4.1.
  • ad hoc to paper Assumption 3 (Optimistic Closure): for every V in the class V defined in Eq. (16), ||V||_{H_{k_psi}} <= c_v.
    Ensures the algorithm's proxy value functions stay in the RKHS with bounded norm. Borrowed from Chowdhury and Oliveira (2023, Assumption 1); Theorems 2 and 3 fail without it.
  • standard math Mercer representation of the kernel and bounded eigenfunctions |psi_m| <= psi_max.
    Background for the spectral decomposition of V and for the new confidence interval; Appendix F.
  • domain assumption Polynomial eigendecay gamma_m = O(m^-p) with p > 1, and maximum information gain Gamma(n) = ~O(n^{1/p}).
    Defines the kernel class for the stated sample complexities; the information-gain rate is a standard result from Vakili et al. (2021b).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learning." pith.science (2026). https://pith.science/paper/HWVB5FCC

@misc{pith2026250207715,
  author       = {Pith},
  title        = {Pith review of: Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HWVB5FCC}},
  note         = {Machine review of arXiv:2502.07715}
}
read the original abstract

Reinforcement Learning (RL) problems are being considered under increasingly more complex structures. While tabular and linear models have been thoroughly explored, the analytical study of RL under nonlinear function approximation, especially kernel-based models, has recently gained traction for their strong representational capacity and theoretical tractability. In this context, we examine the question of statistical efficiency in kernel-based RL within the reward-free RL framework, specifically asking: how many samples are required to design a near-optimal policy? Existing work addresses this question under restrictive assumptions about the class of kernel functions. We first explore this question by assuming a generative model, then relax this assumption at the cost of increasing the sample complexity by a factor of H, the length of the episode. We tackle this fundamental problem using a broad class of kernels and a simpler algorithm compared to prior work. Our approach derives new confidence intervals for kernel ridge regression, specific to our RL setting, which may be of broader applicability. We further validate our theoretical findings through simulations.

Figures

Figures reproduced from arXiv: 2502.07715 by the authors.

Figure 1
Figure 1. Average suboptimality gap against N. The error bars indicate standard deviation. When specialized for the case of Mat´ern kernels with p = 1 + 2ν d , we obtain NH = O˜(H( H3 ϵ ) 2+ d ν ) that matches the lower bound for the degenerate case of bandits with H = 1 proven in Scarlett et al. (2017). Our sample complexity is thus order optimal in terms of ϵ dependency. We also recall that the existing results lead to poss… view at source ↗
Figure 2
Figure 2. Reward and transition probability functions generated by kernel ridge regression using SE Kernel with [PITH_FULL_IMAGE:figures/full_fig_p023_2.png] view at source ↗
Figure 3
Figure 3. Reward and transition probability functions generated by kernel ridge regression using Mat´ern kernel [PITH_FULL_IMAGE:figures/full_fig_p023_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Reward and transition probability functions generated by kernel ridge regression using Mat´ern kernel [PITH_FULL_IMAGE:figures/full_fig_p024_4.png]
Figure 5
Figure 5. Figure 5: Average suboptimality gap plotted against the number of episodes [PITH_FULL_IMAGE:figures/full_fig_p025_5.png]
Figure 7
Figure 7. Figure 7: Average suboptimality gap plotted against the number of episodes [PITH_FULL_IMAGE:figures/full_fig_p025_7.png]
Figure 6
Figure 6. Figure 6: Average suboptimality gap plotted against the number of episodes [PITH_FULL_IMAGE:figures/full_fig_p026_6.png]
Figure 8
Figure 8. Figure 8: Average suboptimality gap plotted against [PITH_FULL_IMAGE:figures/full_fig_p026_8.png]
Figure 9
Figure 9. Figure 9: Average suboptimality gap plotted against [PITH_FULL_IMAGE:figures/full_fig_p027_9.png]
Figure 10
Figure 10. Figure 10: Average suboptimality gap plotted against [PITH_FULL_IMAGE:figures/full_fig_p027_10.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

56 extracted references · 47 canonical work pages

  1. [1]

    Abbasi-Yadkori, Y. (2013). Online learning for linearly parametrized control problems

    work page 2013

  2. [2]

    Agarwal, A., Kakade, S., and Yang, L. F. (2020). Model-based reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory , pages 67--83. PMLR

    work page 2020

  3. [3]

    Antos, A., Szepesv \'a ri, C., and Munos, R. (2008). Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning , 71:89--129

    2008

  4. [4]

    Auer, P., Jaksch, T., and Ortner, R. (2008). Near-optimal regret bounds for reinforcement learning. Advances in Neural Information Processing Systems , 21

    work page 2008

  5. [5]

    G., Munos, R., and Kappen, H

    Azar, M. G., Munos, R., and Kappen, H. J. (2013). Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning , 91:325--349

    work page 2013

  6. [6]

    Bartlett, P. L. and Tewari, A. (2012). Regal: A regularization based algorithm for reinforcement learning in weakly communicating MDPs . arXiv preprint arXiv:1205.2661

    arXiv 2012

  7. [7]

    Bellemare, M., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., and Munos, R. (2016). Unifying count-based exploration and intrinsic motivation. Advances in Neural Information Processing Systems , 29

    2016

  8. [8]

    and Jiang, N

    Chen, J. and Jiang, N. (2019). Information-theoretic considerations in batch reinforcement learning. In International Conference on Machine Learning , pages 1042--1051. PMLR

    work page 2019

Show all 56 references
  1. [9]

    Chowdhury, S. R. and Gopalan, A. (2017). On kernelized multi-armed bandits. In International Conference on Machine Learning , pages 844--853. PMLR

    2017

  2. [10]

    Chowdhury, S. R. and Gopalan, A. (2019). Online learning in kernelized M arkov decision processes. In The 22nd International Conference on Artificial Intelligence and Statistics , pages 3197--3205. PMLR

    2019

  3. [11]

    Chowdhury, S. R. and Oliveira, R. (2023). Value function approximations via kernel embeddings for no-regret reinforcement learning. In Asian Conference on Machine Learning , pages 249--264. PMLR

    2023

  4. [12]

    and Steinwart, I

    Christmann, A. and Steinwart, I. (2008). Support Vector Machines . Springer New York, NY

    2008

  5. [13]

    D., M \'e nard, P., Pirotta, M., Kaufmann, E., and Valko, M

    Domingues, O. D., M \'e nard, P., Pirotta, M., Kaufmann, E., and Valko, M. (2021). Kernel-based reinforcement learning: A finite-time analysis. In International Conference on Machine Learning , pages 2783--2792. PMLR

    2021

  6. [14]

    Hazan, E., Kakade, S., Singh, K., and Van Soest, A. (2019). Provably efficient maximum entropy exploration. In International Conference on Machine Learning , pages 2681--2691. PMLR

    2019

  7. [15]

    Hu, P., Chen, Y., and Huang, L. (2022). Towards minimax optimal reward-free reinforcement learning in linear mdps. In The Eleventh International Conference on Learning Representations

    2022

  8. [16]

    Jacot, A., Gabriel, F., and Hongler, C. (2018). Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems , 31

    2018

  9. [17]

    Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018). Is Q -learning provably efficient? Advances in Neural Information Processing Systems , 31

    2018

  10. [18]

    Jin, C., Krishnamurthy, A., Simchowitz, M., and Yu, T. (2020a). Reward-free exploration for reinforcement learning. In International Conference on Machine Learning , pages 4870--4879. PMLR

    2020

  11. [19]

    Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020b). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory , pages 2137--2143. PMLR

    2020

  12. [20]

    Kakade, S. M. (2003). On the sample complexity of reinforcement learning . University of London, University College London (United Kingdom)

    2003

  13. [21]

    and Singh, S

    Kearns, M. and Singh, S. (1998a). Finite-sample convergence rates for q-learning and indirect algorithms. In Advances in Neural Information Processing Systems , volume 11. MIT Press

    1998

  14. [22]

    and Singh, S

    Kearns, M. and Singh, S. (1998b). Finite-sample convergence rates for Q -learning and indirect algorithms. Advances in Neural Information Processing Systems , 11

    1998

  15. [23]

    Lattimore, T. (2023). A lower bound for linear and kernel regression with adaptive covariates. In The Thirty Sixth Annual Conference on Learning Theory , pages 2095--2113. PMLR

    2023

  16. [24]

    and Oh, M.-h

    Lee, J. and Oh, M.-h. (2023). Demystifying linear mdps and novel dynamics aggregation framework. In The Twelfth International Conference on Learning Representations

    2023

  17. [25]

    Levine, S., Kumar, A., Tucker, G., and Fu, J. (2020). Offline reinforcement learning: Tutorial, review, and perspectives on open problems. ArXiv , abs/2005.01643

    2020 arXiv

  18. [26]

    Mercer, J. (1909). Functions of positive and negative type, and their connection with the theory of integral equations. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character , 209:415--446

    1909

  19. [27]

    and Szepesv \'a ri, C

    Munos, R. and Szepesv \'a ri, C. (2008). Finite-time bounds for fitted value iteration. Journal of Machine Learning Research , 9(5)

    2008

  20. [28]

    and Pike-Burke, C

    Neu, G. and Pike-Burke, C. (2020). A unifying view of optimism in episodic reinforcement learning. Advances in Neural Information Processing Systems , 33:1392--1403

    2020

  21. [29]

    A., and Darrell, T

    Pathak, D., Agrawal, P., Efros, A. A., and Darrell, T. (2017). Curiosity-driven exploration by self-supervised prediction. In International Conference on Machine Learning , pages 2778--2787. PMLR

    2017

  22. [30]

    Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. (2011). Scikit-learn: Machine learning in P ython. Jou...

    2011

  23. [31]

    Precup, D. (2000). Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series , page 80

    2000

  24. [32]

    Puterman, M. L. (2014). Markov decision processes: discrete stochastic dynamic programming . John Wiley & Sons

    2014

  25. [33]

    Qiu, S., Ye, J., Wang, Z., and Yang, Z. (2021). On reward-free rl with kernel and neural function approximations: Single-agent MDP and M arkov G ame. In International Conference on Machine Learning , pages 8737--8747. PMLR

    2021

  26. [34]

    Russo, D. (2019). Worst-case regret bounds for exploration via randomized value functions. Advances in Neural Information Processing Systems , 32

    2019

  27. [35]

    Scarlett, J., Bogunovic, I., and Cevher, V. (2017). Lower bounds on regret for noisy G aussian process bandit optimization. In Conference on Learning Theory , pages 1723--1742. PMLR

    2017

  28. [36]

    Sidford, A., Wang, M., Wu, X., Yang, L., and Ye, Y. (2018a). Near-optimal time and sample complexities for solving markov decision processes with a generative model. Advances in Neural Information Processing Systems , 31

    2018

  29. [37]

    Sidford, A., Wang, M., Wu, X., and Ye, Y. (2018b). Variance reduced value iteration and faster algorithms for solving markov decision processes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 770--787. SIAM

    2018

  30. [38]

    M., and Seeger, M

    Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. (2010). Gaussian process optimization in the bandit setting: No regret and experimental design. In International Conference on Machine Learning

    2010

  31. [39]

    Vakili, S. (2024). Open problem: Order optimal regret bounds for kernel-based reinforcement learning. In The Thirty Seventh Annual Conference on Learning Theory , pages 5340--5344. PMLR

    2024

  32. [40]

    Vakili, S., Bouziani, N., Jalali, S., Bernacchia, A., and Shiu, D.-s. (2021a). Optimal order simple regret for G aussian process bandits. Advances in Neural Information Processing Systems , 34:21202--21215

    2021

  33. [41]

    Vakili, S., Bromberg, M., Garcia, J., Shiu, D.-s., and Bernacchia, A. (2023). Information gain and uniform generalization bounds for neural kernel models. In 2023 IEEE International Symposium on Information Theory (ISIT) , pages 555--560. IEEE

    2023

  34. [42]

    Vakili, S., Khezeli, K., and Picheny, V. (2021b). On information gain and regret bounds in gaussian process bandits. In International Conference on Artificial Intelligence and Statistics , pages 82--90. PMLR

    2021

  35. [43]

    Vakili, S., Nabiei, F., Shiu, D.-s., and Bernacchia, A. (2024). Reward-free kernel-based reinforcement learning. In Forty-first International Conference on Machine Learning

    2024

  36. [44]

    and Olkhovskaya, J

    Vakili, S. and Olkhovskaya, J. (2023). Kernelized reinforcement learning with order optimal regret bounds. Advances in Neural Information Processing Systems , 36

    2023

  37. [45]

    Vakili, S., Scarlett, J., Shiu, D.-s., and Bernacchia, A. (2022). Improved convergence rates for sparse approximation methods in kernel-based learning. In International Conference on Machine Learning , pages 21960--21983. PMLR

    2022

  38. [46]

    J., Chen, Y., Simchowitz, M., Du, S., and Jamieson, K

    Wagenmaker, A. J., Chen, Y., Simchowitz, M., Du, S., and Jamieson, K. (2022). Reward-free rl is no harder than reward-aware rl in linear markov decision processes. In International Conference on Machine Learning , pages 22430--22456. PMLR

    2022

  39. [47]

    S., Yang, L., and Salakhutdinov, R

    Wang, R., Du, S. S., Yang, L., and Salakhutdinov, R. R. (2020). On reward-free reinforcement learning with linear function approximation. Advances in Neural Information Processing Systems , 33:17816--17826

    2020

  40. [48]

    S., and Krishnamurthy, A

    Wang, Y., Wang, R., Du, S. S., and Krishnamurthy, A. (2019). Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXiv:1912.04136

    2019 arXiv

  41. [49]

    Whitehouse, J., Ramdas, A., and Wu, S. Z. (2023). On the sublinear regret of GP-UCB . Advances in Neural Information Processing Systems , 36

    2023

  42. [50]

    Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. (2021). Bellman-consistent pessimism for offline reinforcement learning. Advances in Neural Information Processing Systems , 34:6683--6694

    2021

  43. [51]

    and Wang, M

    Yang, L. and Wang, M. (2019). Sample-optimal parametric q-learning using linearly additive features. In International conference on machine learning , pages 6995--7004. PMLR

    2019

  44. [52]

    and Wang, M

    Yang, L. and Wang, M. (2020). Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning , pages 10746--10756. PMLR

    2020

  45. [53]

    Yang, Z., Jin, C., Wang, Z., Wang, M., and Jordan, M. (2020). Provably efficient reinforcement learning with kernel and neural function approximations. Advances in Neural Information Processing Systems , 33:13903--13916

    2020

  46. [54]

    A., and Zhang, X

    Yao, H., Szepesv \'a ri, C., Pires, B. A., and Zhang, X. (2014). Pseudo- MDPs and factored linear action models. In 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL) , pages 1--9. IEEE

    2014

  47. [55]

    Yeh, S.-Y., Chang, F.-C., Yueh, C.-W., Wu, P.-Y., Bernacchia, A., and Vakili, S. (2023). Sample complexity of kernel-based q-learning. In International Conference on Artificial Intelligence and Statistics , pages 453--469. PMLR

    2023

  48. [56]

    Zanette, A., Brandfonbrener, D., Brunskill, E., Pirotta, M., and Lazaric, A. (2020). Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics , pages 1954--1964. PMLR

    2020

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.