<p>We analyze the oracle complexity of the stochastic Halpern iteration with minibatch, where we aim to approximate fixed-points of nonexpansive and contractive operators in a normed finite-dimensional space. We show that if the underlying stochastic oracle has uniformly bounded variance, our method exhibits an overall oracle complexity of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\tilde{O}(\varepsilon ^{-5})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mi>O</mi> <mo stretchy="false">~</mo> </mover> <mrow> <mo stretchy="false">(</mo> <msup> <mi>ε</mi> <mrow> <mo>-</mo> <mn>5</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, to obtain <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\varepsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation> expected fixed-point residual for nonexpansive operators, improving recent rates established for the stochastic Krasnoselskii-Mann iteration. Also, we establish a lower bound of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\Omega (\varepsilon ^{-3})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <msup> <mi>ε</mi> <mrow> <mo>-</mo> <mn>3</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> which applies to a wide range of algorithms, including all averaged iterations even with minibatching. Using a suitable modification of our approach, we derive a <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O(\varepsilon ^{-2}(1-\gamma )^{-3})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>ε</mi> <mrow> <mo>-</mo> <mn>2</mn> </mrow> </msup> <msup> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>-</mo> <mi>γ</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mo>-</mo> <mn>3</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> complexity bound in the case in which the operator is a <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi>γ</mi> </math></EquationSource> </InlineEquation>-contraction to obtain an approximation of the fixed-point. As an application, we propose new model-free algorithms for average and discounted reward MDPs. For the average reward case, our method applies to weakly communicating MDPs and can be implemented without requiring prior parameter knowledge.</p>

Stochastic Halpern iteration in normed spaces and applications to reinforcement learning

期刊论文
发表日期：

2026年3月16日

查看全文

Mario Bravo,
Juan Pablo Contreras

摘要

We analyze the oracle complexity of the stochastic Halpern iteration with minibatch, where we aim to approximate fixed-points of nonexpansive and contractive operators in a normed finite-dimensional space. We show that if the underlying stochastic oracle has uniformly bounded variance, our method exhibits an overall oracle complexity of $\tilde{O}(\varepsilon ^{-5})$ $\tilde{O} (ε^{- 5})$ , to obtain $\varepsilon $ $ε$ expected fixed-point residual for nonexpansive operators, improving recent rates established for the stochastic Krasnoselskii-Mann iteration. Also, we establish a lower bound of $\Omega (\varepsilon ^{-3})$ $Ω (ε^{- 3})$ which applies to a wide range of algorithms, including all averaged iterations even with minibatching. Using a suitable modification of our approach, we derive a $O(\varepsilon ^{-2}(1-\gamma )^{-3})$ $O (ε^{- 2} {(1 - γ)}^{- 3})$ complexity bound in the case in which the operator is a $\gamma $ $γ$ -contraction to obtain an approximation of the fixed-point. As an application, we propose new model-free algorithms for average and discounted reward MDPs. For the average reward case, our method applies to weakly communicating MDPs and can be implemented without requiring prior parameter knowledge.