Fast Convergence of Policy Regret in
Learning Stochastic Optimal Control
May 25, 2026
Policy learning in modern operations environments faces a fundamental tension between limited operational data and the large, often continuous, state and action spaces over which good decisions must be identified and deployed. We study value-based policy learning in stochastic optimal control: a greedy policy induced by an estimate of the optimal action-value function \(Q^*\) is deployed, and its performance is measured by regret. The empirical success of this approach calls for statistical insight into the structures that enable fast regret convergence. We show that, in continuous action spaces, fast policy learning is induced by three geometric structures: a growth exponent \(p\), which quantifies how quickly \(Q^*\) separates suboptimal actions from its maximizers; a margin-mass exponent \(m\), which controls how much deployment mass lies on states with weak growth; and an action-wise regularity exponent \(q\), which measures the smoothness of the \(Q^*\)-estimation error across actions. Given a \(n^{-1/2}\)-accurate estimator of \(Q^*\), we show that the minimax-optimal policy regret convergence rate is \[\widetilde{\Theta}\!\left( n^{-\min\left\{\frac{p}{2(p-q)},\,\frac{m+1}{2m}\right\}} \right),\] up to a logarithmic factor at the boundary between the two regimes. The exponent \(q\) is crucial: \(q>0\) yields faster-than-\(n^{-1/2}\) regret. This regime is natural in operations applications. In particular, we verify \(q>0\) under mild regularity conditions in dynamic inventory control and service allocation examples, while the mechanism underlying this fast rate regime extends beyond these settings.
Stochastic control is a central language for sequential and dynamic decision-making in operations research (OR). It formalizes how controlled dynamical systems evolve over time and provides principled guidance on how a decision maker should act when inventories evolve, queues build up, demand fluctuates, or workloads move through a network. Classical stochastic control models typically take the transition dynamics, reward function, and exogenous noise distribution as known primitives, and then focus on solving the induced dynamic program [1]. Modern operations applications are different. Model parameters, transition distributions, and sometimes even rewards or utilities must be inferred from operational data before a policy can be computed. Therefore, it becomes increasingly important to consider stochastic optimal control through a statistical lens. This perspective is now central in many modern OR applications. Dynamic pricing systems learn demand response before setting prices, inventory systems use historical demand and covariates to prescribe replenishment decisions, and service and resource allocation systems estimate uncertain network conditions before deploying routing, matching, or allocation policies [2], [3].
In these operations settings, the object ultimately inferred and deployed is a policy, and the relevant performance metric is therefore its value or regret; i.e., the performance loss of the learned policy relative to the optimal dynamic decision rule. At the same time, forecasts, parameter estimates, value estimates, and learned reward models are intermediate objects: their utility is ultimately judged by the decisions they support.
This distinction becomes particularly important in continuous state and action spaces. Many OR decisions are either inherently continuous or naturally benefit from continuous embeddings: prices, order quantities, staffing levels, production rates, allocations, and related operational decisions live more naturally in real vector spaces than as discrete labels. Such embeddings are not merely a modeling convenience. They can reveal smoothness and local structure that are invisible in worst-case discrete formulations [4], and therefore create additional statistical leverage for policy learning. At the same time, continuous spaces make learning more delicate. The target policy is an infinite-dimensional object, while the available operational data may be very limited. These features make the way in which data are converted into a policy central to data-driven stochastic optimal control.
There are two main principles for learning good policies from data. A policy-based approach parameterizes and optimizes a policy directly, while a value-based approach estimates a surrogate value function and acts greedily. This paper studies the second route in a Markov decision process environment. We consider an estimator \(\widehat Q_n\) of the optimal action-value function \(Q^*\) and deploy the greedy policy \(\hat{\pi}_n(x) \in \arg\max_{a\in \mathbb{A}} \widehat Q_n(x,a)\), where \(x\in\mathbb{X}\) and \(a\in\mathbb{A}\) represent the state and the action. This principle underlies fitted value and \(Q\) iteration, projected dynamic programming, and many reinforcement learning (RL) methods [5]–[9]. It has strong empirical appeal: value-based and actor-critic methods often produce effective deployed policies even when global value-function estimates or Bellman errors remain far from negligible [10]. This empirical phenomenon raises a basic statistical question: Why can a greedy policy perform well before the \(Q\)-function is accurately estimated?
An important insight is that a \(Q\)-function is used comparatively. A good greedy policy does not require the learned \(Q\)-function to be uniformly accurate; it requires the estimate to preserve the relevant action comparisons in the regions that matter for deployment. Estimation errors have a limited impact on performance when they still preserve nearby comparisons, occur away from good actions, or happen at states with little deployment visitation mass. Thus, the statistical difficulty of value-based policy learning is governed by how the \(Q^*\) estimation error interacts with the local geometry of the action maximization problem.
For finite action spaces, this insight has a clean form. [11] observed that an action gap can make a greedy policy more stable: if the best action is separated from the second-best action, then moderate value-estimation errors need not change the selected action. Building on this idea, [12] developed fast policy-regret guarantees for offline RL and showed that policy regret can converge faster than the global \(Q\)-estimation error when the decision problem has favorable noise or margin structure. These results explain an important part of the empirical success of value-based learning. But they also reveal a limitation of the finite-action theory. In a continuous action space, an action gap is almost always absent. Indeed, if \(a\rightarrow Q^*(x,a)\) is continuous, then actions arbitrarily close to an optimizer have values arbitrarily close to optimal, hence no positive optimality gap. Therefore, a theory for the continuous action case needs a different notion of decision stability.
This paper develops such a theory. In continuous action spaces, the analogue of a finite action gap is not a discrete separation between two actions, but the local growth of the \(Q\)-surface near its maximizers. This growth matters in two ways: it determines how estimation error moves the greedy action, and it determines how costly the resulting action error is in value. We capture this local decision geometry through an action-growth condition.
Since we study value-based learning, the structure of the \(Q\)-estimation error is also important. A uniform bound on \(\widehat Q_n-Q^*\) controls the maximum error gap, but greedy action selection depends more critically on how smoothly this error varies across actions. If the centered error is smooth in the action variable, then nearby actions receive similar perturbations, making the argmax more stable. This motivates an action-wise regularity condition on the estimation error, which we show is satisfied in many important OR models.
Finally, these considerations need not hold uniformly over all states. Policy regret is averaged over the states relevant for deployment, so states with weak local growth matter only to the extent that they carry mass under this distribution. The margin-mass condition controls the prevalence of such difficult states. It is the continuous-action analogue of the margin conditions in classification and finite-action policy learning [12]–[14], but the margin now concerns the action value growth rather than a strict action gap.
The paper gives a minimax-optimal theory of the interaction between estimation error and continuous decision geometry. At a high level, the rate is determined by three quantities. The growth exponent \(p\) quantifies how quickly the true \(Q\)-function depreciates actions when moving away from the optimal action set. The action-wise regularity exponent \(q\) describes the smoothness of the estimation error over actions. The margin exponent \(m\) limits the probability mass of states where this local growth is weak. When the \(Q\) estimator has the canonical \(n^{-1/2}\) convergence rate, we prove matching upper and lower bounds for the policy regret rate as \[\widetilde{\Theta}\left( n^{-\min\left\{{\frac{p}{2(p-q)},\frac{m+1}{2m}}\right\}} \right).\] Here \(\widetilde{\Theta}\) suggests minimax optimality up to logarithmic factors; the logarithmic factor appears only in the boundary case \(\frac{p}{2(p-q)} = \frac{m+1}{2m}.\) The first exponent corresponds to the growth-limited regime, while the second corresponds to the margin-mass-limited regime.
Crucially, when \(q>0\) (with \(q < p <\infty\) and \(m<\infty\) typically holding automatically), the rate is always faster than the canonical \(n^{-1/2}\). This explains how fast convergence in optimal policy learning can arise in structured OR settings. In particular, our theory applies naturally to data-driven control problems where the system dynamics are known or accessible, but the driving noise distribution must be learned from data, such as demand uncertainty in inventory and pricing, travel-time uncertainty in logistics, and service-time variability in queueing and resource allocation. Through the dynamic inventory control and service allocation examples in Section 5.3, we show that OR models with max-plus-linear dynamics often admit faster policy learning rates.
In addition to guaranteeing fast rates for OR settings, the optimal rate quantitatively shows how local action growth, together with smooth-in-action \(Q\)-estimation error, can turn a moderately accurate value estimate into a substantially more accurate greedy policy. This points to a new perspective: the design and analysis of value-based policy learning should focus on the interaction among the data-generating process, the regularity of the \(Q\) estimator, and the local geometry of the decision problem.
Finally, we remark that although the paper is framed in discounted stochastic optimal control, both the upper and lower bounds cover contextual stochastic optimization [15]–[17] as a special case (with one stage). Indeed, by letting the system transition immediately to an absorbing state, the optimal value function reduces to the contextual objective \(V^*(x) := \max_{a\in\mathbb{A}} \mathbb{E}[r(x,a,W)]\), where \(r\) is the reward, \(a\in\mathbb{A}\) represents the decision vector, and \(x\in\mathbb{X}\) is the context/covariate. Then, the greedy policy against the plug-in estimate of \(\mathbb{E}[r(x,a,W)]\) becomes the usual sample-average-approximation estimator. Thus, the same growth, action-wise regularity, and margin-mass structure characterizes when continuous-action contextual decisions can achieve fast policy-regret rates.
Dynamic programming and Markov decision processes are foundational models for sequential decision-making under uncertainty [1], [18]. The data-driven OR literature shifts the emphasis from solving a fully specified model to learning decisions from finite operational data. This perspective appears across dynamic pricing with demand learning [2], data-driven inventory [3], renewable-energy operations [19], ride-sharing assignment [20], and dynamic treatment regimes [21]. Classical sample-average approximation provides a principled statistical route for stochastic optimization [22], [23], while model-free methods such as \(Q\)-learning and policy gradient provide complementary approaches when model primitives are unavailable or difficult to estimate [24]–[27]. Closely related one-stage formulations appear in prescriptive analytics and contextual stochastic optimization, where covariates are used to prescribe decisions rather than only predict uncertainty [3], [16], [28]. Predict-then-optimize and decision-focused learning make the same distinction explicit: prediction accuracy and decision quality need not coincide [29], [30]. Our work studies the dynamic value-based analogue, where the central object is the regret of the deployed greedy policy rather than the estimation loss for the learned value function.
Value-based methods underlie fitted value and \(Q\) iterations, and offline RL [5], [7]–[9]. The pioneering work of [11] explains the fast convergence of value-based methods through the action-gap between optimal and suboptimal actions. Related gap-weighted ideas also appear in classification-based approximate policy iteration [31]. Most directly, [12] develops a finite-action fast-rate theory for offline reinforcement learning, showing that policy regret can converge faster than the canonical \(n^{-1/2}\) rate. Related ideas appear in treatment assignment, policy learning, and contextual bandit [17], [32]–[34]. Our work identifies the continuous-action analogue of this action-gap phenomenon, which is inherently tied to discrete action settings.
Fast statistical rates often arise when the induced decision loss is smoother than the estimation error. This idea goes back at least to the margin analysis of [13], and was further developed through low-noise, margin, and calibration conditions in [14] and [35]. The present paper develops the analogous theory for greedy policies in continuous-action stochastic optimal control and contextual stochastic optimization.
We consider an infinite-horizon discounted stochastic optimal control problem. The state space \(\mathbb{X}\subset\mathbb{R}^{d_\mathbb{X}}\), action space \(\mathbb{A}\subset\mathbb{R}^{d_\mathbb{A}}\), and noise space \(\mathbb{W}\subset\mathbb{R}^{d_\mathbb{W}}\) are endowed with their Borel \(\sigma\)-fields \(\mathcal{X}\), \(\mathcal{A}\), and \(\mathcal{W}\), respectively. We assume that \(\mathbb{A}\) is compact and convex. Let \(\mathbb{Z}:=\mathbb{X}\times\mathbb{A}\), equipped with the product \(\sigma\)-field \(\mathcal{X}\times\mathcal{A}\). Throughout the paper, \(\left|\cdot\right|\) denotes the Euclidean norm on arbitrary-dimensional real spaces, and \(\left\|\cdot\right\|\) denotes the sup norm.
We consider a controlled stochastic system driven by a measurable state transition function \(f:\mathbb{X}\times\mathbb{A}\times\mathbb{W}\rightarrow\mathbb{X}\). The stochasticity of the system is defined on the canonical space \((\mathbb{X}\times\mathbb{W}^\mathbb{N},\mathcal{X}\times\mathcal{W}^\mathbb{N})\), supporting random variables \(\left\{{X_0,W_1,W_2,\dots}\right\}\) such that \(X_0(\omega)=x_0\) and \(W_n(\omega)=w_n\) for \(\omega=(x_0,w_1,w_2,\dots)\in\mathbb{X}\times\mathbb{W}^\mathbb{N}\). Here, \(X_0\) is the initial state and \(\left\{{W_n:n\geq 1}\right\}\) is the driving noise sequence. For an initial distribution \(\mu\in\mathcal{P}(\mathcal{X})\) and a common noise law \(\psi\in\mathcal{P}(\mathcal{W})\), we consider the probability measure \(\mathbb{P}_\mu=\mu\times\psi^\mathbb{N}\) on \((\mathbb{X}\times\mathbb{W}^\mathbb{N},\mathcal{X}\times\mathcal{W}^\mathbb{N})\), where the dependence on \(\psi\) is suppressed for notational convenience.
Let \(\Pi_{\mathrm{HD}}\) denote the class of admissible deterministic history-dependent policies; that is, each \(\pi\in\Pi_{\mathrm{HD}}\) is a sequence of measurable functions \(\pi=\left\{{\pi_t:t\geq 0}\right\}\) with \(\pi_t:\mathbb{X}^{t+1}\to\mathbb{A}\). Let \(\Pi_{\mathrm{SD}}\subset\Pi_{\mathrm{HD}}\) denote the class of measurable stationary deterministic policies. We identify each \(\pi\in\Pi_{\mathrm{SD}}\) with a measurable map \(\pi:\mathbb{X}\to\mathbb{A}\).
For fixed \(\pi\in\Pi_{\mathrm{HD}}\), we write \(X_0^\pi := X_0\) for notation convenience and recursively define the processes \[A_t^\pi:=\pi_t(X^\pi_t,X^\pi_{t-1},\dots,X_0^\pi), \quad\text{and}\quad X^\pi_{t+1}:=f(X^\pi_t,A_t^\pi,W_{t+1})\] for all \(t\geq 0\). We refer to the pair \(\left\{{(X^\pi_t,A_t^\pi):t\geq 0}\right\}\) as the controlled Markov chain under policy \(\pi\). In this setting, it is convenient to define the controlled transition kernel as the pushforward measure \[\label{eqn:def95P95from95f} P(B\mid z):=\psi\left( \left\{{w\in\mathbb{W}:\;f(z,w)\in B}\right\} \right),\tag{1}\] for all \(B\in\mathcal{X}\) and \(z\in\mathbb{Z}\). Thus, under \(\mathbb{E}_\mu\), the law of \(\left\{{X^\pi_t:t\geq 0}\right\}\) coincides with that of a stochastic process with initial distribution \(\mu\) and transition distribution \(P(\cdot| x_t,\pi_t(x_t,\dots,x_0))\).
Let \(r:\mathbb{X}\times\mathbb{A}\times\mathbb{W}\to\mathbb{R}\) be a measurable reward function. Throughout the paper, we assume that \(r(z,\cdot)\) is \(\psi\)-integrable and define \[\bar r(z):=\int_\mathbb{W}r(z,w)\psi(dw).\] We then define the control performance metric as the expected infinite-horizon discounted reward \[\label{eqn:def95Vpi} V^\pi(\mu):= \mathbb{E}_\mu\left[ \sum_{t=0}^\infty \gamma^t r(X^\pi_t,A_t^\pi,W_{t+1}) \right].\tag{2}\] When \(\mu=\delta_x\) is a point mass at \(x\in\mathbb{X}\), we write \(\mathbb{E}_{\delta_x}=\mathbb{E}_x\) and, by abuse of notation, write \(V^\pi(\delta_x)=V^\pi(x)\). Define the optimal control value function \[V^*(x):=\sup_{\pi\in\Pi_{\mathrm{HD}}}V^\pi(x)\] for all \(x\in\mathbb{X}\).
Definition 1 (Policy regret). For \(\pi\in\Pi_{\mathrm{SD}}\), define the regret from \(\mu\) by \[\mathrm{Regret}(\pi;\mu):=V^*(\mu)-V^\pi(\mu).\]
The regret \(\mathrm{Regret}(\pi;\mu)\) therefore measures the loss in discounted reward incurred by using the stationary policy \(\pi\), relative to the optimal value attainable starting from the initial distribution \(\mu\).
When \(V^*\) is measurable, we define the action-value function by \[\label{eqn:def95Qstar} Q^*(z):= \bar r(z)+\gamma\int_{\mathbb{X}}V^*(x') P(dx'|z), \qquad z=(x,a)\in\mathbb{Z}.\tag{3}\]
In this paper, we consider a policy learning strategy based on a sequence of estimators \(\{\widehat Q_n:n\geq 1\}\) that approximate \(Q^*\) as \(n\rightarrow\infty\). We then take the greedy policy \(\hat{\pi}_n\) with respect to \(\widehat Q_n\) as our policy, and show that the regret can converge faster than the canonical rates under additional regularity conditions. We further prove matching lower bounds, certifying the optimality of our results.
Throughout, \(\{\widehat Q_n:n\geq 1\}\) and \(\{\hat{\pi}_n:n\geq 1\}\) are estimators defined on an underlying probability space \((\Omega,\mathcal{F},P)\), which is distinct from the canonical space introduced above. We assume that \(\mathcal{F}\) contains all \(P\)-null sets. We note that the index \(n\) may, but need not, represent the number of samples used to construct the estimator \(\widehat Q_n\). A rigorous abstraction is defined and analyzed in Section 4.
To ensure that the stochastic control problem is well-behaved and the optimal policy learning problem is well-posed, we first impose the following measurability requirement. To streamline the main results, we state this requirement as an abstract assumption; sufficient conditions on the model primitives \((f,r,\psi)\) are established in Section 5.
Assumption 1 (Measurability and optimality). Assume that \(\bar r:\mathbb{Z}\to\mathbb{R}\), \(V^*:\mathbb{X}\to\mathbb{R}\), and \(Q^*:\mathbb{Z}\to\mathbb{R}\) are bounded and measurable. For each \(x\in\mathbb{X}\), the mapping \(a\rightarrow Q^*(x,a)\) is continuous on \(\mathbb{A}\), and for all \(x\in\mathbb{X}\), \[\label{eqn:Vstar95max95Qstar} V^*(x)=\max_{a\in\mathbb{A}}Q^*(x,a).\tag{4}\]
For each \(n\ge 1\) and \(P\)-a.e.\(\omega\in\Omega\), the map \(\widehat Q_n(\omega,\cdot):\mathbb{Z}\to\mathbb{R}\) is \((\mathcal{X}\times\mathcal{A})\)-measurable and, for each \(x\in\mathbb{X}\), the mapping \(a\rightarrow\widehat Q_n(\omega,x,a)\) is continuous on \(\mathbb{A}\).
Remark 1. Since \(\mathcal{F}\) contains all \(P\)-null sets, by modifying \(\widehat Q_n\) on a null set if necessary, we may and do assume throughout that the properties in Assumption 1 hold for every \(\omega\in\Omega\).
We first observe that, by the integrability of \(r(z,\cdot)\), the boundedness of \(\bar r\), and the independence of \(W_{t+1}\) from \((X^\pi_t,A_t^\pi)\) under \(\mathbb{E}_\mu\), \[\mathbb{E}_\mu\left[ \sum_{t=0}^\infty \gamma^t \bar r(X^\pi_t,A_t^\pi) \right] = \sum_{t=0}^\infty \gamma^t\mathbb{E}_\mu\left[ r(X^\pi_t,A_t^\pi,W_{t+1}) \right] = V^\pi(\mu).\] Thus, we may treat \(\bar r\) as the effective reward function.
On the other hand, by Assumption 1 and compactness of \(\mathbb{A}\), the set \[\label{eqn:def95Astar} \mathbb{A}^*(x):=\left\{{a\in\mathbb{A}:\;Q^*(x,a)=V^*(x)}\right\}\tag{5}\] is nonempty and closed, hence compact, for every \(x\in\mathbb{X}\). By the measurable maximum theorem, there exists a measurable selector \(\pi^*\in\Pi_{\mathrm{SD}}\) such that \(\pi^*(x)\in\mathbb{A}^*(x)\) and \(V^*(x)=Q^*(x,\pi^*(x))\) for all \(x\in\mathbb{X}\). Moreover, the correspondence \(x\to \mathbb{A}^*(x)\) is measurable.
Similarly, as clarified in Remark 1, for each \(\omega\in\Omega\), we can always choose \(\hat{\pi}_n(\omega,\cdot):\mathbb{X}\to\mathbb{A}\) as a measurable selector satisfying \[\label{eqn:def95hat95pi} \hat{\pi}_n(\omega,x)\in \underset{a\in\mathbb{A}}{\operatorname{arg} \operatorname{max}}\;\widehat Q_n(\omega,x,a)\tag{6}\] for all \(x\in\mathbb{X}\). Thus, the existence of measurable \(\hat{\pi}_n(\omega,\cdot)\) on \(\Omega\) follows from the same measurable maximum theorem on this full-probability set in Assumption 1.
We suppress the dependence of \(\widehat Q_n\) and \(\hat{\pi}_n\) on \(\omega\) in the notation. Observe that, for now, we do not assume joint measurability of \((\omega,z)\to \widehat Q_n(\omega,z)\) or \((\omega,x)\to \hat{\pi}_n(\omega,x)\).
Next, we impose conditions on the statistical error of \(\widehat Q_n\) that are tailored to our analysis of policy regret convergence rates. To handle measurability issues, we work with error envelopes. Specifically, the envelope \(\delta_n\) controls the uniform estimation error of \(\widehat Q_n\), while \(\Lambda_n(q)\) controls the \(q\)-Hölder modulus, in the action variable, of the centered error \(\widehat Q_n-Q^*\). This latter action-wise regularity is one of the main ingredients in our analysis: the greedy maximizer can be more stable when the estimation error varies smoothly across nearby actions.
Assumption 2 (Estimation error moments bounds). There exists \(q\in[0,1]\) and measurable random variables \(\left\{{\delta_n,\Lambda_n(q)>0:n\geq 1}\right\}\) such that for each \(n\ge 1\) \[\sup_{z\in\mathbb{Z}}\left|\widehat Q_n(z)-Q^*(z)\right|\le \delta_n,\] and \[\sup_{x\in\mathbb{X}}\sup_{a\ne b} \frac{\left|\left( \widehat Q_n(x,a)-Q^*(x,a) \right)-\left( \widehat Q_n(x,b)-Q^*(x,b) \right)\right|}{\left|a-b\right|^q} \le \Lambda_n(q)\] a.s.\(P\). Moreover, there exists a constant \(C_\delta<\infty\) and, for each integer \(k\ge 2\), a constant \(C_{\Lambda,k}<\infty\) such that for all \(n\ge 1\), \[E\left[ \delta_n^2 \right]\le \frac{C_\delta}{n}, \qquad E\left[ \Lambda_n(q)^k \right]\le \frac{C_{\Lambda,k}}{n^{k/2}}.\]
Remark 2. We note that the requirement \(\delta_n,\Lambda_n(q)>0\) is only for the convenience of future discussions, where we do not need to deal with \(0\cdot +\infty\). In particular, if one finds \(\delta_n',\Lambda_n'(q)\ge 0\) satisfying the rest of the requirements in Assumption 2, then \(\delta_n=\delta_n'+n^{-17}\) and \(\Lambda_n(q)=\Lambda_n'(q)+n^{-17}\) satisfy Assumption 2.
As in Remark 1, since \(\mathcal{F}\) contains all \(P\)-null sets, after modifying \(\delta_n\) and \(\Lambda_n(q)\) on a null set if necessary, we assume that the a.s. bounds in Assumption 2 hold for every \(\omega\in\Omega\). This convention is used throughout.
Assumption 2 is result-driven: the regret analysis below depends only on the envelopes \(\delta_n,\Lambda_n(q)\) and their moment bounds. In Section 5, we consider a data-driven stochastic optimal control setting and show that, under verifiable regularity conditions on the model primitives that usually hold in OR settings, Assumption 2 is satisfied.
The regret \(\mathrm{Regret}(\pi;\mu)\) is a trajectory-level quantity, while the greedy policy \(\hat{\pi}_n\) is defined via maximization of \(\widehat Q_n(x,\cdot)\). To connect these two objects, we use a performance-difference identity that expresses policy regret as an occupancy-weighted Bellman suboptimality gap. We begin by defining the discounted occupancy measure.
Definition 2 (Discounted occupancy measure).
For a stationary deterministic policy \(\pi\in\Pi_{\mathrm{SD}}\) and the fixed initial distribution \(\mu\), define the discounted state occupancy measure \[\nu_\mu^\pi(B):=(1-\gamma)\sum_{t=0}^\infty \gamma^t \mathbb{P}_\mu(X^\pi_t\in B), \qquad B\in\mathcal{X}.\]
The performance-difference identity below will integrate the state-wise loss \(V^*(x)-Q^*(x,\pi(x))\) against \(\nu_\mu^\pi\). Since this measure depends on the policy, we impose a common domination condition that allows all such integrals to be compared to integration with respect to a fixed reference measure \(\lambda_\mu\).
Assumption 3 (Concentrability relative to \(\mu\)). There exist a reference probability measure \(\lambda_\mu\) on \(\mathbb{X}\) and a constant \(C_{\mathrm{conc}}<\infty\) such that for every stationary deterministic policy \(\pi\in\Pi_{\mathrm{SD}}\), \[\nu_\mu^\pi \ll \lambda_\mu \qquad\text{and}\qquad \mathop{\mathrm{ess sup}}_{\lambda_\mu}\frac{d\nu_\mu^\pi}{d\lambda_\mu}\le C_{\mathrm{conc}}.\]
Intuitively, this condition holds when the discounted occupancy measures induced by stationary policies admit densities that are uniformly bounded with respect to a common reference measure. It is mild in many standard settings; for example, it is usually satisfied when \(\nu_\mu^\pi\) does not concentrate at different points as \(\pi\) varies.
Next, we present a performance-difference identity in the present setting.
Proposition 1 (Performance-difference identity). For every \(\pi\in\Pi_{\mathrm{SD}}\), \[\mathrm{Regret}(\pi;\mu) = \frac{1}{1-\gamma}\int_{\mathbb{X}}\left( V^*(x)-Q^*(x,\pi(x)) \right) \nu_\mu^\pi(dx).\] Under Assumption 3, this implies \[\label{eqn:pdl-bound} \mathrm{Regret}(\pi;\mu) \le \frac{C_{\mathrm{conc}}}{1-\gamma}\int_{\mathbb{X}}\left( V^*(x)-Q^*(x,\pi(x)) \right) \lambda_\mu(dx).\qquad{(1)}\]
Since 6 holds for every \(\omega\in\Omega\), ?? applies to the greedy policy \(\hat{\pi}_n\) everywhere.
Proof of Proposition 1. Consider the natural filtration \(\mathcal{F}_t:=\sigma(X^\pi_0,\ldots,X^\pi_t)\). By the definition 3 , \[Q^*(x,\pi(x)) = \bar r(x,\pi(x))+\gamma\int_{\mathbb{X}}V^*(x') P(dx'|x,\pi(x)),\] and therefore \[Q^*(X^\pi_t,\pi(X^\pi_t)) = \bar r(X^\pi_t,\pi(X^\pi_t)) + \gamma \mathbb{E}_\mu\left[ V^*(X^\pi_{t+1})\middle|\mathcal{F}_t \right] \qquad\text{a.s.}\] Hence, with \(\ell^\pi(x):=V^*(x)-Q^*(x,\pi(x))\), \[\ell^\pi(X^\pi_t) = V^*(X^\pi_t)-\bar r(X^\pi_t,\pi(X^\pi_t)) -\gamma \mathbb{E}_\mu\left[ V^*(X^\pi_{t+1})\middle|\mathcal{F}_t \right] \qquad\text{a.s.}\] Taking expectations, multiplying by \(\gamma^t\), and summing from \(t=0\) to \(T\) yield \[\sum_{t=0}^T\gamma^t\mathbb{E}_\mu\left[ \ell^\pi(X^\pi_t) \right] = V^*(\mu)-\mathbb{E}_\mu\left[ \sum_{t=0}^T\gamma^t \bar r(X^\pi_t,\pi(X^\pi_t)) \right]-\gamma^{T+1}\mathbb{E}_\mu\left[ V^*(X^\pi_{T+1}) \right].\] By Assumption 1, \(V^*\) is bounded, so the last term vanishes as \(T\to\infty\). Letting \(T\to\infty\) gives \[V^*(\mu)-V^\pi(\mu)=\sum_{t=0}^\infty \gamma^t \mathbb{E}_\mu\left[ \ell^\pi(X^\pi_t) \right].\] Using the definition of \(\nu_\mu^\pi\), \[(1-\gamma)\sum_{t=0}^\infty \gamma^t \mathbb{E}_\mu\left[ \ell^\pi(X^\pi_t) \right] = \int_{\mathbb{X}}\ell^\pi(x) \nu_\mu^\pi(dx),\] which proves the identity.
By 4 , \[\ell^\pi(x)=V^*(x)-Q^*(x,\pi(x))\ge 0\] for all \(x\in\mathbb{X}\). Therefore Assumption 3 yields \[\int_{\mathbb{X}}\ell^\pi d\nu_\mu^\pi \le C_{\mathrm{conc}}\int_{\mathbb{X}}\ell^\pi d\lambda_\mu,\] which proves ?? . ◻
In continuous action spaces with continuous \(a\to Q^*(x,a)\), action gaps typically vanish even when the maximizer is unique. Thus, the approach used in the finite-action setting cannot work directly. Instead, the growth of \(Q^*(x,\cdot)\) away from the optimal action set, together with the \(\lambda_\mu\)-mass of states having small growth, will determine the effect of estimation error.
Assumption 4 (\(p\)-growth and margin-mass). There exist \(p>0\), \(m>0\), a measurable function \(g_p:\mathbb{X}\to[0,\infty)\), and a constant \(M<\infty\) such that for all \(x\in\mathbb{X}\) and \(a\in\mathbb{A}\), \[\label{eqn:Q95err95pgrowth95in95action} V^*(x)-Q^*(x,a)\ge g_p(x) \mathop{\mathrm{dist}}(a,\mathbb{A}^*(x))^p,\tag{7}\] and for all \(t\ge 0\), \[\label{eqn:margin95mass} \lambda_\mu(\left\{{x\in\mathbb{X}:\;g_p(x)\le t}\right\})\le M t^{1/m}.\tag{8}\]
Remark 3. The exponent \(m\) quantifies how much mass of states have a small growth coefficient (small \(g_p(x)\)). This is the continuous-action analogue of margin conditions in the discrete-action setting. Note that 8 evaluated at \(t=0\) implies \(\lambda_\mu(\{x:\;g_p(x)=0\})=0\), so \(g_p\) may vanish but only on a \(\lambda_\mu\)-null set.
It is convenient to separate the case when \(g_p\) is uniformly bounded away from \(0\). In particular, if there exists \(g_\wedge>0\) such that \(g_p(x)\ge g_\wedge\) for \(\lambda_\mu\)-a.e.\(x\), then the analysis can be treated as a “uniform margin” regime (cf.Theorem 1).
Assumption 4 can be viewed as a continuous-action analogue of the margin-mass condition in classification [13]. In the binary classification setting, the difficult region is the neighborhood of the decision boundary, where two labels are nearly tied. In our continuous-action setting, the analogous difficulty is not an action-tie, but the set of states where the action-value surface is too flat near \(\mathbb{A}^*\), making it statistically difficult to distinguish optimal actions from near-optimal ones. This idea is quantified by the two-layer structure of Assumption 4.
\(p\)-growth: For a fixed \(x\in\mathbb{X}\), if an action is at distance \(d\) from the optimal action set, then the value gap measured by \(Q^*\) is at least of order \(g_p(x)d^p\). Thus, \(p\) captures the local growth near \(\mathbb{A}^*\) of the action-value maximization problem, while \(g_p(x)\) is a state-dependent curvature coefficient. Allowing \(g_p(x)\) to be small or 0 captures states at which this growth is weak and hence optimal decision-making is hard.
Margin mass: This condition controls the \(\lambda_\mu\)-mass where \(g_p(x)\) is small. It is analogous to the Tsybakov margin condition in classification: faster rates are achieved when only a small amount of mass lies near the difficult region [13].
We now combine the preceding ingredients to obtain upper bounds on the policy regret of the greedy policy \(\hat{\pi}_n\). Because joint measurability of \((\omega,x)\rightarrow\hat{\pi}_n(\omega,x)\) is not imposed at this stage, the results are stated in terms of measurable random variables \(R_n\) that dominate the regret. When the regret itself is measurable, these bounds can be read directly as expected regret bounds.
As noted in Remark 3, we separately consider the case where \(g_p\) is essentially bounded away from \(0\) (Theorem 1) and the case where \(g_p\) satisfies a nontrivial margin-mass bound (Theorem 2).
Theorem 1. Suppose Assumptions 1, 2, and 3 hold and there exist \(p>q\) and a constant \(g_\wedge>0\) such that \[V^*(x)-Q^*(x,a) \ge g_\wedge \mathop{\mathrm{dist}}(a,\mathbb{A}^*(x))^p,\] for all \(a\in\mathbb{A}\) and for \(\lambda_\mu\)-a.e.\(x\in\mathbb{X}\). Then there exists a measurable random variable \(R_n\) with \(R_n\ge \mathrm{Regret}(\hat{\pi}_n;\mu)\) such that for all \(n\geq 1\), \[ER_n \le C n^{-p/(2(p-q))}\] for some constant \(C<\infty\), depending on \(\gamma,C_{\mathrm{conc}},p,q,g_\wedge\) and \(C_{\Lambda,k_*}\), where \(k_*:=\left\lceil{p/(p-q)}\right\rceil\vee 2\).
Theorem 2. Suppose Assumptions 1, 2, 3, and 4 hold. Then there exists a measurable random variable \(R_n\) with \(R_n\ge \mathrm{Regret}(\hat{\pi}_n;\mu)\) such that for all \(n\ge 2\):
if \(q\leq p<q(m+1)\), then \(ER_n \le C n^{-(m+1)/(2m)}\),
if \(p=q(m+1)\), then \(ER_n \le C n^{-(m+1)/(2m)}\log n\),
if \(p>q(m+1)\), then \(ER_n \le C n^{-p/(2(p-q))}\),
for some \(C<\infty\), depending only on \(\gamma,C_{\mathrm{conc}},M,m,p,q,C_\delta\), and \(\left\{{C_{\Lambda,k}: k\ge 2}\right\}\).
We note that when \(q< p < q(m+1)\), \(\frac{m+1}{2m}< \frac{p}{2(p-q)}\); and when \(p > q(m+1)\), \(\frac{m+1}{2m}> \frac{p}{2(p-q)}\). Therefore, Theorem 2 implies that for \(p\ge q\), \[\label{eqn:continuous95action95ub95summary} ER_n \le \widetilde{O} \left( n^{-\min\left\{{\frac{p}{2(p-q)},\frac{m+1}{2m}}\right\}} \right)\tag{9}\] where for the case \(p = q\) we read \(\frac{p}{2(p-q)} = +\infty\), and \(\widetilde{O}\) hides a \(\log n\) term only when \(p = q(m+1)\).
The two exponents in 9 correspond to two different bottlenecks. The exponent \(-p/(2(p-q))\) is the growth-limited rate. It appears when the error in estimating the optimal action from \(\widehat Q_n\) is converted into regret through the \(p\)-growth of \(Q^*(x,\cdot)\). The exponent \(-(m+1)/(2m)\) is the margin-mass-limited rate. It reflects the possibility that a \(\lambda_\mu\)-non-negligible set of states has weak growth, so that uniformly accurate Q-estimation may still lead to unstable action selection on those states. The critical case \(p=q(m+1)\) is where these two mechanisms balance, leading to the logarithmic factor.
Remark 4. We observe that since \(p>0\) in Theorem 2, the case \(q=0\) can only arise in (iii) when \(p>q(m+1)\). Thus, when \(q=0\), we recover the \(O(n^{-1/2})\) rate. The same happens in Theorem 1. This is the natural scaling, as the moments bounds on \(\Lambda_n(0)\) do not provide additional leverage beyond that for \(\delta_n\).
On the other hand, as noted in the introduction, when \(q>0\), the rate is always faster than the canonical \(n^{-1/2}\). Together with the matching lower bound, this shows that the \(\Lambda_n(q)\) envelope Assumption 2 plays a pivotal role in guaranteeing fast convergence.
Given the crucial role of \(q\), in Section 5 we provide a separate treatment that imposes regularity conditions on the model primitives to guarantee Assumption 2.
Define the policy error at state \(x\in\mathbb{X}\) by \[\ell_n(x):=V^*(x)-Q^*(x,\hat{\pi}_n(x)).\] When \(p>q\), we use the convention that \(g_p(x)^{-\alpha}=+\infty\) on the set \(\{g_p(x)=0\}\) for any \(\alpha>0\), and \(g_p(x)^0\equiv 1\).
The proof of both upper bounds relies on the following key stability property of the greedy action.
Proposition 2 (Greedy stability under \(p\)-growth). Suppose Assumptions 1, 2, and 7 hold. For any \(x\in\mathbb{X}\), the following hold:
If \(p=q\), then \[\ell_n(x) \le 2\delta_n \mathbb{1}\left\{{g_p(x)\le \Lambda_n(q)}\right\}.\]
If \(p>q\), with \(\alpha=q/(p-q)\) and \(\beta=p/(p-q)\), \[\ell_n(x) \le \min\left\{{2\delta_n,\;\Lambda_n(q)^{\beta} g_p(x)^{-\alpha}}\right\}.\]
A key insight from the proof of this proposition is that the error \(\ell_n(x)\) is bounded above by the action selection error \(\mathop{\mathrm{dist}}(\hat{\pi}_n(x),\mathbb{A}^*(x))^q\) and \(\Lambda_n(q)\) by Assumption 2, while it is bounded below by the action selection error raised to the power \(p\) and \(g_p(x)\) through 7 . Together, these bounds imply that the action selection error is at most \(\Lambda_n(q)^{1/(p-q)}g_p(x)^{-1/(p-q)}\) when \(p>q\); that is, the interplay between the growth-in-action and the \(Q\)-estimation-error controls the action selection error at each state \(x\in\mathbb{X}\). Substituting this estimate back into the upper bound then yields the claim in Proposition 2.
Proof of Proposition 2. Fix \(x\in\mathbb{X}\) and set \(\hat{a}:=\hat{\pi}_n(x)\).
If \(\hat{a}\in\mathbb{A}^*(x)\), then \(\ell_n(x)=0\) and the bounds hold. Hence, we only need to consider the case \(\hat{a}\notin\mathbb{A}^*(x)\) and set \(d:=\mathop{\mathrm{dist}}(\hat{a},\mathbb{A}^*(x))>0\).
By definition of \(\hat{a}=\hat{\pi}_n(x)\) in 6 , \(\widehat Q_n(x,\hat{a})\ge \widehat Q_n(x,a^*)\) for every \(a^*\in\mathbb{A}^*(x)\). Hence, \[\begin{align} Q^*(x,a^*)-Q^*(x,\hat{a}) &= Q^*(x,a^*)\pm \widehat Q_n(x,\hat{a}) \pm \widehat Q_n(x,a^*)-Q^*(x,\hat{a})\\ &\le Q^*(x,a^*) + \widehat Q_n(x,\hat{a}) - \widehat Q_n(x,a^*)-Q^*(x,\hat{a})\\ &\le \left|\widehat Q_n(x,a^*)-Q^*(x,a^*)\right|+\left|\widehat Q_n(x,\hat{a})-Q^*(x,\hat{a})\right|. \end{align}\] Using Assumption 2, \[\label{eqn:tu95Q95err95bd95by95delta} Q^*(x,a^*)-Q^*(x,\hat{a})\le 2\delta_n.\tag{10}\] Since \(Q^*(x,a^*)=V^*(x)\) by 5 , this gives \(\ell_n(x)\le 2\delta_n\).
Moreover, by Assumption 2, \[\left( \widehat Q_n(x,\hat{a})-Q^*(x,\hat{a}) \right)-\left( \widehat Q_n(x,a^*)-Q^*(x,a^*) \right) \le \Lambda_n(q)\left|\hat{a}-a^*\right|^q.\] Using \(\widehat Q_n(x,\hat{a})\ge \widehat Q_n(x,a^*)\) and rearranging yields \[Q^*(x,a^*)-Q^*(x,\hat{a})\le \Lambda_n(q)\left|\hat{a}-a^*\right|^q.\] Taking the infimum over \(a^*\in\mathbb{A}^*(x)\) gives \[\label{eqn:tu95Q95err95ub95by95Lambda} \ell_n(x)\le \Lambda_n(q)\mathop{\mathrm{dist}}(\hat{a},\mathbb{A}^*(x))^q=\Lambda_n(q) d^q.\tag{11}\] On the other hand, by 7 , \[\label{eqn:tu95Q95err95lb95by95growth} \ell_n(x)=V^*(x)-Q^*(x,\hat{a})\ge g_p(x)d^p.\tag{12}\]
If \(p=q\), then 11 and 12 imply \(g_p(x)\le \Lambda_n(q)\). Therefore, whenever \(\hat{a} \notin\mathbb{A}^*(x)\) we have \(\mathbb{1}\{g_p(x)\le \Lambda_n(q)\}=1\), and the bound \[\ell_n(x)\le 2\delta_n \mathbb{1}\left\{{g_p(x)\le \Lambda_n(q)}\right\}\] follows from 10 .
If \(p>q\) and \(g_p(x)=0\), then when \(q>0\) the convention gives \(\Lambda_n(q)^\beta g_p(x)^{-\alpha}=+\infty\), so 10 yields the stated minimum bound; when \(q=0\), we have \(\alpha=0\) and \(\beta=1\), so combining 10 and 11 gives \(\ell_n(x)\le \min\left\{{2\delta_n,\Lambda_n(0)}\right\}\).
If \(p>q\) and \(g_p(x)>0\), then combining 11 and 12 yields \(g_p(x)d^{p-q}\le \Lambda_n(q)\), i.e. \[d\le \left( \frac{\Lambda_n(q)}{g_p(x)} \right)^{1/(p-q)}.\] Substitute this into 11 to obtain \[\ell_n(x)\le \Lambda_n(q)^{1+q/(p-q)}g_p(x)^{-q/(p-q)}=\Lambda_n(q)^\beta g_p(x)^{-\alpha}.\] Taking the minimum with 10 yields the claim. ◻
Proof. By ?? in Proposition 1, \[\mathrm{Regret}(\hat{\pi}_n;\mu) \le \frac{C_{\mathrm{conc}}}{1-\gamma}\int_{\mathbb{X}}\ell_n(x) \lambda_\mu(dx).\] Thus it suffices to exhibit, for each \(n\), a measurable random variable dominating \(\int \ell_n d\lambda_\mu\) whose expectation admits the claimed rate.
Define a measurable function \(g_p:\mathbb{X}\to[0,\infty)\) by \(g_p(x)=g_\wedge\) on the \(\lambda_\mu\)-full-measure set where the assumed growth bound holds, and \(g_p(x)=0\) otherwise. Then 7 holds for all \(x\in\mathbb{X}\) and \(a\in\mathbb{A}\), while \(g_p(x)\ge g_\wedge\) for \(\lambda_\mu\)-a.e.\(x\).
Since \(p>q\), Proposition 2(ii) implies \[\ell_n(x)\le \Lambda_n(q)^\beta g_p(x)^{-\alpha} \qquad\text{for all }x\in\mathbb{X},\] with \(\alpha:=q/(p-q)\) and \(\beta:=p/(p-q)\). Therefore, \[\int_{\mathbb{X}}\ell_n d\lambda_\mu \le \Lambda_n(q)^\beta \int_{\mathbb{X}} g_p(x)^{-\alpha} \lambda_\mu(dx) \le g_\wedge^{-\alpha}\Lambda_n(q)^\beta.\] Applying ?? yields \[\mathrm{Regret}(\hat{\pi}_n;\mu) \le \frac{C_{\mathrm{conc}}}{1-\gamma}g_\wedge^{-\alpha}\Lambda_n(q)^\beta.\] Hence we may take \[R_n:= \frac{C_{\mathrm{conc}}}{1-\gamma}g_\wedge^{-\alpha}\Lambda_n(q)^\beta.\] Let \(k_*:=\left\lceil{\beta}\right\rceil\vee 2\). By monotonicity of \(L^q\) norms and Assumption 2, \[\begin{align} ER_n &=\frac{C_{\mathrm{conc}}}{1-\gamma}g_\wedge^{-\alpha}E\left[ \Lambda_n(q)^\beta \right]\\ &\le \frac{C_{\mathrm{conc}}}{1-\gamma}g_\wedge^{-\alpha}E\left[ \Lambda_n(q)^{k_*} \right]^{\beta/k_*}\\ &\le Cn^{-\beta/2}, \end{align}\] for a constant \(C<\infty\) depending on \(\gamma,C_{\mathrm{conc}},p,q,g_\wedge\), and \(C_{\Lambda,k_*}\). Since \(\beta/2=p/(2(p-q))\), the result follows. ◻
Proof. By ?? in Proposition 1, \[\label{eqn:thm295pdl95start} \mathrm{Regret}(\hat{\pi}_n;\mu) \le \frac{C_{\mathrm{conc}}}{1-\gamma}\int_{\mathbb{X}}\ell_n(x) \lambda_\mu(dx).\tag{13}\] As in Remark 2, we work throughout with strictly positive envelopes \(\delta_n,\Lambda_n(q)>0\), so all ratios used below are well defined. To simplify notation, when \(p>q\) we define the exponents \[\alpha:=\frac{q}{p-q}, \quad\text{and}\quad \beta:=\frac{p}{p-q} = \alpha+1.\]
We treat the cases in Theorem 2 separately. Moreover, we split the case \(q\leq p<q(m+1)\) into \(p=q\) and \(q<p<q(m+1)\).
By Proposition 2(i), \[\int_{\mathbb{X}}\ell_n(x) \lambda_\mu(dx) \le 2\delta_n \lambda_\mu(\left\{{g_p\le \Lambda_n(q)}\right\}).\] By the margin-mass condition 8 , applied at \(u=\Lambda_n(q)\), \[\lambda_\mu(\left\{{g_p\le \Lambda_n(q)}\right\})\le M\Lambda_n(q)^{1/m}.\] Therefore, \[\int_{\mathbb{X}}\ell_n(x) \lambda_\mu(dx) \le 2M\delta_n\Lambda_n(q)^{1/m},\] and 13 yields \[\mathrm{Regret}(\hat{\pi}_n;\mu)\le R_n, \quad \text{with}\quad R_n:=\frac{2MC_{\mathrm{conc}}}{1-\gamma} \delta_n\Lambda_n(q)^{1/m}.\] Using Cauchy–Schwarz and Assumption 2, \[E[\delta_n\Lambda_n(q)^{1/m}] \le E[\delta_n^2]^{1/2} E[\Lambda_n(q)^{2/m}]^{1/2}.\] Let \(k_1:=\left\lceil{2/m}\right\rceil\vee 2\). By monotonicity of moments, \(E[\Lambda_n(q)^{2/m}] \le E[\Lambda_n(q)^{k_1}]^{2/(mk_1)}\), hence \[ER_n \le \frac{2MC_{\mathrm{conc}}}{1-\gamma} E[\delta_n^2]^{1/2} E[\Lambda_n(q)^{k_1}]^{1/(mk_1)} \le C n^{-(m+1)/(2m)}.\]
For cases \(q<p\le q(m+1)\), we first note that in this regime \(\alpha\geq 1/m\). We will use the following lemma; its proof is given in Appendix 7.1.
Lemma 1. Let \(G\ge 0\) be a random variable such that \(\mathbb{P}(G\le t)\le M t^{1/m}\) for all \(t\in[0,1]\). Fix \(\alpha\ge 1/m\), and let \(u>0\) and \(v>0\). Interpret \(G^{-\alpha}=+\infty\) on \(\{G=0\}\).
If \(\alpha>1/m\), then there exists \(C_{\mathrm{tr}}<\infty\), depending only on \((M,m,\alpha)\), such that \[E\left[ \min\left\{{2u,\;vG^{-\alpha}}\right\} \right] \le C_{\mathrm{tr}}\left( u^{1-1/(m\alpha)}v^{1/(m\alpha)} + v \right).\]
If \(\alpha=1/m\), then \[E\left[ \min\left\{{2u,\;vG^{-\alpha}}\right\} \right] \le (M+1)v + Mm v\max\left\{{0, \log\left( \frac{2u}{v} \right)}\right\}.\]
We note that the proof of this lemma relies on optimally truncating the law of the random variable \(G\) at small values. In particular, the “tr” subscript in \(C_{\mathrm{tr}}\) stands for truncation. Equipped with Lemma 1, we analyze \(q<p<q(m+1)\) and \(p = q(m+1)\) separately.
Note that \(\alpha>1/m\) in this regime. By Proposition 2(ii), \[\ell_n(x)\le \min\left\{{2\delta_n,\;\Lambda_n(q)^\beta g_p(x)^{-\alpha}}\right\}.\]
Let \(X\) be an auxiliary random variable with law \(\lambda_\mu\) under \(\mathbb{P}\) and set \(G:=g_p(X)\). By 8 , \[\mathbb{P}(G\le t)=\lambda_\mu(\{g_p\le t\})\le M t^{1/m},\] for all \(t\ge 0\). So, applying Lemma 1 (i) to \(G\), with \(u=\delta_n\) and \(v=\Lambda_n(q)^\beta\), gives \[\label{eqn:tu951pm95case95err95ub} \begin{align} \int_{\mathbb{X}}\ell_n d\lambda_\mu &\leq \mathbb{E}\left[ \min\left\{{2\delta_n,\;\Lambda_n(q)^\beta G^{-\alpha}}\right\} \right]\\ &\le C_{\mathrm{tr}}\left( \delta_n^{1-1/(m\alpha)}\Lambda_n(q)^{\beta/(m\alpha)}+\Lambda_n(q)^\beta \right). \end{align}\tag{14}\]
Since \(\alpha=q/(p-q)\), \[1-\frac{1}{m\alpha}=\frac{q(m+1)-p}{mq}, \qquad \frac{\beta}{m\alpha}=\frac{p}{mq}.\] Therefore, combining 14 and 13 , we have \(\mathrm{Regret}(\hat{\pi}_n;\mu)\le R_n,\) where \[\label{eqn:tu95Rn95for951pm} R_n:= \frac{C_{\mathrm{conc}}C_{\mathrm{tr}}}{1-\gamma} \left( \delta_n^{(q(m+1)-p)/(mq)}\Lambda_n(q)^{p/(mq)}+\Lambda_n(q)^\beta \right).\tag{15}\]
To control the expectation of \(R_n\), set \[a:=\frac{q(m+1)-p}{mq}\in(0,1), \qquad b:=\frac{p}{mq}, \qquad k_2:=\left\lceil{\max\left\{{2,\frac{2p}{p+q(m-1)}}\right\}}\right\rceil.\] Note that \[\frac{b}{k_2}\leq \frac{p+q(m-1)}{2mq},\] so \[\frac{a}{2}+\frac{b}{k_2}\le \frac{q(m+1)-p}{2mq} + \frac{p+q(m-1)}{2mq} = 1.\] Applying the generalized Hölder inequality in Lemma 4 gives \[\begin{align} E[\delta_n^a\Lambda_n(q)^b] &\le E[\delta_n^2]^{a/2} E[\Lambda_n(q)^{k_2}]^{b/k_2}\\ &\le C n^{-a/2}n^{-b/2}\\ &= C n^{-(m+1)/(2m)}. \end{align}\] where the second step follows from Assumption 2 and \(C\) satisfies the dependence conditions in Theorem 2.
For the second term in 15 , let \(k_\beta:=\left\lceil{\beta}\right\rceil\vee 2\). Then by Jensen’s inequality, \[E[\Lambda_n(q)^\beta] \le E[\Lambda_n(q)^{k_\beta}]^{\beta/k_\beta} \le C n^{-\beta/2}.\] with some possibly different \(C\) that also satisfies the dependence conditions in Theorem 2. Since \(q<p<q(m+1)\) implies \[\frac{\beta}{2} = \frac{p}{2(p-q)}>\frac{m+1}{2m},\] the term \(E[\Lambda_n(q)^\beta]\) is of smaller order. Hence \(ER_n\le C n^{-(m+1)/(2m)}\) where the \(C\) is the max of the two cases.
In this case \(\alpha=1/m\). As in the previous case, Proposition 2 (ii) yields \[\ell_n(x)\le \min\left\{{2\delta_n,\;\Lambda_n(q)^\beta g_p(x)^{-\alpha}}\right\}.\] Let \(X\sim\lambda_\mu\) under \(\mathbb{P}\) and set \(G=g_p(X)\). Lemma 1 (ii) with \(u=\delta_n\) and \(v=\Lambda_n(q)^\beta\) gives \[\begin{align} \int_{\mathbb{X}}\ell_n d\lambda_\mu&= \mathbb{E}\left[ \min\left\{{2\delta_n,\;\Lambda_n(q)^\beta G^{-\alpha}}\right\} \right]\\ &\le (M+1)\Lambda_n(q)^\beta + Mm \Lambda_n(q)^\beta\max\left\{{0,\log\left( \frac{2\delta_n}{\Lambda_n(q)^\beta} \right)}\right\}. \end{align}\] Therefore, \(\mathrm{Regret}(\hat{\pi}_n;\mu)\le R_n,\) where \[\label{eqn:tu95Rn95case95peqm} R_n:= \frac{C_{\mathrm{conc}}}{1-\gamma} \left[ (M+1)\Lambda_n(q)^\beta + Mm \Lambda_n(q)^\beta\max\left\{{0,\log\left( \frac{2\delta_n}{\Lambda_n(q)^\beta} \right)}\right\} \right].\tag{16}\]
To bound the expectation of the logarithmic term, we use the following lemma, proved in Appendix 7.2.
Lemma 2. Suppose Assumption 2 holds. Fix \(\beta>1\) and set \(k_\beta:=\left\lceil{\beta+1}\right\rceil\). Then for all \(n\ge 2\), \[E\left[ \Lambda_n(q)^\beta\max\left\{{0,\log\left( \frac{2\delta_n}{\Lambda_n(q)^\beta} \right)}\right\} \right] \le C n^{-\beta/2}\log n,\] for some \(C<\infty\), depending only on \((\beta,C_\delta,C_{\Lambda,k_\beta})\).
Moreover, with \(k_\beta=\left\lceil{\beta+1}\right\rceil\), \[E[\Lambda_n(q)^\beta] \le E[\Lambda_n(q)^{ k_\beta}]^{\beta/ k_\beta} \le C n^{-\beta/2}.\] Since \(\beta/2=(m+1)/(2m)\), we obtain \(ER_n\le C n^{-(m+1)/(2m)}\log n\) for some possibly different \(C < \infty\) that satisfies the requirement of Theorem 2 and depends on \(\left\{{C_{\Lambda,k}:k\geq 2}\right\}\) only through \(C_{\Lambda,k_\beta}\).
In this case, \(\alpha\in[0,1/m)\). As in the previous cases, Proposition 2 (ii) yields \[\label{eqn:tu95ln95bd95pgm} \begin{align} \ell_n(x)&\le \min\left\{{2\delta_n,\;\Lambda_n(q)^\beta g_p(x)^{-\alpha}}\right\}\\ &\le \Lambda_n(q)^\beta g_p(x)^{-\alpha}\mathbb{1}\left\{{g_p(x) > 0}\right\} + 2\delta_n\mathbb{1}\left\{{g_p(x) = 0}\right\}. \end{align}\tag{17}\]
We will use the following lemma, whose proof is given in Appendix 7.3.
Lemma 3. Let \(G\ge 0\) satisfy \(\mathbb{P}(G\le u)\le M u^{1/m}\) for all \(u\in[0,1]\). Fix \(\alpha\in [0,1/m)\). Then \[E\left[ G^{-\alpha} \mathbb{1}\{G>0\} \right]\le 1+\frac{Mm\alpha}{1-m\alpha}.\]
As before, let \(X\sim \lambda_\mu\) be an auxiliary random variable with law \(\lambda_\mu\) under \(\mathbb{P}\) and set \(G:=g_p(X)\). Then \(\mathbb{P}(G\le u)\le M u^{1/m}\) on \(u\in[0,1]\) by 8 . Therefore, Lemma 3 implies \[C_{g}:=\mathbb{E}\left[ G^{-\alpha} \mathbb{1}\{G>0\} \right]<\infty.\] Therefore, from 17 and Assumption 4, we have \[\begin{align} \int_{\mathbb{X}}\ell_n d\lambda_\mu &\le \Lambda_n(q)^\beta\int_{\mathbb{X}}g_p(x)^{-\alpha}\mathbb{1}\left\{{g_p(x) > 0}\right\} \lambda_\mu(dx) + 2\delta_n\lambda_\mu(\left\{{g_p =0}\right\})\\ &= \Lambda_n(q)^\beta \mathbb{E}\left[ G^{-\alpha} \mathbb{1}\{G>0\} \right] + 2\delta_n\lambda_\mu(\left\{{g_p \leq 0}\right\})\\ &\le C_{g}\Lambda_n(q)^\beta. \end{align}\] This, combined with 13 , yields \(\mathrm{Regret}(\hat{\pi}_n;\mu)\le R_n\) where \[R_n:= \frac{C_{\mathrm{conc}}C_{g}}{1-\gamma}\Lambda_n(q)^\beta.\] Let \(k_\beta:=\left\lceil{\beta}\right\rceil\vee 2\). Then \[E[\Lambda_n(q)^\beta] \le E[\Lambda_n(q)^{k_\beta}]^{\beta/k_\beta} \le C n^{-\beta/2} = C n^{-p/(2(p-q))},\] where \(C\) depends on \(\left\{{C_{\Lambda,k}:k\ge 2}\right\}\) only through \(C_{\Lambda,k_\beta}\). This completes the proof of Theorem 2. ◻
In this section, we prove matching minimax lower bounds on the expected regret for policy learning that complement the upper bounds in Theorems 1 and 2. The lower bound is based on MDP instances that satisfy the assumptions of the upper bounds in a strong sense.
Specifically, for any fixed \(\gamma\in(0,1)\), \(q\in(0,1]\), \(p>q\), and \(m\geq 0\), we define two families of \(\theta\in\Theta=[-1,1]\)-indexed MDP instances, denoted by \(\left\{{\mathcal{M}_\theta^+,\mathcal{M}_\theta^-:\theta\in\Theta}\right\}\). To simplify notation, we suppress the dependence of \(\mathcal{M}_\theta^+\) and \(\mathcal{M}_\theta^-\) on \((\gamma,m,p,q)\), and use these families of instances only for fixed \((\gamma,m,p,q)\). The main result of this section can be understood as follows.
We show that the following (informal) statement holds for each fixed feasible \((\gamma,m,p,q)\).
Assumptions 1, 3, and 4 holds for all instances in \(\left\{{\mathcal{M}_\theta^+,\mathcal{M}_\theta^-:\theta\in\Theta}\right\}\) with the corresponding \((m,p)\).
There exists a data generating process (to be rigorously defined later) from which we can construct estimators \(\widehat Q_n^+\) and \(\widehat Q_n^-\) so that their estimation error compared to the corresponding optimal Q-functions \(Q_\theta^+\) and \(Q_\theta^-\) satisfies Assumption 2 with Hölder exponent \(q\).
Given the data generating process, the minimax expected regret for optimal policy learning over the family \(\left\{{\mathcal{M}_\theta^+:\theta\in\Theta}\right\}\) is lower bounded by \(\Omega\left( n^{-(m+1)/(2m)} \right)\), while over the family \(\left\{{\mathcal{M}_\theta^-:\theta\in\Theta}\right\}\) it is lower bounded by \(\Omega\left( n^{-p/(2(p-q))} \right)\).
Combining the two cases, we obtain lower bounds that match the upper bounds in Theorems 1 and 2, with only a \(\log n\) mismatch in the case \(p=q(m+1)\).
Remark 5. We note that the performance of a policy learning algorithm naturally depends on the quality of the data: if the data generating process reveals the optimal Q-function in one step, then one can achieve zero regret with \(n=1\). Thus, the lower bound should be interpreted as follows: even if one can construct an estimator of the optimal Q-function satisfying Assumption 2, one cannot in general guarantee a faster convergence rate than the stated lower bounds without additional assumptions on the MDP instance or the data generating process.
Next, we establish the minimax lower bound in a mathematically rigorous manner by carefully specifying the hard instance families, the data-generating processes, the admissible learning algorithms, and the minimax expected regret criterion.
In this section, we construct the families of MDPs \(\left\{{\mathcal{M}_\theta^+,\mathcal{M}_\theta^-:\theta\in\Theta}\right\}\) that are used in the subsequent proofs of minimax lower bounds. We note that \(\left\{{\mathcal{M}_\theta^+:\theta\in\Theta}\right\}\) will correspond to the \(m\)-margin-mass-limited family, hence leading to a lower bound of \(\Omega\left( n^{-(m+1)/(2m)} \right)\). On the other hand \(\left\{{\mathcal{M}_\theta^-:\theta\in\Theta}\right\}\) is \(p\)-growth-limited leading to a lower bound of \(\Omega\left( n^{-p/(2(p-q))} \right)\).
Specifically, all the MDP instances we construct will have common state, action, and noise spaces, transition function, and initial distribution. The only differences are the reward structures and noise distributions. Specifically, we define the state space to be \(\mathbb{X}:= [0,1]\cup \left\{{2}\right\}\), where \(2\) is considered a terminal absorbing state. The action and noise spaces are \(\mathbb{A}:= [-1,1]\) and \(\mathbb{W}= \left\{{-1,1}\right\}\times[0,1]\). The transition function is the deterministic absorption \(f(x,a,w) = 2\) for all \((x,a,w)\in \mathbb{X}\times\mathbb{A}\times \mathbb{W}\). The driving noise of the MDP is an i.i.d. sequence \(\left\{{W_i:i\ge 1}\right\}\), where each \(W_i = (Y_i,D_i)\in\mathbb{W}\). We will use a uniform initial distribution \(\mu\) on \([0,1]\).
The families \(\left\{{\mathcal{M}_\theta^+:\theta\in\Theta}\right\}\) are indexed by a parameter \(\theta\in\Theta \subset [-1,1]\). To reflect the common setting in which the reward is specified by the modeler, and where knowledge of the reward function alone does not allow direct inference of \(\theta\), we deliberately design the reward functions so that they are independent of \(\theta\). Under these constructions, the instances \(\mathcal{M}_\theta^+\) and \(\mathcal{M}_\theta^-\) can therefore be identified with the respective pairs consisting of a reward function and a law of \(W\), namely \((r^+,\psi_\theta^+)\) and \((r^-,\psi_\theta^-)\), where the corresponding reward functions and probability laws are defined as follows.
For \(\mathcal{M}_\theta^+\), we consider the function \[\label{eqn:def95hp} h_p(a) :=\frac{(1+a)^p}{(1+a)^p+(1-a)^p}.\tag{18}\] Then, the reward function \(r^+\) is defined by \[r^+(x,a,(y,d)):=x^m h_p(a)+ y\mathbb{1}\left\{{x\leq d}\right\}\left( 1- h_p(a) \right),\quad r^+(2,a,(y,d)) = 0\] for \(x\in[0,1]\), \(a\in \mathbb{A}\), and \((y,d)\in \mathbb{W}\). We note an important property of \(h_p\) underlying this construction: \(h_p(a)=\Theta((1+a)^p)\) as \(a\downarrow-1\), and \(1-h_p(a)=\Theta((1-a)^p)\) as \(a\uparrow 1\).
In this case, the law \[\label{eqn:psitheta43} \mathrm{Law}_{\theta}^+(W_1) = \psi_\theta^+ : = \frac{1-\theta}{2}\delta_{(-1,d_\theta^+)} + \frac{1+\theta}{2}\delta_{(1,d_\theta^+)},\quad d_\theta^+ = \left( \frac{|\theta|}{2} \right)^{1/m}.\tag{19}\] Thus, under \(\psi_\theta^+\), \(Y = \pm1\) with probability \((1\pm \theta)/2\) and \(D = d^+_\theta\) almost surely.
Since the controlled Markov chain transitions deterministically to state 2, where the associated reward is equal to 0, it follows that the optimal Q function is \[Q_\theta^+(x,a) = \int r^+(x,a,w)\psi_\theta(dw) = x^m h_p(a) + \theta\mathbb{1}\left\{{x\leq d^+_\theta}\right\}(1-h_p(a)).\label{eqn:Qtheta43}\tag{20}\] We note that \(h_p\) is designed to enforce the \(p\)-growth condition. The key intuition behind this construction leading to the lower bound rate is that, when \(\theta\) is small and \(x\leq d_\theta^+\), identifying the optimal action is difficult, since the optimum is \(+1\) or \(-1\) depending on the sign of \(\theta\). In particular, the hard margin width in this case is \(d_\theta^+\asymp |\theta|^{1/m}\), while the value gap incurred by taking the wrong action is of order \(|\theta|\). Therefore, if \(|\theta|\asymp n^{-1/2}\), the sign of \(\theta\) cannot be identified reliably, so the wrong action is chosen with constant probability. This yields a total state-averaged error (i.e., regret) of order \(\Omega(|\theta|d_\theta^+)=\Omega(n^{-(m+1)/(2m)}).\)
For \(\mathcal{M}_\theta^-\), the reward function \(r^-\) is defined by \[r^-(x,a,(y,d)):= y\;\mathrm{sign}(a)(|a|^q\wedge d^q) - ||a|-d|^p,\quad r^-(2,a,w) = 0\] for \(x\in[0,1]\) and \((a,(y,d))\in\mathbb{A}\times \mathbb{W}\), where \((x\wedge c) = \min{\left\{{x,c}\right\}}\).
Then, define the similar law \[\label{eqn:psitheta-} \mathrm{Law}_{\theta}^-(W_1) = \psi_\theta^- : = \frac{1-\theta}{2}\delta_{(-1,d_\theta^-)} + \frac{1+\theta}{2}\delta_{(1,d_\theta^-)},\quad d_\theta^-:= |\theta|^{\frac{1}{p-q}}\tag{21}\] where the only difference compared to 19 is that the deterministic \(D_1\) concentrates at \(d_\theta^-\).
In this case, the optimal Q-function is given by \[Q_\theta^-(x,a) =\int r^-(x,a,w)\psi_\theta(dw) = \theta\;\mathrm{sign}(a)(|a|^q\wedge (d_\theta^-)^q) - ||a|-d_\theta^-|^p.\label{eqn:Qtheta-}\tag{22}\]
We note that the intuition leading to the lower bound rate in this construction is as follows. The term \(-||a|-d_\theta^-|^p\) creates two candidate maximizers at \(a=\pm \, d_\theta^-\) and enforces the \(p\)-growth. The term \(\theta\,\mathrm{sign}(a)\left( |a|^q\wedge (d_\theta^-)^q \right)\) then breaks the tie by favoring the action with \(\mathrm{sign}(a)=\mathrm{sign}(\theta)\), while preserving \(q\)-Hölder continuity near \(0\). Thus, when \(\theta\) is small, the main difficulty is to determine which of \(+d_\theta^-\) and \(-d_\theta^-\), is optimal. The value loss from choosing the wrong branch is of order \(|\theta|(d_\theta^-)^q=|\theta|^{p/(p-q)}.\) Therefore, if \(|\theta|\asymp n^{-1/2}\), the sign of \(\theta\) cannot be identified reliably, so the wrong branch is selected with constant probability. Since this ambiguity occurs uniformly over the state space, the resulting regret is of order \(\Omega\bigl(|\theta|(d_\theta^-)^q\bigr)=\Omega\bigl(n^{-p/(2(p-q))}\bigr).\)
Remark 6. Observe that when \(x=2\), both rewards are \(0\), and the transition satisfies \(f(x,a,w)=2\) everywhere. Hence \(X^\pi_k=2\) for all \(k\geq 1\), so no further reward is collected after stage \(0\). Thus, the policy optimization problem effectively reduces to a single-stage contextual stochastic optimization problem, where the context is the realized initial state. Therefore, together with the lower bounds in Theorem 3, this shows that the optimal policy learning rates in Theorems 1 and 2 also apply to related stochastic optimization settings.
Next, we show that the instances defined above–specifically, their optimal Q-functions in 20 and 22 –satisfy Assumptions 1, 3, and 4.
Proposition 3. Fix any \(\gamma\in(0,1)\), Hölder exponent \(q\in(0,1]\), growth exponent \(p>q\), and margin-mass exponent \(m>0\). Then, any MDP instance within \(\left\{{\mathcal{M}_\theta^+,\mathcal{M}_\theta^-:\theta\in\Theta}\right\}\) satisfies Assumptions 1, 3, and 4 with parameters \((m,p,q)\) and reference measure \(\lambda_\mu:= \frac{1}{2}\mu + \frac{1}{2}\delta_2\).
Before presenting the proof, we note that the verification process in the proof reflects the careful design of the hard instance family. In particular, these verifications complement the intuition underlying the constructions that lead to the lower bound rates (cf. the discussion after 20 and 22 ).
Proof. Fix \(\theta\in\Theta=[-1,1]\). We verify Assumptions 1, 3, and 4 for both instances \(\mathcal{M}_\theta^+\) and \(\mathcal{M}_\theta^-\).
By the form of \((r^+,Q_\theta^+)\) and \((r^-,Q_\theta^-)\), the boundedness, measurability, and continuity requirements in Assumption 1 are clearly satisfied. Moreover, by the one-stage nature of the dynamics and rewards noted in Remark 6, a policy is optimal if and only if it maximizes the reward at time \(0\). Hence, 4 holds in both cases.
Fix any MDP instance \(\mathcal{M}_\theta^\dagger\) where \(\dagger\) can be \(+\) or \(-\). Let \(\pi:\mathbb{X}\to\mathbb{A}\) be any stationary policy and let \(\nu_\mu^\pi\) be the discounted occupancy measure as in Definition 2 with the dependence on \(\mathcal{M}_\theta^\dagger\) suppressed.
As noted in Remark 6, under both families of MDPs, \(X^\pi_0\sim\mu\) and \(X^\pi_k=2\) for all \(k\ge1\). Hence, the state’s marginal distribution at time \(0\) is \(\mu\), while for each \(k\ge1\) it is \(\delta_2\). Therefore, for \(\dagger = +\) and \(-\), \[\begin{align} \nu_\mu^\pi& =(1-\gamma)\mathrm{Law}_{\mathcal{M}_\theta^\dagger}(X^\pi_0)+ (1-\gamma)\sum_{k=1}^\infty \gamma^k \mathrm{Law}_{\mathcal{M}_\theta^\dagger}(X^\pi_k)\\ &= (1-\gamma)\mu + (1-\gamma)\sum_{k=1}^\infty \gamma^k \delta_2\\ &= (1-\gamma)\mu+\gamma\delta_2, \end{align}\] independent of \(\pi\) and \(\theta\).
Recall that \(\lambda_\mu=\frac{1}{2}\mu+\frac{1}{2}\delta_2\) and \(\gamma\in(0,1)\). Clearly \(\nu_{\mu}^\pi\ll \lambda_\mu\) and \[\frac{d \nu_{\mu}^\pi}{d\lambda_\mu}(x) = \begin{cases} 2(1-\gamma) & \text{if }x\in[0,1],\\ 2\gamma & \text{if }x=2, \end{cases}\] is a version of the likelihood ratio. Consequently, \[\mathop{\mathrm{ess sup}}_{\lambda_\mu}\frac{d \nu_{\mu}^\pi}{d\lambda_\mu}\le 2;\] i.e., Assumption 3 holds for both families with \(C_{\mathrm{conc}} = 2\).
We work with \(Q_\theta^+\) in 20 . Before we verify Assumption 4 for \(\mathcal{M}_\theta^+\), we establish some auxiliary facts. Note that for \(x\in[0,1],\;a\in\mathbb{A}\), \[\label{eqn:Qtheta4395cases} Q_\theta^+(x,a)= \begin{cases} x^m h_p(a), & x>d_\theta^+,\\ \theta+(x^m-\theta)h_p(a), & x\le d_\theta^+, \end{cases}\tag{23}\] and \(Q_\theta^+(2,a)=0\). Moreover, from 18 we have for \(a\in(-1,1)\), \[h_p(a)=\frac{1}{1+\left( \frac{1-a}{1+a} \right)^p},\] as well as \(h_p(-1)=0\) and \(h_p(1)=1\). Note that \(a\to \frac{1-a}{1+a}\) is decreasing on \((-1,1]\), hence \(h_p\) is increasing on \([-1,1]\). With these preparations, we proceed to verify Assumption 4.
Optimal action sets and values. We compute the optimal action set \(\mathbb{A}_\theta^+(x)\) and optimal value function \(V^+_\theta(x)\) for different cases of \(x\in[0,1]\) and \(\theta\in[-1,1]\).
If \(x>d_\theta^+\), then \(Q_\theta^+(x,a)=x^m h_p(a)\) is maximized by \(a=1\), so \(\mathbb{A}_\theta^+(x)=\{1\}\) and \(V_\theta^+(x)=x^m\).
If \(x\le d_\theta^+\) and \(\theta>0\), then \(x^m\le \theta/2\) so \(x^m-\theta<0\), hence \(\theta+(x^m-\theta)h_p(a)\) is maximized by taking \(h_p(a)=0\), i.e.\(a=-1\). Thus \(\mathbb{A}_\theta^+(x)=\{-1\}\) and \(V_\theta^+(x)=\theta\).
If \(x\le d_\theta^+\) and \(\theta<0\), then \(x^m-\theta>0\), so the expression is maximized by \(h_p(a)=1\), i.e.\(a=1\). Thus \(\mathbb{A}_\theta^+(x)=\{1\}\) and \(V_\theta^+(x)=x^m\).
If \(\theta=0\), then \(d_\theta^+=0\). For \(x>0\), we are in the first case and \(\mathbb{A}_0^+(x)=\{1\}\). At \(x=0\), \(Q_0^+(0,a)=0\) for all \(a\), hence \(\mathbb{A}_0^+(0)=\mathbb{A}\).
Moreover, at \(x=2\), \(Q_\theta^+(2,\cdot)\equiv 0\), so \(\mathbb{A}_\theta^+(2)=\mathbb{A}\).
Thus, the optimal action sets and the corresponding optimal values can be summarized as follows: \[\label{eqn:tu95A95V95breakdown} \renewcommand{\arraystretch}{1.2} \begin{array}{lll} \mathbb{A}_\theta^+(x) & V_\theta^+(x) & \text{Condition} \\ \hline \{1\} & x^m & x\in[0,1], \;\theta<0 \;\text{or}\;x>d_\theta^+\\ \{-1\} & \theta &x\in[0,1], \; \theta>0,\; x\le d_\theta^+\\ \mathbb{A}& 0 & x=2 \;\text{or}\;(\theta,x)=(0,0) \end{array}\tag{24}\]
The \(p\)-growth condition. We claim that for all \(x\in[0,1]\) and \(a\in\mathbb{A}\), \[\label{eqn:pgrowth95plus95new} V_\theta^+(x)-Q_\theta^+(x,a)\;\ge\;2^{-(p+1)}x^m\,\mathop{\mathrm{dist}}\!\big(a,\mathbb{A}_\theta^+(x)\big)^p.\tag{25}\] Also, \(V_\theta^+(2)-Q_\theta^+(2,a)=0\) and \(\mathop{\mathrm{dist}}(a,\mathbb{A}_\theta^+(2))=0\). Therefore, the \(p\)-growth condition 7 holds with \[\label{eqn:gplus95new} g_{p,\theta}^+(x):= \begin{cases} 2^{-(p+1)}x^m,& x\in[0,1],\\ 2,& x=2. \end{cases}\tag{26}\]
It remains to prove 25 . To show this, we first note that for all \(a\in[-1,1]\), \((1\pm a)^p\le 2^p\). Thus, \[\label{eqn:hp95basic95bounds} \begin{align} h_p(a)&=\frac{(1+a)^p}{(1+a)^p+(1-a)^p}\ge 2^{-(p+1)}(1+a)^p,\\ 1-h_p(a)&=\frac{(1-a)^p}{(1+a)^p+(1-a)^p}\ge 2^{-(p+1)}(1-a)^p. \end{align}\tag{27}\]
We now consider cases according to different optimal action sets in 24 .
If \(\mathbb{A}_\theta^+(x)=\{1\}\), then \(V_\theta^+(x)=x^m\) and from 23 \[V_\theta^+(x)-Q_\theta^+(x,a) = \begin{cases} x^m(1-h_p(a)), & x>d_\theta^+,\\ (x^m-\theta)(1-h_p(a)), & x\le d_\theta^+,\;\theta<0. \end{cases}\] In both situations, applying the lower bound in 27 yields \[V_\theta^+(x)-Q_\theta^+(x,a)\ge x^m(1-h_p(a)) \ge2^{-(p+1)}x^m(1-a)^p.\] Since \(\mathop{\mathrm{dist}}(a,\{1\})=1-a\) for \(a\in[-1,1]\), this yields 25 .
If \(\mathbb{A}_\theta^+(x)=\{-1\}\), then we observe from 24 that necessarily \(\theta>0\) and \(x\le d_\theta^+\), so \(x^m\le \theta/2\). Moreover, in this case \(V_\theta^+(x)=\theta\). Thus, \[\begin{align} V_\theta^+(x)-Q_\theta^+(x,a) &= \theta-\left( x^m h_p(a)+\theta(1-h_p(a)) \right)\\ &=(\theta-x^m)h_p(a)\\ &\geq \frac{\theta}{2}h_p(a)\\ &\geq 2^{-(p+1)}x^m(a+1)^p. \end{align}\] Since \(\mathop{\mathrm{dist}}(a,\{-1\})=a+1\) for \(a\in[-1,1]\), this also implies 25 .
If \(\mathbb{A}_\theta^+(x)=\mathbb{A}\), which this only occurs when \((\theta,x)=(0,0)\) or \(x=2\), then \(\mathop{\mathrm{dist}}(a,\mathbb{A}_\theta^+(x))=0\) and \(V_\theta^+(x)-Q_\theta^+(x,a)=0\), so 25 holds trivially.
As these cases summarize all possible \(\mathbb{A}_\theta^+(x)\), we have shown that 25 holds for all \(x\in[0,1]\) and \(a\in\mathbb{A}\), checking the \(p\)-growth condition for \(\mathcal{M}_\theta^+\).
The margin-mass condition. With \(g_{p,\theta}^+\) defined in 26 , fix \(t\ge 0\). If \(t<2\), then \(2\notin\{x\in\mathbb{X}:g_{p,\theta}^+(x)\le t\}\), and thus \[\begin{align} \lambda_\mu\left( \{x\in\mathbb{X}:g_{p,\theta}^+(x)\le t\} \right) &= \frac{1}{2}\mu\left( \left\{{x\in[0,1]:2^{-(p+1)}x^m\le t}\right\} \right)\\ &= \frac{1}{2}\mu\left( \left\{{x\in[0,1]:x\le (2^{p+1}t)^{1/m}}\right\} \right)\\ &\leq2^{\frac{p+1}{m}-1}t^{1/m}. \end{align}\]
If \(t\ge 2\), then \(g_{p,\theta}^+(2)=2\le t\). Also \(g_{p,\theta}^+(x)\le 2^{-(p+1)}\le t\) for all \(x\in[0,1]\), so \(\{x:g_{p,\theta}^+(x)\le t\}=\mathbb{X}\). Therefore, for \(t\ge 2\), \[\lambda_\mu\left( \{x\in\mathbb{X}:g_{p,\theta}^+(x)\le t\} \right) = 1\leq 2^{-1/m}t^{1/m}.\]
Therefore, combining the two cases shows that 8 holds for all \(t\ge 0\) for \(\mathcal{M}_\theta^+\) with exponent \(m\) and constant \(M=\max\left\{{2^{\frac{p+1}{m}-1},2^{-1/m}}\right\}\).
Recall \(Q_\theta^-\) computed in 22 .
Optimal action sets and values. Since \(Q_\theta^-(x,\cdot)\) is independent of \(x\in[0,1]\), the maximizing action is the same for all \(x\in[0,1]\). As noted after 22 , it is not hard to see that \[\label{eqn:tu95A95V95breakdown95minus} \renewcommand{\arraystretch}{1.2} \begin{array}{lll} \mathbb{A}_\theta^-(x) & V_\theta^-(x) & \text{Condition} \\ \hline \{d_\theta^-\} & |\theta|^{p/(p-q)} & x\in[0,1], \;\theta\geq 0 \\ \{-d_\theta^-\} & |\theta|^{p/(p-q)} &x\in[0,1], \; \theta<0\\ \mathbb{A}& 0 & x=2 \end{array}\tag{28}\] and, when \(\theta = 0\), \(a_\theta^-\) is interpreted as 0.
The \(p\)-growth condition. We define \[c_p:= \inf_{\rho \ge 0}\frac{1+|1-\rho|^p}{(1+\rho)^p} .\] It is not hard to see that \(c_p > 0\). We show that for all \(\theta\in[-1,1]\) and \((x,a)\in\mathbb{Z}\), \[\label{eqn:ts95pgrowth95minus} V_\theta^-(x)-Q_\theta^-(x,a)\ge c_{p}\mathop{\mathrm{dist}}\left( a,\mathbb{A}_\theta^-(x) \right)^p.\tag{29}\] Hence the \(p\)-growth condition 7 hold with \(g_p\equiv c_p\).
Note that, by symmetry, we only need treat the case \(\theta \geq 0\). The case \(\theta< 0\) is equivalent when we change the variable \(a\) to \(-a\). Therefore, we will assume \(\theta\geq 0\) and, in particular, \(\mathbb{A}_\theta^{-}(x) = d_\theta^-\) when \(x\in[0,1]\).
We proceed to separately bound the growth for \(a \ge 0\) and \(a < 0\). When \(a\ge 0\), by 28 and 22 , we have \[\begin{align}V_\theta^-(x) - Q_\theta^-(x,a) &= |a - d_\theta^-|^p + \theta^{p/(p-q)} - \theta(a^q\wedge \theta^{q/(p-q)})\\ &=|a - d_\theta^-|^p + \theta(\theta^{q/(p-q)} - a^q\wedge \theta^{q/(p-q)})\\ &= \begin{cases} (d_\theta^- - a)^p + \theta((d_\theta^-)^q - a^q), &0\leq a<d_\theta^-,\\ (a-d_\theta^-)^p, & d_\theta^- \leq a\le 1, \end{cases} \end{align}\] for all \(x\in[0,1]\). Thus, when \(a\geq 0\) \[\label{eqn:tu95v95Q95minus95growth95age0} V_\theta^-(x) - Q_\theta^-(x,a) \geq |a-d_\theta^-|^p = \mathop{\mathrm{dist}}(a,\mathbb{A}_\theta^-(x))^p \geq c_p\mathop{\mathrm{dist}}(a,\mathbb{A}_\theta^-(x))^p\tag{30}\] for all \(x\in[0,1]\) and \(a\ge 0\), where we used \(c_p\leq 1\).
On the other hand, if \(a<0\), \[V_\theta^-(x) - Q_\theta^-(x,a) \geq |d_\theta^--|a| |^p + (d_\theta^-)^p\] Note that \(\mathbb{A}_\theta^- = \left\{{d_\theta^-}\right\}\) which is non-negative. So for \(a < 0\) and \(x\in[0,1]\), \(\mathop{\mathrm{dist}}(a,\mathbb{A}_\theta^-(x))= |a| + d_\theta^-\). Using this fact, we bound \[\label{eqn:tu95v95Q95minus95growth95ale0} \begin{align}V_\theta^-(x) - Q_\theta^-(x,a) &\geq \frac{|d_\theta^- -|a| |^p + (d_\theta^-)^p}{(|a| + d_\theta^-)^p}\mathop{\mathrm{dist}}(a,\mathbb{A}_\theta^-(x))^p\\ &= \frac{|1- \rho_\theta |^p + 1}{(\rho_\theta + 1)^p}\mathop{\mathrm{dist}}(a,\mathbb{A}_\theta^-(x))^p\\ &\geq c_p \mathop{\mathrm{dist}}(a,\mathbb{A}_\theta^-(x))^p \end{align}\tag{31}\] for \(x\in[0,1]\), where \(\rho_\theta = |a|/d_\theta^-\).
Finally, combining 30 , 31 , and the trivial case \(x = 2\), we conclude 29 for \(\theta\ge 0\). For \(\theta < 0\), as noted earlier, 29 follows from the same argument under a change of variable \(b = -a\).
The margin-mass condition. Note that for the \(-\) case, \(g_p\equiv c_p\), so the margin mass condition 8 in Assumption 4 holds with any \(m> 0\) and \(M = c_p^{-1/m}\).
To conclude, we have verified Assumptions 1, 3, and 4 for both instances \(\mathcal{M}_\theta^+\) and \(\mathcal{M}_\theta^-\) for any \(\theta\in[-1,1]\), \(m > 0\), \(p>q>0\). This completes the proof. ◻
Definition 3 (Adapted policy learning and Q estimation algorithms). A data generating process is a filtered probability space \(\left\{{\Omega,\mathcal{F},\left\{{\mathcal{D}_n:n\ge 1}\right\},P}\right\}.\)
An adapted policy learning algorithm is a sequence of measurable maps \[\left\{{\hat{\pi}_n: \hat{\pi}_n\in m\left\{{ \mathcal{X}\times \mathcal{D}_n\rightarrow\mathcal{A}}\right\},\; n\ge 1}\right\}.\] We denote the class of all adapted policy learning algorithm at time \(n\) by \(\hat{\pi}_n\in \mathrm{PLA}_n\) where the dependence on the data generating process is suppressed.
Similarly, an adapted Q-estimation algorithm is a sequence of measurable maps \[\left\{{\widehat Q_n: \widehat Q_n\in m\left\{{ \mathcal{Z}\times \mathcal{D}_n\rightarrow\mathcal{B}(\mathbb{R})}\right\},\; n\ge 1}\right\}.\]
Before we state the main minimax lower bound theorem, we redefine the policy regret notation (consistent with the definition in Definition 1) to avoid potential ambiguity. For measurable function \(\pi:\mathbb{X}\rightarrow\mathbb{A}\) and \(\mathcal{M}_\theta^\dagger\), \(\dagger = +,-\), let \[\label{eqn:def95reg95hard95M} \mathrm{Regret}\left( \pi;\mathcal{M}_\theta^\dagger \right):= V_\theta^\dagger(\mu) - V_\theta^{\pi,\dagger}(\mu) = V_\theta^\dagger(\mu) - \int_\mathbb{X}Q_\theta^\dagger(x,\pi(x))\mu(dx)\tag{32}\] where \(\mu\) is the common uniform initial distribution, \(Q_\theta^\dagger\) is defined in 20 or 20 , \(V_\theta^{\pi,\dagger}(\mu)\) is defined as in 2 using the instance \(\mathcal{M}_\theta^\dagger\), and the corresponding \(V_\theta^\dagger\) is computed in the proof of Proposition 3. Here, we note that the second equality follows from the one-stage structure as noted in Remark 6.
Therefore, for \(\hat{\pi}_n\in \mathrm{PLA}_n\), \(\hat{\pi}_n(\omega,\cdot):\mathbb{X}\rightarrow\mathbb{A}\) is measurable. Hence, the regret in 32 is well defined for \(\hat{\pi}_n\in \mathrm{PLA}_n\). With this notation in place, we now state the main lower bound theorem.
Theorem 3. Fix any \(\gamma\in(0,1)\), Hölder exponent \(q\in(0,1]\), growth exponent \(p>q\), and margin-mass exponent \(m>0\). For any \(\theta\in\Theta = [-1,1]\) and \(\dagger = +\) or \(-\), there exists a data generating process \(\left\{{\Omega,\mathcal{F},\left\{{\mathcal{D}_n:n\ge 1}\right\},P_\theta^\dagger}\right\}\) supporting an adapted Q-estimation algorithms \(\left\{{\widehat Q_n^\dagger:n\geq 1}\right\}\) that satisfies Assumption 2 with \(Q^*\) replaced by \(Q^\dagger_\theta\) and \(P\) replaced by \(P_\theta^\dagger\). At the same time, the uniform regret achievable by any adapted policy learning algorithms over each of the two families is lower bounded by \[\label{eq:lb95margin95mass} \inf_{\hat{\pi}_n\in \mathrm{PLA_n}}\max_{\theta\in\Theta} E_\theta^+\left[ \mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_\theta^+ \right) \right] \geq Cn^{-(m+1)/(2m)}\tag{33}\] and \[\label{eq:lb95growth} \inf_{\hat{\pi}_n\in \mathrm{PLA_n}}\max_{\theta\in\Theta} E_\theta^-\left[ \mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_\theta^- \right) \right] \geq Cn^{-p/(2(p-q))}\tag{34}\] where the constant \(C\) is independent of \(n\).
In addition, by Proposition 3, the instances \(\mathcal{M}_\theta^\dagger,\;\dagger = +,-\) further satisfy Assumptions 1, 3, and 4. Therefore, for MDPs satisfying Assumptions 1–4, the expected policy regret is lower bounded in a minimax sense by \[\Omega\left( \max\left\{{n^{-p/(2(p-q))},\,n^{-(m+1)/(2m)}}\right\} \right) = \Omega\left( n^{-\min\left\{{\frac{p}{2(p-q)},\,\frac{m+1}{2m}}\right\}} \right),\] which matches the upper bound in 9 , except in the case \(p=q(m+1)\), where there is a \(\log n\) gap.
We note that, once the hard MDP families are carefully constructed, the lower-bound proof of Theorem 3, although technical, follows standard reduction arguments from the statistics literature; see, for example, [36]. At the same time, the proof also relies on a data-generating process motivated by a data-driven stochastic optimal control framework. This framework, which we study in detail in the next section, concerns learning an optimal control policy for a system whose dynamics are known, but whose noise distribution is unknown and must be estimated from data.
In view of these considerations, we defer the proof of Theorem 3 to Appendix 8.
From the highlight in Remark 4, we see that the Hölder exponent \(q\) in Assumption 2 is crucial for fast convergence of policy regret. In this section, we consider a class of policy learning environments that is widely applicable in operations settings, and show that Assumptions 1 and 2 hold with \(q>0\) under mild regularity conditions on the model primitives. We then present two important OR problems that naturally satisfy these sufficient conditions. The core verification mechanisms extend naturally to other dynamical systems arising in operations applications. This suggests the broad applicability of our results and, more importantly, explains why fast convergence commonly arises in these settings.
Specifically, we consider the optimal policy learning problem for a Markov stochastic dynamic system driven by an i.i.d. noise sequence \(\left\{{W_t:t\geq 1}\right\}\). The system evolution follows the state recursion \[\label{eqn:noise95model95recursion} X^\pi_{t+1}=f(X^\pi_t,A_t^\pi,W_{t+1}),\tag{35}\] where the measurable transition function \(f:\mathbb{X}\times\mathbb{A}\times\mathbb{W}\to\mathbb{X}\) is known, while the distribution of the sequence \(\left\{{W_t}\right\}\) must be inferred from data. This setting is common in data-driven control problems in OR, including applications with demand, workload arrival, and service-rate uncertainty.
Specifically, we consider an i.i.d.data set consisting of \(2n\) samples \(\{W_i^V,W_i^Q:i=1,\dots,n\}\) with law \(\psi\) defined on an underlying probability space \((\Omega,\mathcal{F},P)\). To simplify notation, let \(W\overset{d}{=}W_1^V\) also be defined on \((\Omega,\mathcal{F},P)\), independent of \(\{W_i^V,W_i^Q:i=1,\dots,n\}\). For all measurable \(\phi\) and \(U=V,Q\), define \(\mathcal{F}_n^U = \sigma(W_1^U,\dots W_n^U),\) \[\psi_n^U:=\frac{1}{n}\sum_{i=1}^n\delta_{W_i^U} \quad\text{and}\quad E_n^U\phi(W)=\int_\mathbb{W}\phi(w)\psi_n^U(dw).\] To signify adaptivity, a random function with a superscript \(U = V\) or \(Q\) is generally \(\mathcal{F}_n^U\) measurable (e.g. \(E[\phi(G^V_n(\theta,w))|\mathcal{F}_n^V] = \phi(G^V_n(\theta,w))\) for all bounded measurable \(\phi\)).
We then construct the estimator in two steps. First, we solve the Bellman equation for the value function: \[\label{eqn:def95hatVn} \widehat V_n(x)=\sup_{a\in\mathbb{A}}E_n^V[r(x,a,W)+\gamma \widehat V_n(f(x,a,W))]\tag{36}\] for all \(x\in\mathbb{X}\). Then, using the remaining samples, we define \[\label{eqn:def95hatQn} \widehat Q_n(z):=E_n^Q[r(z,W)+\gamma \widehat V_n(f(z,W))].\tag{37}\]
We note that the sample split is used to make the verification transparent. The \(V\)-sample constructs the empirical Bellman fixed point \(\widehat V_n\), and the independent \(Q\)-sample evaluates the corresponding action-value estimator. Conditional on \(\mathcal{F}_n^V\), \(\widehat V_n\) is fixed when averaging over the \(Q\)-sample, which separates the regularity of \(\widehat V_n\) from the empirical process error that determines \(\delta_n\) and \(\Lambda_n(q)\). Under broad conditions, this two-layer estimator satisfies Assumption 2.
We first identify regularity conditions under which the Bellman operator preserves Hölder continuity. This verifies Assumption 1 and helps to establish the regularity of \(\widehat V_n\).
For a function \(g:\mathbb{S}\to\mathbb{R}\), where \(\mathbb{S}\) is either \(\mathbb{X}\) or \(\mathbb{Z}\), and \(\alpha\in(0,1]\), define the \(\alpha\)-Hölder coefficient by \[[g]_{\alpha,\mathbb{S}}:= \sup_{u\neq u'\in\mathbb{S}}\frac{|g(u)-g(u')|}{|u-u'|^\alpha}.\]
Assumption 5. Assume the following conditions hold.
For all \(z\in\mathbb{Z}\), \(\left|E[r(z,W)]\right|\le r_\vee.\)
For some \(\alpha_r\in(0,1]\), \(r\) is weakly \(\alpha_r\)-Hölder continuous in \(z\); i.e. there is \(\ell_r <\infty\) such that \[\label{eqn:r95weak95holder95z} E\left|r(z,W)-r(z',W)\right| \le \ell_r |z-z'|^{\alpha_r}\tag{38}\] for all \(z,z'\in\mathbb{Z}\).
\(f\) is weakly \(\ell_f\)-Lipschitz continuous in \(z\); i.e. \[\label{eqn:f95weak95lip95z} E\left|f(z,W)-f(z',W)\right| \le \ell_f |z-z'|\tag{39}\] for all \(z,z'\in\mathbb{Z}\).
We note that these weak continuity and integrability assumptions are rather mild for OR applications, where many dynamic models naturally have a max-plus-linear structure; see Section 5.3. Under these regularity conditions, we show in the following Theorem 4 that the resulting optimal value and \(Q\)-functions are Hölder continuous. The proof follows from a successive approximation argument and is deferred to Appendix 9.1.
Theorem 4 (Hölder continuity). Suppose Assumption 5 holds. Let \(\alpha\in(0,1]\) satisfy \(\alpha\le \alpha_r\) and \(\gamma \ell_f^\alpha<1\), and define \[\ell_\alpha := \frac{\ell_r^{\alpha/\alpha_r}(2r_\vee)^{1-\alpha/\alpha_r}}{1-\gamma \ell_f^\alpha}.\] Then \(V^*\) and \(Q^*\) as defined in 3 are bounded and \(\alpha\)-Hölder continuous with \([V^*]_{\alpha,\mathbb{X}}\le \ell_\alpha\) and \([Q^*]_{\alpha,\mathbb{Z}}\le \ell_\alpha.\) Moreover, 4 holds; i.e. \(V^*(x)=\max_{a\in\mathbb{A}}Q^*(x,a)\) for all \(x\in\mathbb{X}\).
Applying Theorem 4 to empirical measures supported on finitely many data points yields the following corollary.
Corollary 1. Fix \(n\ge 1\) and \(\omega\in\Omega\). Suppose Assumption 5 holds with the law of \(W\) taken as \(\psi\), \(\psi_n^V(\omega,\cdot)\), and \(\psi_n^Q(\omega,\cdot).\) Then the assertions in Assumption 1 hold.
Proof of Corollary 1. Applying Theorem 4 with the population measure \(\psi\) yields that \(V^*\in C_b(\mathbb{X})\), \(Q^*\in C_b(\mathbb{Z})\), and \(V^*(x)=\max_{a\in\mathbb{A}}Q^*(x,a)\) for all \(x\in\mathbb{X}\).
Next, applying Theorem 4 with \(\psi\) replaced by \(\psi_n^V(\omega,\cdot)\) shows that \(\widehat V_n(\omega,\cdot)\in C_b(\mathbb{X})\), since the Bellman equation in that theorem is precisely 36 .
It remains to verify the corresponding statement in Assumption 1 for \(\widehat Q_n(\omega,\cdot)\).
Let \(z_k\to z\) in \(\mathbb{Z}\). Since Assumption 5 holds with reference measure \(\psi_n^Q(\omega,\cdot)\), part (ii) implies that the map \(z\to E_n^Q[r(z,W)]\) is continuous on \(\mathbb{Z}\). Since \(\widehat V_n(\omega,\cdot)\in C_b(\mathbb{X})\), bounded convergence then implies that \[E_n^Q[\widehat V_n(\omega,f(z_k,W))]\to E_n^Q[\widehat V_n(\omega,f(z,W))].\] Therefore, by 37 , \(\widehat Q_n(\omega,\cdot)\) is continuous on \(\mathbb{Z}\).
Moreover, Assumption 5 (i) with reference measure \(\psi_n^Q(\omega,\cdot)\) implies that \(\sup_{z\in\mathbb{Z}}\left|E_n^Q[r(z,W)]\right|<\infty\). This, together with the boundedness of \(\widehat V_n(\omega,\cdot)\), the continuity of \(\widehat Q_n\), and the definition in 37 , implies that \(\widehat Q_n(\omega,\cdot)\in C_b(\mathbb{Z})\).
This proves all the assertions in Assumption 1 regarding \(V^*\), \(Q^*\), and \(\widehat Q_n(\omega,\cdot)\). ◻
In this section, we establish sufficient conditions on the model primitives for Assumptions 1 and 2. Leveraging the regularity properties in the previous section, we turn to stochastic error bounds that serve as envelopes for the errors in Assumption 2. Before proving the main Theorem 5, we explain how Hölder regularity yields envelopes satisfying the moments conditions in Assumption 2. The key tool is the following empirical process bound for Hölder parametric classes. To streamline the discussion, we defer the proof to Appendix 9.2.
Proposition 4. Let \(\Theta\subset\mathbb{R}^d\) be compact and let \(g:\Theta\times\mathbb{W}\to\mathbb{R}\) be measurable. Assume that there exist measurable functions \(R,L:\mathbb{W}\to\mathbb{R}_+\) and \(\eta\in(0,1]\) such that \[|g(\theta,w)|\le R(w) \quad\text{and}\quad |g(\theta,w)-g(\theta',w)|\le L(w)|\theta-\theta'|^\eta\] for all \(\theta,\theta'\in\Theta\) and \(w\in\mathbb{W}\). In addition, assume that for every integer \(k\ge2\), \(E\left[ R(W)^k+L(W)^k \right]<\infty.\) Then, for every integer \(k\ge2\), the empirical process error \(Z_n:=\sup_{\theta\in\Theta}\left|(E_n-E)g(\theta,W)\right|\) satisfies \[E\left[ Z_n^k \right]\le \frac{C_{\mathrm{emp},k}}{n^{k/2}}\] for some finite constant \(C_{\mathrm{emp},k}\) depending only on \(\left( \Theta,\eta,k,E[R(W)^k],E[L(W)^k] \right)\).
Therefore, if \(V^*\) and \(\widehat V_n\) are Hölder continuous, then, conditional on \(\mathcal{F}_n^V\), the estimation error \(\|\widehat Q_n-Q^*\|\) can be viewed as the empirical process error over a Hölder parametric class indexed by \(z\in\mathbb{Z}\). The action-wise regularity follows from a similar but more involved argument applied to the corresponding ratio process. Motivated by this intuition, the main sufficient conditions we use are summarized in Assumption 6.
Assumption 6. Assume that the following properties hold
\(\mathbb{Z}= \mathbb{X}\times \mathbb{A}\subseteq\mathbb{R}^{d_\mathbb{X}+ d_\mathbb{A}}\) is compact.
There exists \(\ell_{P} \geq 0\) and \(\bar q\in[0,1]\), such that for all \(x\in \mathbb{X}\) and \(a,b\in \mathbb{A}\), \[d_{\mathrm{TV}}(P(\cdot|x,a),P(\cdot|x,b))\le \ell_{P}|a-b|^{\bar q}.\]
For some \(z_0\in\mathbb{Z}\), \(E[|r(z_0,W)|^k] < \infty\) for all integers \(k\geq 2\).
There exists \(\alpha_r\in(0,1]\) and a non-negative measurable function \(L_r:\mathbb{W}\rightarrow\mathbb{R}_+\) with \(E[L_r(W)^k] < \infty\) for all integers \(k\geq 2\), such that \(|r(z,w) - r(z',w)| \leq L_r(w)|z-z'|^{\alpha_r}\) for all \(z,z'\in\mathbb{Z}\).
There exists \(\ell_f\geq 0\) such that \(|f(z,w) - f(z',w)| \leq \ell_f|z-z'|\) for all \(z,z'\in\mathbb{Z}\).
Under these conditions on the model primitives, the abstract requirements on \(\widehat Q_n\) and \(Q^*\) used in the regret analysis can be verified directly from \(f\), \(r\), and \(\psi\). This is shown in the following theorem, whose proof is deferred to Appendix 9.3.
Theorem 5. Suppose Assumption 6 is in force. Then, for every \(\alpha\in(0,\alpha_r]\) such that \(\gamma\ell_f^\alpha<1\), both \(Q^*\) and \(\widehat Q_n(\omega,\cdot)\) are \(\alpha\)-Hölder continuous on \(\mathbb{Z}\). Consequently, Assumption 1 holds. Moreover, define \(\alpha^*:=\sup\{\alpha\in[0,\alpha_r]:\gamma\ell_f^\alpha<1\}\), then Assumption 2 holds for every exponent \(q\in[0,\bar q]\) and \(q < \alpha^*\).
In particular, as \(\alpha^* > 0\), Theorem 5 implies that if (ii) holds with \(\bar q > 0\), then the split-sample estimator satisfies Assumptions 2 with some \(q>0\). This implies a fast convergence rate for the regret of the greedy policy.
In Assumption 6, the smoothness and integrability conditions on the reward and dynamics are usually easy to verify. The nontrivial requirement is the total-variation regularity condition in the action, namely part (ii). This is also the key factor determining whether a fast convergence rate is possible from Theorem 5. We show that this condition holds broadly with \(\bar q=1\) in OR settings through two continuous-state, continuous-action examples: a multi-item lost-sales inventory control model and a dynamic service allocation problem.
We impose the following regularity condition on the exogenous noise, which may represent demand in the inventory problem or arriving workload in the service allocation problem. Assume that the noise distribution admits a density \(p\) on \(\mathbb{R}^{d_\mathbb{W}}\) such that for some \(\bar q\in(0,1]\) and \(\ell<\infty\), \[\label{eqn:cond95on95density} \left\|p(\cdot+h)-p\right\|_{L^1(\mathbb{R}^{d_\mathbb{W}})} \le \ell |h|^{\bar q}\tag{40}\] for all \(h\in\mathbb{R}^{d_\mathbb{W}}\). We note that this assumption permits arbitrary dependence across demand coordinates. In particular, it holds with \(\bar q=1\) when \(p\in BV(\mathbb{R}^{d_\mathbb{W}})\) has bounded variation; i.e., there exists a vector of finite measures \(\nu = (\nu_1,\dots,\nu_m)\) such that \(\int(\nabla\cdot\phi) d p_D = -\int \phi^\top d\nu_D\) for all \(\phi\in C_c^1\) that is continuously differentiable with compact support.
Indeed, we consider a \(C_c^\infty\) mollifier \(\rho_\epsilon\) that integrates to 1, supported on the ball with radius \(\epsilon\) centered at 0 (e.g., the bump function). Let \(p_\epsilon := p*\rho_\epsilon\) be the smoothed density. Then, differentiate w.r.t. \(x_i\), \[\partial_{i}p_\epsilon(x) = \int \partial_i \rho_\epsilon(x-y)p(dy) = \int \rho_\epsilon(x-y)\nu_i(dy) = \nu_i*\rho_\epsilon\] By the fundamental theorem of calculus, the smoothed density satisfies the estimate \[\begin{align}\left\|p_\epsilon(\cdot+h) - p_\epsilon\right\|_{L^1(\mathbb{R}^{d_\mathbb{W}})} &= \int \left|\int_0^1 h^\top\nabla p_\epsilon(x +th)\right| dx \\ &\leq |h| \left|\int \nu*\rho_\epsilon(x) dx\right|\\ &= |h|\left|\iint \rho_\epsilon(x-y)dx\nu(dy)\right|\\ &=|h||\nu|(\mathbb{R}^{d_\mathbb{W}}) \end{align}\] where \(|\nu|\) denotes the total variation measure, and the last equality follows from \(\rho_\epsilon(\cdot-y)\) integrates to 1. Since \(p\in L^1(\mathbb{R}^{d_\mathbb{W}})\), taking \(\epsilon\downarrow 0\) yields 40 .
We note that the Sobolev space \(W^{1,1}(\mathbb{R}^{d_\mathbb{W}})\subset BV(\mathbb{R}^{d_\mathbb{W}})\) contains a rich family of densities. Moreover, regular densities with jump discontinuities (e.g., uniforms on regular geometries such as cubes or spheres) usually also have bounded variation.
With this condition in mind, we look at the following examples.
Example 1. Consider a Markovian multi-item lost-sales inventory control problem with continuous inventory levels. The state space is \(\mathbb{X}=\left\{{(x_1,\dots,x_k)\in\mathbb{R}_+^k:\;0\le x_i\le b_i,\;i=1,\dots,k}\right\}\) where \(x_i\) and \(b_i\) denote the inventory level and storage capacity of item \(i\), respectively. A natural action space is \(\mathbb{A}=\left\{{(a_1,\dots,a_k)\in\mathbb{R}_+^k:\;0\le a_i\le b_i,\;i=1,\dots,k}\right\}\), where \(a_i\) is the amount of item \(i\) ordered and delivered at the beginning of the period. We assume no lead time between ordering and the arrival of replenishment inventory. Let \(X_t\) be the inventory level at the beginning of day \(t\), before the arrival of the replenishment order \(A_t\). Then, naturally, the inventory levels evolve as \[X_{t+1}=\left( \min\left\{{X_t+A_t,b}\right\}-D_{t+1} \right)_+,\] where the minimum and positive part are applied componentwise, and \(D_{t+1}\) denotes demand. The demand process \(\left\{{D_t\in\mathbb{R}_+^k:t\geq 1}\right\}\) is i.i.d., with possibly correlated components. Then the transition kernel is given by \(P(\cdot| x,a) =\text{Law}\left[ (\min\left\{{x+a,b}\right\}-D)_+ \right].\)
Now, assume that the distribution of \(D_t\) satisfies 40 . Since total variation is non-increasing under the pushforward mapping \((\cdot)_+\), \[\begin{align} d_{\mathrm{TV}}\left( P(\cdot| x,a), P(\cdot| x,a') \right) &\le d_{\mathrm{TV}}\left( \text{Law}\left( \min\left\{{x+a,b}\right\}-D \right), \text{Law}\left( \min\left\{{x+a',b}\right\}-D \right) \right) \\ &= \frac{1}{2} \int_{\mathbb{R}^m} \left| p\left( \min\left\{{x+a,b}\right\}-u \right) - p\left( \min\left\{{x+a',b}\right\}-u \right) \right| \,du \\ &\le \frac{\ell}{2}|\min\left\{{x+a,b}\right\}-\min\left\{{x+a',b}\right\}|^{\bar q}\\ &\leq \frac{\ell}{2}|a-a'|^{\bar q}, \end{align}\] where the last inequality follows from the fact that the \(\min\) is \(1\)-Lipschitz. Thus, Assumption 6 part (ii) holds with \(\ell_P=\ell/2\) and exponent \(\bar q\).
Example 2. Consider a workload formulation of a dynamic service allocation problem. We use the same state spaces \(\mathbb{X}=\left\{{(x_1,\dots,x_k)\in\mathbb{R}_+^k:\;0\leq x_i\leq b_i,\;i=1,\dots,k}\right\}\), where \(x_i\) and \(b_i\) denote the remaining workload, and buffer capacity of class \(i\), respectively. We consider an action space representing possible service-allocation vectors, \[\mathbb{A}=\left\{{(a_1,\dots,a_k)\in\mathbb{R}_+^k:\;\sum_{i=1}^k a_i\leq \zeta,\;0\leq a_i\leq b_i,\;i=1,\dots,k}\right\},\] where \(a_i\) denotes the service capacity allocated to class \(i\), and \(\zeta\) is the total available service capacity.
Let \(X_t\) denote the remaining workload vector at the beginning of period \(t\). During the period, a new workload vector \(\Xi_{t+1}\) arrives, and the controller allocates service capacity \(A_t\) across the \(k\) classes. The allocated service reduces the combined old and newly arrived workload, but the workload cannot become negative and is truncated by the finite buffer capacity. Thus, the workload evolves as \[X_{t+1}=\min\left\{{(X_t+\Xi_{t+1}-A_t)_+,b}\right\}.\] The arrival process \(\left\{{\Xi_t\in\mathbb{R}_+^m:t\ge 1}\right\}\) is assumed to be i.i.d., and the components of \(\Xi_t\) may be correlated. The transition kernel is thus given by \(P(\cdot| x,a) = \text{Law}(\min\left\{{(x+\Xi-a)_+,b}\right\}).\)
Now, assume that the distribution of \(\Xi_t\) satisfies 40 . By the same argument as in Example 1, \[\begin{align} d_{\mathrm{TV}}\left( P(\cdot| x,a), P(\cdot| x,a') \right) &\le d_{\mathrm{TV}}\left( \text{Law}\left( x+\Xi-a \right), \text{Law}\left( x+\Xi-a' \right) \right) \\ &= \frac{1}{2} \int_{\mathbb{R}^m} \left| p\left( u-x+a \right) - p\left( u-x+a' \right) \right| \,du \\ &\le \frac{\ell}{2}|a-a'|^{\bar q}. \end{align}\] Thus, Assumption 6 part (ii) holds with \(\ell_P=\ell/2\) and exponent \(\bar q\).
Remark 7. Both examples satisfy Assumption 6(ii) through the same mechanism. In both cases, for fixed \(x\), changing the action translates the exogenous noise distribution before applying a fixed measurable map. Thus, the desired action regularity follows from the \(L^1\) translation regularity of the density of the exogenous noise, as in 40 . This phenomenon extends beyond these two settings to many max-plus-linear systems [37], which commonly arise in OR applications. However, if the exogenous noise has discrete masses, then an arbitrarily small translation can induce a TV distance proportional to the mass, and the TV regularity may fail.
J. Blanchet gratefully acknowledges support from DoD through the grant ONR 1398311, also support from NSF via grants 2229012, 2312204, and 2403007 is gratefully acknowledged.
Lemma 4. Let \(X,Y\) be random variables. Let \(p,q\in[1,\infty]\) satisfy \(\frac{1}{p}+\frac{1}{q}\leq 1.\) Then \[\mathbb{E}\left[ \left|XY\right| \right] \le \mathbb{E}\left[ \left|X\right|^p \right]^{1/p} \mathbb{E}\left[ \left|Y\right|^q \right]^{1/q},\] with the usual convention that when \(p=\infty\) or \(q=\infty\), the corresponding factor is interpreted as the essential supremum.
Proof. Let \[r = \frac{1}{1-\frac{1}{p}-\frac{1}{q}}\ge 1\] and \(r = \infty\) if \(\frac{1}{p}+\frac{1}{q} = 1.\) Apply the three-factor Hölder inequality to the random variables \(\left|X\right|\), \(\left|Y\right|\), and \(1\) with exponents \(p,q,r\). Since \[\frac{1}{p}+\frac{1}{q}+\frac{1}{r}=1,\] we obtain \[\mathbb{E}\left|XY\right| = \mathbb{E}\left[ \left|X\right|\left|Y\right|\cdot 1 \right] \le \mathbb{E}\left[ \left|X\right|^p \right]^{1/p} \mathbb{E}\left[ \left|Y\right|^q \right]^{1/q} \mathbb{E}\left[ 1^r \right]^{1/r}.\] Hence, \[\mathbb{E}{\left|XY\right|} \le \mathbb{E}\left[ \left|X\right|^p \right]^{1/p} \mathbb{E}\left[ \left|Y\right|^q \right]^{1/q}.\] ◻
This section collects proofs of auxiliary lemmas used in the proof of Theorem 2.
Proof. Fix \(\alpha\ge 1/m\) and \(u>0\), \(v>0\). Define the threshold \[s := \left( \frac{v}{2u} \right)^{1/\alpha} \qquad\text{and hence}\qquad v s^{-\alpha}=2u.\] Write \[\label{eqn:tu95min95sep95bd}\mathbb{E}\left[ \min\left\{{2u,\;vG^{-\alpha}}\right\} \right] = 2u \mathbb{P}(G\le s) + v\mathbb{E}\left[ G^{-\alpha}\mathbb{1}\{G>s\} \right],\tag{41}\] where \(G^{-\alpha}=+\infty\) on \(\{G=0\}\).
If \(s\ge 1\), then \(v\ge 2u\) and \(G^{-\alpha}\mathbb{1}\{G>s\} \leq \mathbb{1}\{G>s\}\). So, 41 implies that \(\mathbb{E}\left[ \min\left\{{2u,\;vG^{-\alpha}}\right\} \right]\leq v\) when \(s\ge 1\). Since both stated upper bounds in Lemma 1 dominate \(v\), it suffices to treat the case \(s\in(0,1)\).
Assume now \(s\in(0,1)\). By assumption, the first term satisfies \[\label{eqn:tu95min95sep95uPG95bd} 2u \mathbb{P}(G\le s)\le 2Mu s^{1/m}.\tag{42}\]
For the second term, use the tail integral identity: \[\label{eqn:tu95EG95as95int95bd} \begin{align} \mathbb{E}\left[ G^{-\alpha}\mathbb{1}\{G>s\} \right] &= \int_0^\infty \mathbb{P}\left( G^{-\alpha}\mathbb{1}\left\{{G>s}\right\}> t \right) dt\\ &=\int_0^\infty \mathbb{P}\left( s<G < t^{-1/\alpha} \right) dt\\ &\leq 1 + \int_1^ {s^{-\alpha}} \mathbb{P}\left( s<G < t^{-1/\alpha} \right) dt \end{align}\tag{43}\] where the contribution to the integral from \(t\in(0,1)\) is at most 1, and when \(t \geq s^{-\alpha}\), \(t^{-1/\alpha}\leq s\), leading to a 0 integrand. For \(t\in(1,s^{-\alpha})\), we have \(t^{-1/\alpha}\in(s,1)\). Hence, by assumption, \[\label{eqn:tu95prob95int95bd} \int_1^{s^{-\alpha}} \mathbb{P}\left( s<G<t^{-1/\alpha} \right) dt \le M\int_1^{s^{-\alpha}} t^{-1/(m\alpha)} dt.\tag{44}\] Using this bound, we now conclude separately for \(\alpha>1/m\) and \(\alpha = 1/m\).
In this case, \(1/(m\alpha)\in(0,1)\) and 44 is bounded by \[M\int_1^{s^{-\alpha}} t^{-1/(m\alpha)} dt = \frac{Mm\alpha}{m\alpha-1}\left( s^{1/m-\alpha}-1 \right) \leq C s^{1/m-\alpha},\] where \(C<\infty\) depending only on \((M,m,\alpha)\). Therefore, from 43 , \[v\mathbb{E}[G^{-\alpha}\mathbb{1}\{G>s\}] \le v + C v s^{1/m-\alpha} = v + C u^{1-1/(m\alpha)}v^{1/(m\alpha)}.\]
Moreover, from 42 , \[2u \mathbb{P}(G\le s)\le 2Mu s^{1/m} = 2M 2^{-1/(m\alpha)}u^{1-1/(m\alpha)}v^{1/(m\alpha)}\] matching the power of the expectation term.
Therefore, these bounds and 41 together implies Lemma 1 (i).
In this case, the integral in 44 is \[M\int_1^{s^{-\alpha}} t^{-1/(m\alpha)} dt = M\int_1^{s^{-m}} t^{-1} dt = Mm\log(s^{-1}).\] Since \(s=(v/(2u))^m < 1\), we have \(\log(s^{-1})=\log(2u/v)\), and therefore \[v\mathbb{E}[G^{-1/m}\mathbb{1}\{G>s\}] \le v + Mm v\log\left( \frac{2u}{v} \right).\] Moreover, noting that when \(s < 1\) \[\log\left( \frac{2u}{v} \right)= \max\left\{{0, \log\left( \frac{2u}{v} \right)}\right\},\]
Now, 42 implies that \(2u \mathbb{P}(G\le s)\le 2Mu s^{1/m}=Mv\). These bounds together gives Lemma 1 (ii). ◻
Proof. To simplify notation, write \[\log_+(x):=\max\left\{{0, \log x}\right\}\] for all \(x > 0\). For \(n\geq 2\), let \[\theta_n:=\frac{1}{1+\log n}\in(0,1).\] For any \(x>0\) and any \(\theta>0\), we have \[\log_+(x)\le \frac{x^\theta}{\theta}.\] Indeed, this is trivial when \(x\le 1\). For \(x>1\), \(d_x\log(x) = x^{-1} \leq d_x(x^\theta/\theta) = x^{\theta-1}\) and \(\log(1)= 0 < 1/\theta\). So, \(\log x\le x^\theta/\theta\) when \(x>1\).
Applying this with \(x=2\delta_n/\Lambda_n(q)^\beta > 0\) and \(\theta=\theta_n\), we get \[\Lambda_n(q)^\beta \log_+\left( \frac{2\delta_n}{\Lambda_n(q)^\beta} \right) \le \frac{1}{\theta_n}\Lambda_n(q)^\beta \left( \frac{2\delta_n}{\Lambda_n(q)^\beta} \right)^{\theta_n} = \frac{2^{\theta_n}}{\theta_n}\delta_n^{\theta_n}\Lambda_n(q)^{\beta(1-\theta_n)}.\] Therefore \[\label{eqn:critical95log95reduce95to95mixed95moment} \mathbb{E}\left[ \Lambda_n(q)^\beta \log_+\left( \frac{2\delta_n}{\Lambda_n(q)^\beta} \right) \right] \le \frac{2^{\theta_n}}{\theta_n} \mathbb{E}\left[ \delta_n^{\theta_n}\Lambda_n(q)^{\beta(1-\theta_n)} \right].\tag{45}\]
Now set \[p_n:=\frac{2}{\theta_n}, \qquad q_n:=\frac{k_\beta}{\beta(1-\theta_n)}.\] Since \(k_\beta=\left\lceil{\beta+1}\right\rceil>\beta\) and \(\theta_n\in(0,1)\), \[\frac{1}{p_n}+\frac{1}{q_n} = \frac{\theta_n}{2}+\frac{\beta(1-\theta_n)}{k_\beta} = \frac{\beta}{k_\beta} + \theta_n\left( \frac{1}{2}-\frac{\beta}{k_\beta} \right) <1.\] Hence, the generalized Hölder inequality in Lemma 4 gives \[\mathbb{E}\left[ \delta_n^{\theta_n}\Lambda_n(q)^{\beta(1-\theta_n)} \right] = \mathbb{E}\left[ \delta_n^{2/p_n}\Lambda_n(q)^{k_\beta/q_n} \right] \le \mathbb{E}\left[ \delta_n^2 \right]^{1/p_n} \mathbb{E}\left[ \Lambda_n(q)^{k_\beta} \right]^{1/q_n}.\] Therefore, by Assumption 2, \[\label{eqn:tu95delta95Lambda95moment95bd} \mathbb{E}\left[ \delta_n^{\theta_n}\Lambda_n(q)^{\beta(1-\theta_n)} \right] \le C n^{-\theta_n/2}n^{-\beta(1-\theta_n)/2} = C n^{-\beta/2}n^{(\beta-1)\theta_n/2},\tag{46}\] where \(C<\infty\) depends only on \((\beta,C_\delta,C_{\Lambda,k_\beta})\).
Since \[\theta_n\log n=\frac{\log n}{1+\log n}\le 1,\] we have \[n^{(\beta-1)\theta_n/2} = \exp\left( \frac{\beta-1}{2}\theta_n\log n \right) \le \exp\left( \frac{\beta-1}{2} \right).\] Also, \(2^{\theta_n}\le 2\) and \[\frac{1}{\theta_n}=1+\log n \leq 2\log 2+\log n\le 3\log n, \qquad n\ge 2.\] Substituting these bounds into 46 and 45 , we obtain \[\begin{align} \mathbb{E}\left[ \Lambda_n(q)^\beta\log_+\left( \frac{2\delta_n}{\Lambda_n(q)^\beta} \right) \right] &\le C \frac{2^{\theta_n}}{\theta_n} n^{-\beta/2}n^{(\beta-1)\theta_n/2}\\ &\leq 6e^{(\beta-1)/2}C n^{-\beta/2}\log n \end{align}\] for all \(n\ge 2\). This proves Lemma 2 ◻
Proof. When \(\alpha = 0\), Lemma 3 holds trivially. For \(\alpha\in(0,1/m)\), using the tail integral identity as in 43 and the assumption on \(G\), we get \[\begin{align} \mathbb{E}\left[ G^{-\alpha}\mathbb{1}\{G>0\} \right] &\le 1 + \int_1^\infty \mathbb{P}(0<G<t^{-1/\alpha}) dt.\\ &\leq 1+M\int_1^\infty t^{-1/(m\alpha)} dt \\ &=1+\frac{Mm\alpha}{1-m\alpha}. \end{align}\] ◻
Proof. The proof is structured as follows. First, we show that for each fixed \(\theta\in\Theta\), \(m > 0\), \(p>q\ge 0\), and \(\dagger\in\left\{{+,-}\right\}\), there exist adapted Q-estimators \(\left\{{\widehat Q_n:n\ge 1}\right\}\) satisfying Assumption 2 with \(Q^*\) replaced by \(Q_\theta^\dagger\). Second, we establish the lower bounds 33 and 34 .
Fix \(\theta\in\Theta=[-1,1]\) and \(\dagger\in\left\{{+,-}\right\}\). We work on the canonical space \((\Omega=\mathbb{W}^{\mathbb{N}},\mathcal{F}=\mathcal{B}(\mathbb{W})^{\mathbb{N}},P_\theta^\dagger:=(\psi_\theta^\dagger)^{ \mathbb{N}})\), where \(\psi_\theta^+\) and \(\psi_\theta^-\) are defined in 19 and 21 , respectively, and \(\mathbb{N}\) is the set of positive integers.
Define the sequence \(\left\{{W_i=(Y_i,D_i):i=1,2,\dots}\right\}\) by the coordinate projection mapping \(W_i(\omega) = \omega_i = (y_i,d_i)\in \mathbb{W}\). Let \(\mathcal{D}_n = \sigma\left\{{W_i:i=1,\dots,n}\right\}\). Thus, under \(P_\theta^\dagger\), \(\left\{{W_i:i\in\mathbb{N}}\right\}\) are i.i.d. with common law \(\psi_\theta^\dagger\).
Define the empirical means \[\bar Y_n:=\frac{1}{n}\sum_{i=1}^n Y_i,\quad\text{and}\quad \bar D_n:=\frac{1}{n}\sum_{i=1}^n D_i.\] By construction, \(\bar Y_n\) and \(\bar D_n\) are \(\mathcal{D}_n\)-measurable, and \(\bar D_n=d_\theta^\dagger\) a.s.\(P_\theta^\dagger\) for all \(n\geq 1\), where \(d_\theta^\dagger\) is defined in 19 and 21 .
We now define the adapted plug-in estimators. For the \(+\) family, let \[\label{eqn:minimax95lb95Qhat95plus} \widehat Q_n^+(x,a) := \begin{cases} x^m h_p(a)+\bar Y_n\mathbb{1}\left\{{x\le \bar D_n}\right\}\left( 1-h_p(a) \right), & x\in[0,1],\\ 0, & x=2, \end{cases}\tag{47}\] where \(h_p\) is defined in 18 . For the \(-\) family, let \[\label{eqn:minimax95lb95Qhat95minus} \widehat Q_n^-(x,a) := \begin{cases} \bar Y_n\,\mathrm{sign}(a)\left( |a|^q\wedge \bar D_n^q \right)-\big||a|-\bar D_n\big|^p, & x\in[0,1],\\ 0, & x=2. \end{cases}\tag{48}\] Both \(\widehat Q_n^+\) and \(\widehat Q_n^-\) are \(\mathcal{D}_n\)-adapted Q-estimation algorithms in the sense of the preceding definition. Also, for each fixed \(\omega\) and \(x\), the maps \(a\to \widehat Q_n^\dagger(\omega,x,a)\) are continuous on \(\mathbb{A}\).
We note that since \(Y_i\in\left\{{-1,1}\right\}\) and \(E_\theta[Y_i]=\theta\) under either family, \(\bar Y_n-\theta\) is centered and sub-Gaussian with variance proxy \(1/n\). Therefore, by standard sub-Gaussian moment bounds (see, e.g., [38]), for every integer \(k\ge 2\), there exists a constant \(C_k<\infty\), depending only on \(k\), such that \[\label{eqn:tu95subgaussian95moments} E_\theta\left[ |\bar Y_n-\theta|^k \right]\le C_k n^{-k/2}, \qquad k\ge 2.\tag{49}\]
We proceed with the proof by considering the \(+\) and \(-\) families separately.
Since \(\bar D_n=d_\theta^+\) a.s.\(P_\theta^+\), 47 and 20 give \[\widehat Q_n^+(x,a)-Q_\theta^+(x,a) = (\bar Y_n-\theta)\mathbb{1}\left\{{x\le d_\theta^+}\right\}\left( 1-h_p(a) \right),\] for all \((x,a)\in \mathbb{Z}\) a.s.\(P_\theta^+\). Since \(h_p(a)\in[0,1]\) for all \(a\in\mathbb{A}\), \[\label{eqn:tu95ub95Qtheta4395delta} \sup_{z\in\mathbb{Z}}\left|\widehat Q_n^+(z)-Q_\theta^+(z)\right| \le \left|\bar Y_n-\theta\right|, \quad \text{a.s.P_\theta^+.}\tag{50}\]
Next, fix \(x\in\mathbb{X}\) and \(a\neq b\). Then \[\begin{align} &\frac{\left|\left( \widehat Q_n^+(x,a)-Q_\theta^+(x,a) \right)-\left( \widehat Q_n^+(x,b)-Q_\theta^+(x,b) \right)\right|}{|a-b|^q}= \left|\bar Y_n-\theta\right|\mathbb{1}\left\{{x\le d_\theta^+}\right\} \frac{\left|h_p(a)-h_p(b)\right|}{|a-b|^q}. \end{align}\] If \(q=0\), then the last quotient is bounded by \(2\). If \(q\in(0,1]\), then \[h_p(a)=\frac{(1+a)^p}{(1+a)^p+(1-a)^p},\] the denominator is bounded away from \(0\) on \([-1,1]\). Recall that \(p>q\), the maps \(a\rightarrow(1+a)^p\) and \(a\rightarrow(1-a)^p\) are \(q\)-Hölder on \([-1,1]\). Hence there exists \(0 <\ell_{p,q}^+ < \infty\), depending only on \((p,q)\), such that for all \(a,b\in[-1,1]\) \[|h_p(a)-h_p(b)|\le \ell_{p,q}^+|a-b|^q.\] Consequently, \[\label{eqn:tu95ub95Qtheta4395Lambda} \sup_{x\in\mathbb{X}}\sup_{a\neq b} \frac{\left|\left( \widehat Q_n^+(x,a)-Q_\theta^+(x,a) \right)-\left( \widehat Q_n^+(x,b)-Q_\theta^+(x,b) \right)\right|}{|a-b|^q} \le (\ell_{p,q}^+\vee 2)\left|\bar Y_n-\theta\right|, \qquad \text{a.s.P_\theta^+.}\tag{51}\]
Thus, in view of 50 and 51 , we define \[\delta_n^+:=\left|\bar Y_n-\theta\right|+n^{-17} \quad\text{and}\quad \Lambda_n^+(q):=(\ell_{p,q}^+\vee 2)\left|\bar Y_n-\theta\right|+n^{-17}.\] Applying 49 , we conclude that Assumption 2 holds for the \(+\) family with positive measurable envelopes \(\delta_n^+\) and \(\Lambda_n^+(q)\).
Fix \(n\ge 1\) and let \(\hat{\pi}_n\in \mathrm{PLA}_n\) be an arbitrary adapted policy learning algorithm. Since \(\hat{\pi}_n\) is \(\mathcal{D}_n\)-adapted and \(\mathcal{D}_n=\sigma\left\{{W_1,\dots,W_n}\right\}\), by the Doob–Dynkin lemma we may identify \(\hat{\pi}_n\) with a measurable map in \(m\left\{{\mathcal{W}^n\times\mathcal{X}\rightarrow\mathcal{A}}\right\}\), and we suppress the dependence on \(w_1,\dots,w_n\) in the notation below.
To simplify notation, let \[\Psi_{\theta}^n(d\mathbf{w}_n) :=\Psi_{\theta}^n(dw_1,\dots,dw_n):=\psi_\theta^+(dw_1)\psi_\theta^+(dw_2)\dots\psi_\theta^+(dw_n);\] i.e. \(\Psi^n_\theta\) is the law of \(W_1,\dots,W_n\) under \(P_\theta^+\).
We consider \(\theta = \pm\,\xi\) where \[\xi:=\frac{1}{4\sqrt n},\quad \text{and recall that}\quad d_\xi^+=\left( \frac{\xi}{2} \right)^{1/m}.\] We consider the following \(\mathcal{D}_n\) measurable random variable on \((\Omega,\mathcal{F})\) \[\label{eqn:tu95def95L95n9543} \widehat L_n := \int_{[0,d_\xi^+]} h_p\left( \hat{\pi}_n(x) \right)\mu(dx);\tag{52}\] where the \(\omega\) dependence comes only from \(\hat{\pi}_n\). Since \(\mu\) is the uniform distribution on \([0,1]\) and \(0\leq h_p\leq 1\) \[\label{eqn:tu95Ln95bd} 0\le \widehat L_n\le \mu\left( [0,d_\xi^+] \right)=d_\xi^+.\tag{53}\]
Recall from 32 that for \(\theta = \pm \xi\), \[\mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_\theta^+ \right) = \int_{[0,1]}\left( V_\theta^+(x)-Q_\theta^+\left( x,\hat{\pi}_n(x) \right) \right)\mu(dx).\]
Consider first the instance \(\mathcal{M}_{\xi}^+\). If \(x\in[0,d_\xi^+]\), then \(x^m\le (d_\xi^+)^m=\xi/2\). Moreover, by 24 , the optimal action set for \(x\in[0,d_\xi^+]\) is \(\left\{{-1}\right\}\). Thus, \[Q_{\xi}^+(x,-1)-Q_{\xi}^+(x,a) = (\xi-x^m)h_p(a) \ge \frac{\xi}{2}h_p(a),\] for all \(a\in \mathbb{A}\). By the non-negativity of \(V_\theta^+(x) - Q_\theta^+(x,a)\), integrating over \(x\in[0,d_\xi^+]\) gives \[\mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{\xi}^+ \right) \ge \int_{[0,d_\xi^+]}\left( Q_{\xi}^+(x,-1)-Q_\xi^+\left( x,\hat{\pi}_n(x) \right) \right)\mu(dx) \ge \frac{\xi}{2}\widehat L_n.\] Hence, identifying \(\hat{\pi}_n\) with a measurable function in \(m\left\{{\mathcal{W}^n\times\mathcal{X}\rightarrow\mathcal{A}}\right\}\) and inducing the measurability of \(\widehat L_n\) from 52 , we have \[\label{eqn:tu954395reg9543delta} E_\xi\left[ \mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{\xi}^+ \right) \right] = \int_{\mathbb{W}^n}\mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{\xi}^+ \right)\Psi^{n}_\xi(d\mathbf{w}_n) \ge \frac{\xi}{2}\int_{\mathbb{W}^n}\widehat L_n\Psi^{n}_\xi(d\mathbf{w}_n).\tag{54}\]
Now consider the instance \(\mathcal{M}_{-\xi}^+\). Again by 24 , the optimal action on \([0,d_\xi^+]\) is \(1\), and \[Q_{-\xi}^+(x,1)-Q_{-\xi}^+(x,a) = (x^m+\xi)\left( 1-h_p(a) \right) \ge \frac{\xi}{2}\left( 1-h_p(a) \right)\] for all \(x\in[0,d_\xi^+]\), and \(a\in\mathbb{A}\). Therefore \[\mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{-\xi}^+ \right) \ge \frac{\xi}{2}\int_{[0,d_\xi^+]}\left( 1-h_p\left( \hat{\pi}_n(x) \right) \right)\,\mu(dx) = \frac{\xi}{2}\left( d_\xi^+-\widehat L_n \right).\] We take expectations on both sides and rewrite using the law of \(W_1,\dots,W_n\) to get \[\label{eqn:tu954395reg95-delta} E_{-\xi}\left[ \mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{-\xi}^+ \right) \right] \ge \frac{\xi}{2}\left( d_\xi^+-\int_{\mathbb{W}^n}\widehat L_n\Psi^{n}_{-\xi}(d\mathbf{w}_n) \right).\tag{55}\]
Note that \(\max\{a,b\}\geq \frac{1}{2}(a+b)\). Taking the maximum of 54 and 55 yields \[\label{eqn:tu954395reg95tv95bd} \begin{align} \max_{\theta \in\left\{{\xi,-\xi}\right\}} E_{\theta}\left[ \mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{\theta}^+ \right) \right]&\ge \frac{\xi}{4}\left( d_\xi^+ + \int_{\mathbb{W}^n}\widehat L_n\Psi^{n}_\xi(d\mathbf{w}_n)-\int_{\mathbb{W}^n}\widehat L_n\Psi^{n}_{-\xi}(d\mathbf{w}_n) \right)\\ &= \frac{\xi}{4}\left( d_\xi^+ - \int_{\mathbb{W}^n}\widehat L_n[\Psi^{n}_{-\xi}-\Psi^{n}_\xi](d\mathbf{w}_n) \right)\\ &\geq \frac{\xi}{4}d_\xi^+\left( 1 - d_{\mathrm{TV}}\left( \Psi^{n}_\xi,\Psi^{n}_{-\xi} \right) \right) \end{align}\tag{56}\] where \(d_{\mathrm{TV}}\) denotes the total variation distance and the last inequality uses 53 and \(\int f(d\mu-d\nu)\leq \left\|f\right\| d_{\mathrm{TV}}(\mu,\nu)\) for bounded function \(f\) and probability measures \(\mu\) and \(\nu\).
We now bound the total variation distance by the Kullback–Leibler (KL) divergence. By Pinsker’s inequality, \[\label{eqn:tu954395tv95kl} d_{\mathrm{TV}}\left( \Psi^{n}_\xi,\Psi^{n}_{-\xi} \right) \le \sqrt{\frac{1}{2}\mathrm{KL}\left( \Psi^{n}_\xi\middle\|\Psi^{n}_{-\xi} \right)}.\tag{57}\] Since under \(\psi_\xi^+\) and \(\psi_{-\xi}^+\) the law of \(D\) is the same deterministic value \(d_\xi^+\), only the law for \(Y\) differs. Hence, by the property of the KL divergence for product measures, \[\begin{align} \mathrm{KL}\left( \Psi^{n}_\xi\,\middle\|\,\Psi^{n}_{-\xi} \right) &= n\mathrm{KL}\left( \psi_{\xi}^+\,\middle\|\,\psi_{-\xi}^+ \right)\\ &= n\left[ \frac{1+\xi}{2}\log\frac{1+\xi}{1-\xi}+\frac{1-\xi}{2}\log\frac{1-\xi}{1+\xi} \right]\\ &=n\left[ \frac{1+\xi}{2}-\frac{1-\xi}{2} \right] \log\frac{1+\xi}{1-\xi} \\ &= n\xi\log\frac{1+\xi}{1-\xi}. \end{align}\]
Since \(\xi\le 1/4\), \[\log\frac{1+\xi}{1-\xi} = \log\left( 1+\frac{2\xi}{1-\xi} \right) \le \frac{2\xi}{1-\xi} \le 4\xi.\] Therefore, \[\label{eqn:tu95KL95ub} \mathrm{KL}\left( \Psi^{n}_\xi\,\middle\|\,\Psi^{n}_{-\xi} \right) \le 4n\xi^2=\frac{1}{4}.\tag{58}\] Combining this with 57 , we obtain \(d_{\mathrm{TV}}\left( \Psi^{n}_\xi,\Psi^{n}_{-\xi} \right) \le1/\sqrt 8\leq 1/2.\) Substituting this bound into 56 yields \[\max_{\theta \in\left\{{\xi,-\xi}\right\}} E_{\theta}\left[ \mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{\theta}^+ \right) \right] \ge \frac{\xi d_\xi^+}{8}.\]
Finally, recalling the choice \(\xi = 1/(4\sqrt n)\) and the definition of \(d_\xi^+\), we obtain \[\frac{\xi d_\xi^+}{8} = \frac{1}{8}\xi\left( \frac{\xi}{2} \right)^{1/m} = 2^{-5-3/m}n^{-(m+1)/(2m)}.\] Therefore, for every \(\hat{\pi}_n\in \mathrm{PLA}_n\), \[\max_{\theta\in\Theta} E_{\theta}\left[ \mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{\theta}^+ \right) \right] \ge\max_{\theta \in\left\{{\xi,-\xi}\right\}} E_{\theta}\left[ \mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{\theta}^+ \right) \right]\ge 2^{-5-3/m}n^{-(m+1)/(2m)}.\] Taking the infimum over \(\hat{\pi}_n\in\mathrm{PLA}_n\) yields 33 .
Since \(\bar D_n=d_\theta^-\) a.s.\(P_\theta^-\), 48 and 22 give \[\widehat Q_n^-(x,a)-Q_\theta^-(x,a) = (\bar Y_n-\theta)\mathrm{sign}(a)\left( |a|^q\wedge (d_\theta^-)^q \right),\] for all \((x,a)\in \mathbb{Z}\) a.s.\(P_\theta^-\). Recall that \(d_\theta^- = |\theta|^{1/(p-q)}\le 1\). Hence, \[\label{eqn:tu95ub95Qtheta-95delta} \sup_{z\in\mathbb{Z}}\left|\widehat Q_n^-(z)-Q_\theta^-(z)\right| \le \left|\bar Y_n-\theta\right|, \quad \text{a.s.P_\theta^-.}\tag{59}\]
Next, fix \(x\in\mathbb{X}\) and \(a\neq b\). Then \[\begin{align} &\frac{\left|\left( \widehat Q_n^-(x,a)-Q_\theta^-(x,a) \right)-\left( \widehat Q_n^-(x,b)-Q_\theta^-(x,b) \right)\right|}{|a-b|^q} = \left|\bar Y_n-\theta\right| \frac{\left|\mathrm{sign}(a)\left( |a|^q\wedge (d_\theta^-)^q \right)-\mathrm{sign}(b)\left( |b|^q\wedge (d_\theta^-)^q \right)\right|}{|a-b|^q}. \end{align}\] If \(q=0\), then the last quotient is bounded by \(2\). If \(q\in(0,1]\), we apply the following lemma, whose proof is deferred to Appendix 8.1.
Lemma 5. Let \(q\in(0,1]\). Then for all \(a,b\in[-1,1]\), \[\bigl|\mathrm{sign}(a)|a|^q-\mathrm{sign}(b)|b|^q\bigr| \le 2^{1-q}|a-b|^q.\]
Moreover, \(\mathrm{sign}(a)\left( |a|^q\wedge (d_\theta^-)^q \right)\) clips \(\mathrm{sign}(a)|a|^q\) within the interval \(\left[ -(d_\theta^-)^q,(d_\theta^-)^q \right]\) and clipping operation is \(1\)-Lipschitz. This, combined with Lemma 5, leads to \[\left|\mathrm{sign}(a)\left( |a|^q\wedge (d_\theta^-)^q \right)-\mathrm{sign}(b)\left( |b|^q\wedge (d_\theta^-)^q \right)\right| \le 2^{1-q}|a-b|^q \le 2|a-b|^q.\] Consequently, \[\label{eqn:tu95ub95Qtheta-95Lambda} \sup_{x\in\mathbb{X}}\sup_{a\neq b} \frac{\left|\left( \widehat Q_n^-(x,a)-Q_\theta^-(x,a) \right)-\left( \widehat Q_n^-(x,b)-Q_\theta^-(x,b) \right)\right|}{|a-b|^q} \le 2\left|\bar Y_n-\theta\right|, \quad \text{a.s.P_\theta^-.}\tag{60}\]
Thus, in view of 59 and 60 , we define \[\delta_n^-:=\left|\bar Y_n-\theta\right|+n^{-17} \quad\text{and}\quad \Lambda_n^-(q):=2\left|\bar Y_n-\theta\right|+n^{-17}.\] Applying 49 , we conclude that Assumption 2 holds for the \(-\) family with positive measurable envelopes \(\delta_n^-\) and \(\Lambda_n^-(q)\).
Fix \(n\ge 1\) and let \(\hat{\pi}_n\in \mathrm{PLA}_n\) be an arbitrary adapted policy learning algorithm. As in the \(+\) case, we identify \(\hat{\pi}_n\) with a measurable map in \(m\left\{{\mathcal{W}^n\times\mathcal{X}\rightarrow\mathcal{A}}\right\}\).
We override the notation and define \[\Psi_{\theta}^n(d\mathbf{w}_n):=\Psi_{\theta}^n(dw_1,\dots,dw_n):=\psi_\theta^-(dw_1)\psi_\theta^-(dw_2)\dots\psi_\theta^-(dw_n);\] i.e. \(\Psi^n_\theta\) is the law of \(W_1,\dots,W_n\) under \(P_\theta^-\).
We consider the same choice \(\theta=\pm\;\xi\) where \(\xi:=1/(4\sqrt{n})\) and recall that \(d_\xi^-:=\xi^{1/(p-q)}.\) We consider the following \(\mathcal{D}_n\) measurable random variable on \((\Omega,\mathcal{F})\): \[\label{eqn:tu95def95S95n95-} \widehat S_n := \mu\left( \left\{{x\in[0,1]:\hat{\pi}_n(x)\ge 0}\right\} \right).\tag{61}\] Since \(\mu\) is a probability measure on \([0,1]\), \(\widehat S_n\in[0,1]\).
Consider first the instance \(\mathcal{M}_{\xi}^-\). By 28 , \[\mathbb{A}_\xi^-(x)=\left\{{d_\xi^-}\right\} \quad\text{and}\quad V_\xi^-(x)=\xi(d_\xi^-)^q=(d_\xi^-)^p\] for \(x\in[0,1]\). If \(\hat{\pi}_n(x)<0\), then 22 gives \[Q_{\xi}^-\left( x,\hat{\pi}_n(x) \right) = \xi\,\mathrm{sign}(\hat{\pi}_n(x))\left( |\hat{\pi}_n(x)|^q\wedge (d_\xi^-)^q \right) - \big||\hat{\pi}_n(x)|-d_\xi^-\big|^p \le 0.\] Moreover, \(V_\xi^-(x)-Q_\xi^-(x,a)\ge 0\) for all \(x\in\mathbb{X}\) and \(a\in\mathbb{A}\). So, we must have \[V_{\xi}^-(x)-Q_{\xi}^-\left( x,\hat{\pi}_n(x) \right) \ge (d_\xi^-)^p\mathbb{1}\left\{{\hat{\pi}_n(x)<0}\right\},\] and integrating over \(x\) yields \[\label{eqn:tu95-95reg9543delta} \mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{\xi}^- \right) \ge (d_\xi^-)^p\mu\left( \left\{{x\in[0,1]:\hat{\pi}_n(x)<0}\right\} \right) = (d_\xi^-)^p(1-\widehat S_n).\tag{62}\]
Now consider the instance \(\mathcal{M}_{-\xi}^-\). Again by 28 , \[\mathbb{A}_{-\xi}^-(x)=\left\{{-d_\xi^-}\right\} \quad\text{and}\quad V_{-\xi}^-(x)=\xi(d_\xi^-)^q=(d_\xi^-)^p,\] for \(x\in[0,1]\). In this case, if \(\hat{\pi}_n(x)\ge 0\), then 22 gives \[Q_{-\xi}^-\left( x,\hat{\pi}_n(x) \right) = -\xi\left( |\hat{\pi}_n(x)|^q\wedge (d_\xi^-)^q \right) - \big||\hat{\pi}_n(x)|-d_\xi^-\big|^p \le 0.\] Therefore, the same reasoning as before implies that \[V_{-\xi}^-(x)-Q_{-\xi}^-\left( x,\hat{\pi}_n(x) \right) \ge (d_\xi^-)^p\mathbb{1}\left\{{\hat{\pi}_n(x)\ge 0}\right\}.\] Integrating over \(x\) yields \[\label{eqn:tu95-95reg95-delta} \mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{-\xi}^- \right) \ge (d_\xi^-)^p\widehat S_n.\tag{63}\]
Taking expectations using the law of \(W_1,\dots,W_n\) under \(E_\xi\) and \(E_{-\xi}\) respectively, we obtain \[\label{eqn:tu95-95reg95tv} \begin{align} \max_{\theta \in\left\{{\xi,-\xi}\right\}} E_{\theta}\left[ \mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{\theta}^- \right) \right] &\ge \frac{1}{2}\left( E_\xi\left[ \mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{\xi}^- \right) \right] + E_{-\xi}\left[ \mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{-\xi}^- \right) \right] \right)\\ &\stackrel{(i)}{\ge} \frac{1}{2}\left( \int_{\mathbb{W}^n}(d_\xi^-)^p(1-\widehat S_n) d\Psi_\xi^n + \int_{\mathbb{W}^n}(d_\xi^-)^p\widehat S_n d\Psi_{-\xi}^n \right)\\ &= \frac{(d_\xi^-)^p}{2}\left( 1- \int_{\mathbb{W}^n}\widehat S_n d[\Psi_\xi^n -\Psi_{-\xi}^n] \right)\\ &\geq \frac{(d_\xi^-)^p}{2}\left( 1-d_{\mathrm{TV}}\left( \Psi^{n}_{\xi},\Psi^{n}_{-\xi} \right) \right), \end{align}\tag{64}\] where \((i)\) applies 62 and 63 and the last inequality follows from \(\widehat S_n\in[0,1]\).
As in the \(+\) case, we can apply Pinsker’s inequality and obtain \[d_{\mathrm{TV}}\left( \Psi^{n}_{\xi},\Psi^{n}_{-\xi} \right) \leq \sqrt{\frac{1}{2}\mathrm{KL}\left( \Psi^{n}_{\xi}\,\middle\|\,\Psi^{n}_{-\xi} \right)}\leq \sqrt{\frac{1}{8}}< \frac{1}{2}.\] where the second inequality follows from the same calculation that arrives at 58 . Substituting this bound into 64 yields \[\max_{\theta \in\left\{{\xi,-\xi}\right\}} E_{\theta}\left[ \mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{\theta}^- \right) \right] \ge \frac{(d_\xi^-)^p}{4}= \frac{1}{4}\xi^{p/(p-q)} = 2^{-2-2p/(p-q)}n^{-p/(2(p-q))}.\]
Therefore, for every \(\hat{\pi}_n\in\mathrm{PLA}_n\), \[\max_{\theta\in\Theta} E_{\theta}\left[ \mathrm{Regret}\left( \hat{\pi}_n;\mathcal{M}_{\theta}^- \right) \right] \ge 2^{-2-2p/(p-q)}n^{-p/(2(p-q))}.\] Taking the infimum over \(\hat{\pi}_n\in\mathrm{PLA}_n\) yields 34 . ◻
Proof. We split into two cases.
If \(a\) and \(b\) have the same sign, then \[\left|\mathrm{sign}(a)|a|^q-\mathrm{sign}(b)|b|^q\right| = \left||a|^q-|b|^q\right|.\] Since \(q\in(0,1]\), the map \(t\rightarrow t^q\) is \(q\)-Hölder with coefficient \(q \le 1\) on \([0,\infty)\), so \[\bigl||a|^q-|b|^q\bigr|\le \bigl||a|-|b|\bigr|^q\le |a-b|^q.\]
Now suppose \(a\) and \(b\) have opposite signs. Then \[\left|\mathrm{sign}(a)|a|^q-\mathrm{sign}(b)|b|^q\right| = |a|^q+|b|^q.\] Because \(t\rightarrow t^q\) is concave on \([0,\infty)\), \[|a|^q+|b|^q\le 2^{1-q}(|a|+|b|)^q.\] Note that when \(a\) and \(b\) have opposite signs, \(|a|+|b|=|a-b|\), hence \[\left|\mathrm{sign}(a)|a|^q-\mathrm{sign}(b)|b|^q\right| \le 2^{1-q}|a-b|^q.\]
Combining the two cases proves the claim. ◻
Proof. For \(v\in C_b(\mathbb{X})\), define the Bellman operator \[\mathcal{T}v(x) := \max_{a\in\mathbb{A}} E[r(x,a,W)+\gamma v(f(x,a,W))], \qquad x\in\mathbb{X}.\] We first show that under Assumption 5, \(V^*\) is the unique fixed-point of \(\mathcal{T}\) in \(C_b(\mathbb{X})\).
By 38 , the map \(z\rightarrow E[r(z,W)]\) is continuous on \(\mathbb{Z}\). Also, if \(z_n\to z\) in \(\mathbb{Z}\), then 39 gives \[E|f(z_n,W)-f(z,W)|\to 0,\] so \(f(z_n,W)\to f(z,W)\) in probability. Hence, for every \(h\in C_b(\mathbb{X})\), since \(h\) is bounded and continuous, \(E[h(f(z_n,W))]\to E[h(f(z,W))].\) Thus, the induced transition kernel is weakly continuous.
Therefore, by standard dynamic programming results (see [39], the operator \(\mathcal{T}\) is a \(\gamma\)-contraction on \(C_b(\mathbb{X})\), and its unique fixed point is \(V^*\in C_b(\mathbb{X})\).
To proceed, we first show a simple inequality. Let \(s,t\ge 0\) and \(\theta\in[0,1]\). Then \[\label{eqn:pwr95bd95min} s\wedge t \le s^\theta t^{1-\theta}.\tag{65}\] Indeed, if \(s\le t\), then \(s^\theta t^{1-\theta}\ge s^\theta s^{1-\theta}=s=s\wedge t.\) If \(t\le s\), then \(s^\theta t^{1-\theta}\ge t^\theta t^{1-\theta}=t=s\wedge t.\) Thus in either case, \(s\wedge t \le s^\theta t^{1-\theta}.\)
With this result, we analyze the Hölder modulus of \(\mathcal{T}v\) for \(v\in C_b(\mathbb{X})\) with \([v]_{\alpha,\mathbb{X}}<\infty\). Set \(z:=(x,a)\in\mathbb{Z}\) and \(z':=(x',a)\in\mathbb{Z}.\) Then \(|z-z'|=|x-x'|\). By 38 , \[\left|E[r(z,W)- r(z',W)]\right| \le E\left[ \left|r(z,W)-r(z',W)\right| \right] \le \ell_r |x-x'|^{\alpha_r}.\] Also, by (i) in Assumption 5, \(\left|E[r(z,W)]-E[r(z',W)]\right| \le 2r_\vee.\) Therefore, \[\label{eqn:tu95rwd95holder95const} \begin{align} \left|E[r(z,W)- r(z',W)]\right| &\le \left( \ell_r |x-x'|^{\alpha_r} \right)\wedge (2r_\vee)\\ &\le \ell_r^{\alpha/\alpha_r}(2r_\vee)^{1-\alpha/\alpha_r}|x-x'|^\alpha\\ &= (1-\gamma \ell_f^\alpha)\ell_\alpha|x-x'|^\alpha, \end{align}\tag{66}\] where we applied 65 with \(s=\ell_r |x-x'|^{\alpha_r}\), \(t=2r_\vee\), and \(\theta=\alpha/\alpha_r\). Moreover, since \(\alpha\le 1\), Jensen’s inequality and 39 imply \[\label{eqn:tu95vf95holder95const} \begin{align} E\left[ \left|v(f(z,W))-v(f(z',W))\right| \right] &\le [v]_{\alpha,\mathbb{X}} E\left[ \left|f(z,W)-f(z',W)\right|^\alpha \right]\\ &\le [v]_{\alpha,\mathbb{X}} \left( E\left[ \left|f(z,W)-f(z',W)\right| \right] \right)^\alpha\\ &\le [v]_{\alpha,\mathbb{X}}\ell_f^\alpha |x-x'|^\alpha. \end{align}\tag{67}\] Hence, combining 66 and 67 yields \[\begin{align} &\left| E[r(z,W)+\gamma v(f(z,W))] - E[r(z',W)+\gamma v(f(z',W))] \right|\\ &\qquad\le \left( (1-\gamma \ell_f^\alpha)\ell_\alpha+\gamma \ell_f^\alpha [v]_{\alpha,\mathbb{X}} \right)|x-x'|^\alpha. \end{align}\]
Taking the maximum over \(a\in\mathbb{A}\) on both sides and that \(|\sup_a h_1(a) - \sup_{a}h_2(a)|\leq \sup_a|h_1(a)-h_2(a)|\) for any functions \(h_1,h_2\), we obtain \[|\mathcal{T}v(x) - \mathcal{T}v(x')|\leq \left( (1-\gamma \ell_f^\alpha)\ell_\alpha+\gamma \ell_f^\alpha [v]_{\alpha,\mathbb{X}} \right)|x-x'|^\alpha.\] This implies that \[[\mathcal{T}v]_{\alpha,\mathbb{X}} \le (1-\gamma \ell_f^\alpha)\ell_\alpha+\gamma \ell_f^\alpha [v]_{\alpha,\mathbb{X}}.\]
To show the Hölder continuity of the fixed point \(V^*\), we consider the Picard iteration approximation. Specifically, define \(v_0\equiv 0\) and \(v_{k+1}:=\mathcal{T}v_k\) for \(k\ge 0\). Since \([v_0]_{\alpha,\mathbb{X}}=0\), the preceding inequality implies by induction that \([v_k]_{\alpha,\mathbb{X}}\le \ell_\alpha,\) for all \(k\ge 0.\)
Because \(\mathcal{T}\) is a contraction on \(C_b(\mathbb{X})\), \(v_k\to V^*\) uniformly. Hence, for all \(x,x'\in\mathbb{X}\), \[|V^*(x)-V^*(x')| = \lim_{k\to\infty}|v_k(x)-v_k(x')| \le \ell_\alpha |x-x'|^\alpha,\] and therefore \([V^*]_{\alpha,\mathbb{X}}\le \ell_\alpha\).
Next, by the definition of \(Q^*\) in 3 , \[Q^*(z) = E[r(z,W)+\gamma V^*(f(z,W))], \qquad z\in\mathbb{Z}.\] Let \(z,z'\in\mathbb{Z}\). Using the Hölder modulus of \(V^*\) and applying the same argument as in 66 , we have \[\begin{align} |Q^*(z)-Q^*(z')| &\le \left|E[r(z,W)- r(z',W)]\right|+\gamma E\left[ \left|V^*(f(z,W))-V^*(f(z',W))\right| \right]\\ &\le (1-\gamma \ell_f^\alpha)\ell_\alpha |z-z'|^\alpha + \gamma \ell_f^\alpha [V^*]_{\alpha,\mathbb{X}}|z-z'|^\alpha\\ &\le \ell_\alpha |z-z'|^\alpha. \end{align}\] Thus, \([Q^*]_{\alpha,\mathbb{Z}}\le \ell_\alpha.\) Moreover, \[|Q^*(z)| \le \left|E[r(z,W)]\right|+\gamma \|V^*\| \le r_\vee+\gamma \|V^*\|, \qquad z\in\mathbb{Z},\] so \(Q^*\in C_b(\mathbb{Z})\).
Finally, since \(\mathcal{T}V^* = V^*\in C_b(\mathbb{X})\) and \(Q^*\) is defined by 3 , we have that \[\max_{a\in\mathbb{A}}Q^*(x,a) = \max_{a\in\mathbb{A}} E[r(x,a,W)+\gamma V^*(f(x,a,W))] = \mathcal{T}V^*(x) = V^*(x)\] for all \(x\in\mathbb{X}\). This completes the proof. ◻
Proof. Fix an integer \(k\ge2\). By enlarging the underlying probability space if necessary, define an i.i.d. Rademacher sequence \(\{\epsilon_i:i=1,\dots,n\}\) on \((\Omega,\mathcal{F},P)\) independent of \(\{W_i:i=1,\dots,n\}\). Let \(\Theta_0\subset\Theta\) be a countable dense set and set \(\mathcal{G}:=\sigma(W_1,\dots,W_n)\).
Since \(\theta\to g(\theta,w)\) is \(\eta\)-Hölder for every fixed \(w\), and since \[|Eg(\theta,W)-Eg(\theta',W)| \le E\left[ L(W) \right]\,|\theta-\theta'|^\eta,\] the map \(\theta\to (E_n-E)g(\theta,W)\) is continuous on \(\Theta\). Hence \[Z_n=\frac{1}{n}\sup_{\theta\in\Theta_0}\left|\sum_{i=1}^n\left( g(\theta,W_i)-Eg(\theta,W) \right)\right|.\] Therefore, by standard symmetrization theorem for empirical processes (see Theorem 3.1.21 in [40]), \[\label{eqn:emp95holder95symm} E\left[ Z_n^k \right] \le \frac{2^k}{n^k} E\left[ E\left[ \sup_{\theta\in\Theta_0}\left|\sum_{i=1}^n \epsilon_i g(\theta,W_i)\right|^k \middle| \mathcal{G} \right] \right].\tag{68}\] We proceed to bound the conditional expectation within the r.h.s of 68 .
We starting with the first moment \(k=1\). Define \(R_{n,2}:=E_n\left[ R(W)^2 \right]^{1/2}\), \(L_{n,2}:=E_n\left[ L(W)^2 \right]^{1/2}\). We consider the symmetrized process \[X_\theta:=\frac{1}{\sqrt n}\sum_{i=1}^n \epsilon_i g(\theta,W_i).\] We proceed to split and bound \[\label{eqn:tu95X95split} E\left[ \sup_{\theta\in\Theta_0}\left|X_\theta\right| \middle| \mathcal{G} \right] \leq E\left[ \left|X_{\theta_0}\right| \middle| \mathcal{G} \right] + E\left[ \sup_{\theta\in\Theta_0}\left|X_\theta-X_{\theta_0}\right| \middle| \mathcal{G} \right]\tag{69}\] where \(\theta_0\in\Theta_0\) is an arbitrary point.
For the first term in 69 , we observe that \[E\left[ \left|X_{\theta_0}\right|^2 \middle| \mathcal{G} \right] = E_n\left[ g(\theta_0,W)^2 \right]\le R_{n,2}^2.\] Therefore, we have \(E\left[ \left|X_{\theta_0}\right| \middle| \mathcal{G} \right]\le R_{n,2}\).
For the second term in 69 , we use sub-Gaussianity of the Rademacher process. Specifically, under measure \(E[\cdot|\mathcal{G}]\), the process \(\{X_\theta:\theta\in\Theta_0\}\) is sub-Gaussian with respect to \(d_n\) where \[d_n(\theta,\theta') := E_n\left[ \left|g(\theta,W)-g(\theta',W)\right|^2 \right]^{1/2}\] for \(\theta,\theta'\in\Theta_0\). This is because for every \(\lambda\in\mathbb{R}\), \[\begin{align} E\left[ \exp\left( \lambda(X_\theta-X_{\theta'}) \right) \middle| \mathcal{G} \right] &= \prod_{i=1}^n E\left[ \exp\left( \frac{\lambda\epsilon_i}{\sqrt n}\left( g(\theta,W_i)-g(\theta',W_i) \right) \right) \middle| \mathcal{G} \right]\\ &\le \exp\left( \frac{\lambda^2}{2}d_n(\theta,\theta')^2 \right), \end{align}\] where we used \(E_\epsilon[e^{u\epsilon}]\le e^{u^2/2}\). We note that, if we write \(d_\eta(\theta,\theta'):=|\theta-\theta'|^\eta\), then \[\label{eqn:emp95holder95dn} d_n(\theta,\theta')\le L_{n,2}\,d_\eta(\theta,\theta')\tag{70}\] for all \(\theta,\theta'\in\Theta_0\).
Next, we apply Dudley’s entropy integral bound for sub-Gaussian processes (see for example [38]) to the process \(\{X_\theta-X_{\theta_0}:\theta\in\Theta_0\}\) and \(\{-(X_\theta-X_{\theta_0}):\theta\in\Theta_0\}\), yielding \[E\left[ \sup_{\theta\in\Theta_0}\left|X_\theta-X_{\theta_0}\right| \middle| \mathcal{G} \right] \le 64\int_0^{D_n}\sqrt{\log N(u,\Theta_0,d_n)}\,du,\] where \(D_n:=\mathrm{diam}(\Theta_0,d_n)\). Let \(D_\eta:=\mathrm{diam}(\Theta,d_\eta)\), then 70 implies \(D_n\le L_{n,2}D_\eta\), and hence \[\begin{align} \int_0^{D_n}\sqrt{\log N(u,\Theta_0,d_n)}\,du &\stackrel{(i)}\le \int_0^{L_{n,2}D_\eta} \sqrt{\log N\left( \frac{u}{L_{n,2}},\Theta,d_\eta \right)}\,du \\ &\stackrel{(ii)}= L_{n,2}\int_0^{D_\eta}\sqrt{\log N(v,\Theta,d_\eta)}\,dv \\ &=: C_{\Theta,\eta}L_{n,2}. \end{align}\] Here, \((i)\) uses 70 together with the bound \(D_n\le L_{n,2}D_\eta\), \((ii)\) is the change of variables \(v=u/L_{n,2}\), and the last line defines a finite constant that depends only on \((\Theta,\eta)\) because \(\Theta\subset\mathbb{R}^d\) is compact.
Combining the preceding bounds and 69 , we obtain \[\label{eqn:emp95holder95first95moment} E\left[ \sup_{\theta\in\Theta_0}\left|\sum_{i=1}^n \epsilon_i g(\theta,W_i)\right| \middle| \mathcal{G} \right]= \sqrt{n}E\left[ \sup_{\theta\in\Theta_0}\left|X_\theta\right| \middle| \mathcal{G} \right] \le \sqrt{n}\left( R_{n,2}+C_{\Theta,\eta}L_{n,2} \right).\tag{71}\]
To generalize this to integers \(k\ge2\), we use the Khinchin-Kahane inequality. Specifically, consider the following countable set \[T_n:= \Bigl\{ \left( g(\theta,W_1),\dots,g(\theta,W_n) \right):\theta\in\Theta_0 \Bigr\} \cup \Bigl\{ -\left( g(\theta,W_1),\dots,g(\theta,W_n) \right):\theta\in\Theta_0 \Bigr\} \subset\mathbb{R}^n.\] Then \[\sup_{\theta\in\Theta_0}\left|\sum_{i=1}^n \epsilon_i g(\theta,W_i)\right| = \sup_{t\in T_n}\sum_{i=1}^n t_i\epsilon_i.\] Therefore, Proposition 3.2.8 of [40] with \(p=k\) and \(q=1\) gives \[E\left[ \sup_{\theta\in\Theta_0}\left|\sum_{i=1}^n \epsilon_i g(\theta,W_i)\right|^k \middle| \mathcal{G} \right]^{1/k} \le C_k\, E\left[ \sup_{\theta\in\Theta_0}\left|\sum_{i=1}^n \epsilon_i g(\theta,W_i)\right| \middle| \mathcal{G} \right],\] where \(C_k<\infty\) depends only on \(k\). Thus, it follows from 71 that \[E\left[ \sup_{\theta\in\Theta_0}\left|\sum_{i=1}^n \epsilon_i g(\theta,W_i)\right|^k \middle| \mathcal{G} \right] \le C_k^k n^{k/2}\left( R_{n,2}+C_{\Theta,\eta}L_{n,2} \right)^k.\] Substituting this estimate into 68 , we conclude that for all \(k\geq 2\) \[\label{eqn:tu95EZnk95temp} E\left[ Z_n^k \right] \le \frac{C_k'}{n^{k/2}} E\left[ \left( R_{n,2}+C_{\Theta,\eta}L_{n,2} \right)^k \right] \le \frac{C_k''}{n^{k/2}} \left( E\left[ R_{n,2}^k \right]+E\left[ L_{n,2}^k \right] \right)\tag{72}\] for some \(C''_k < \infty\) depending on \(k\) and \(C_{\Theta,\eta}\), where we used \((a+b)^k\le 2^{k-1}(a^k+b^k)\).
Finally, to finish the proof, we observe that since \(k/2\ge1\), Jensen’s inequality yields \[R_{n,2}^k = \left( E_n\left[ R(W)^2 \right] \right)^{k/2} \le E_n\left[ R(W)^k \right] \quad\text{and}\quad L_{n,2}^k = \left( E_n\left[ L(W)^2 \right] \right)^{k/2} \le E_n\left[ L(W)^k \right].\] Taking expectations, we obtain \[E\left[ R_{n,2}^k \right]\le E\left[ R(W)^k \right]\quad\text{and}\quad E\left[ L_{n,2}^k \right]\le E\left[ L(W)^k \right].\] Combining this with 72 completes the proof of Proposition 4. ◻
Proof. We divide the proof into two parts. First, we establish the Hölder continuity statements for \(Q^*\) and \(\widehat Q_n\), which in turn verify the properties in Assumption 1. We then use these Hölder continuity together with Proposition 4 to show that the envelope moment bounds in Assumption 2 are satisfied.
Fix \(\alpha\in(0,\alpha_r]\) such that \(\gamma\ell_f^\alpha<1\), and let \(z_0\) be the reference point from Assumption 6 part (iii). Define \[R(w):=|r(z_0,w)|+\mathrm{diam}(\mathbb{Z})^{\alpha_r}L_r(w),\] and let \(r_\vee:=E[R(W)]\) and \(\ell_r:=E[L_r(W)]\). Since \(\mathbb{Z}\) is compact, by Assumption 6 (iii) and (iv), \(R(W)\) has moments of every order. Moreover, note that \[\begin{align} |r(z,w)|&\le |r(z_0,w)|+|r(z,w)-r(z_0,w)|\\ &\leq|r(z_0,w)| + L_r(w)|z-z_0|^{\alpha_r}\\ &\le R(w) \end{align}\] for all \(z\in\mathbb{Z}\) and \(\;w\in\mathbb{W}.\)
Next, as in Theorem 4, we set \[\ell_\alpha:=\frac{\ell_r^{\alpha/\alpha_r}(2r_\vee)^{1-\alpha/\alpha_r}}{1-\gamma\ell_f^\alpha}.\] For \(\mu\in\{\psi,\psi_n^V,\psi_n^Q\}\), write \(E_\mu\phi(W):=\int_\mathbb{W}\phi(w)\mu(dw)\). The preceding bound together with Assumption 6 (iv) and (v) yields \[\begin{align} E_\mu|r(z,W)|&\le E_\mu R(W),\\ E_\mu|r(z,W)-r(z',W)|&\le E_\mu L_r(W)\,|z-z'|^{\alpha_r},\\ E_\mu|f(z,W)-f(z',W)|&\le \ell_f|z-z'|. \end{align}\] Therefore, Theorem 4 applies to the case \(\mu = \psi\), while Corollary 1 applies to measures \(\psi_n^V(\omega,\cdot)\) and \(\psi_n^Q(\omega,\cdot)\). In particular, \(Q^*\) is \(\alpha\)-Hölder on \(\mathbb{Z}\), \([V^*]_{\alpha,\mathbb{X}}\le \ell_\alpha\), and \[\label{eqn:tu95hatV95holder95modulus} \left[ \widehat V_n \right]_{\alpha,\mathbb{X}}\le \widehat L_{\alpha,n}^V := \frac{\left( E_n^V L_r(W) \right)^{\alpha/\alpha_r}\left( 2E_n^V R(W) \right)^{1-\alpha/\alpha_r}}{1-\gamma\ell_f^\alpha}.\tag{73}\]
To show the Hölder continuity of \(\widehat Q_n\), we start from the bounds \[|r(z,w)-r(z',w)|\le L_r(w)|z-z'|^{\alpha_r} \quad\text{and}\quad |r(z,w)-r(z',w)|\le 2R(w).\] So, inequality 65 with \(\theta=\alpha/\alpha_r\), implies \[\label{eqn:tu95r95holder} |r(z,w)-r(z',w)|\le \kappa_r(w)|z-z'|^\alpha\tag{74}\] for all \(z,z'\in\mathbb{Z}\), where \[\kappa_r(w):=L_r(w)^{\alpha/\alpha_r}(2R(w))^{1-\alpha/\alpha_r}.\]
Using 37 , the bound on \([\widehat V_n]_{\alpha,\mathbb{X}}\), and Assumption 6 (v), we obtain for all \(z,z'\in\mathbb{Z}\), \[\begin{align} |\widehat Q_n(z)-\widehat Q_n(z')| &\le E_n^Q|r(z,W)-r(z',W)| + \gamma E_n^Q\left|\widehat V_n(f(z,W))-\widehat V_n(f(z',W))\right| \\ &\le \left( E_n^Q\kappa_r(W)+\gamma \ell_f^\alpha \widehat L_{\alpha,n} \right)|z-z'|^\alpha. \end{align}\] Thus \(\widehat Q_n(\omega,\cdot)\) is \(\alpha\)-Hölder on \(\mathbb{Z}\) for every \(\omega\) and the first claim in Theorem 5 follows. In particular, Assumption 1 holds.
We now verify Assumption 2. We fix \(q\in[0,\bar q]\) and \(q<\alpha^*\). Then, by the definition of \(\alpha^*\), there exists \(\alpha\in( q,\alpha_r]\) such that \(\gamma\ell_f^\alpha<1\). Since \(R(W)\) and \(L_r(W)\) have moments of every order, Jensen’s inequality gives \[E\left[ \left( E_n^V L_r(W) \right)^p \right]\leq EE_n^V [L_r(W)^p] = E[L_r(W)^p]\] and similarly \(E\left[ \left( E_n^V R(W) \right)^p \right] \leq E[R(W)^p]\) for all \(p\ge 1\). Therefore, for every integer \(k\ge1\), \[\label{eqn:tu95Ln95moment95bd} \sup_{n\ge1}E\left[ \left( \widehat L_{\alpha,n}^V \right)^k \right]=:L_k<\infty.\tag{75}\]
Next, define \[g(z,w):=r(z,w)+\gamma V^*(f(z,w)).\] Then \(|g(z,w)|\le R(w)+\gamma\|V^*\|_\infty\). Also, since \([V^*]_{\alpha,\mathbb{X}}\le \ell_\alpha\) and 74 holds, \[\begin{align} |g(z,w)-g(z',w)| &\le \kappa_r(w)|z-z'|^\alpha + \gamma \ell_\alpha |f(z,w)-f(z',w)|^\alpha \\ &\leq \left( \kappa_r(w)+\gamma\ell_\alpha\ell_f^\alpha \right)|z-z'|^\alpha \end{align}\] for all \(z,z'\in\mathbb{Z}\). Hence with \[Z_n^U:=\sup_{z\in\mathbb{Z}}|(E_n^U-E)g(z,W)|\] where \(U = Q\) or \(V\), Proposition 4 applies, yielding \[\label{eqn:tu95Zk95moment95bd} E\left[ \left( Z_n^U \right)^k \right]\le \frac{C_k}{n^{k/2}},\tag{76}\] for all integer \(k\ge2\) and \(U = Q\) or \(V\).
With this moment bound, we verify the first part of Assumption 2. From the definition of \(\widehat Q_n\), \[\label{eqn:sample95split95q95decomp} \begin{align} \sup_{z\in \mathbb{Z}}\left|\widehat Q_n(z)-Q^*(z)\right| &= \sup_{z\in \mathbb{Z}}\left|(E_n^Q-E)g(z,W)+\gamma E_n^Q\left[ (\widehat V_n-V^*)(f(z,W)) \right]\right|\\ &\leq Z_n^Q + \gamma\sup_{z\in\mathbb{Z}}\left|E_n^Q\left[ (\widehat V_n-V^*)(f(z,W)) \right]\right|\\ &\leq Z_n^Q + \gamma \left\|\widehat V_n-V^*\right\| \end{align}\tag{77}\] Then, to achieve the first envelope moment bounds in Assumption 2, it remains to bound the moments of \(\left\|\widehat V_n-V^*\right\|\). By the Bellman equation for \(V^*\) and the definition of \(\widehat V_n\) in 36 , we see that \[\begin{align}\left\|\widehat V_n-V^*\right\|&\leq \sup_{z\in\mathbb{Z}}\left|(E_n^V -E)r(z,W) + \gamma E_n^V\left[ \widehat V_n(f(z,W)) \right] - \gamma E\left[ V^*(f(z,W)) \right]\right|\\ & \leq \sup_{z\in\mathbb{Z}} \left|(E_n^V -E)g(z,W)\right| + \gamma\sup_{z\in\mathbb{Z}} \left|E_n^V\left[ \widehat V_n(f(z,W)) - V^*(f(z,W)) \right]\right|\\ &\leq Z_n^V + \gamma \left\|\widehat V_n-V^*\right\| \end{align}\] Therefore, rearranging the inequality, we get \[\label{eqn:sample95split95delta} \left\|\widehat V_n-V^*\right\| \le \frac{Z_n^V}{1-\gamma}.\tag{78}\] From 77 and 78 , we see that \[\sup_{z\in\mathbb{Z}}|\widehat Q_n(z)-Q^*(z)| \le \delta_n:= Z_n ^Q+ \frac{\gamma Z_n^V}{1-\gamma} + n^{-1}\] with measurable \(\delta_n > 0\), where the measurability follows from the continuity of \(g\) and the compactness of \(\mathbb{Z}\). Moreover, applying 76 with \(k=2\), we conclude that \(E\left[ \delta_n^2 \right]\le C/n\) for some \(C < \infty\).
Next, we verify the divided-difference bound in Assumption 2. Define \[G_n^V(z,w):=r(z,w)+\gamma\widehat V_n(f(z,w)), \qquad B_n^V(w):=\kappa_r(w)+\gamma\ell_f^\alpha\widehat L_{\alpha,n}^V.\] Then, by 74 , 73 , and the Lipschitz property of \(f\), \[\label{eqn:sample95split95Gn95holder} |G_n^V(z,w)-G_n^V(z',w)|\le B_n^V(w)|z-z'|^\alpha\tag{79}\] for all \(z,z'\in\mathbb{Z}\) and \(w\in\mathbb{W}\). Moreover, notice that \[\widehat Q_n(z)=E_n^Q\left[ G_n^V(z,W) \right]\quad\text{and}\quad Q^*(z)=E\left[ G_n^V(z,W) \right]-\gamma\int_\mathbb{X}(\widehat V_n-V^*)(y)\,P(dy|z).\]
We subtract the identities and divide by \(|a-b|^{ q}\) to get \[\label{eqn:sample95split95divdiff} \begin{align} &\sup_{x\in\mathbb{X},a\neq b}\frac{\left|\left( \widehat Q_n(x,a)-Q^*(x,a) \right)-\left( \widehat Q_n(x,b)-Q^*(x,b) \right)\right|}{|a-b|^{q}}\\ & \le \underbrace{\sup_{x\in\mathbb{X},a\neq b } \left|(E_n^Q-E)\left[ \frac{G_n^V(x,a,W)-G_n^V(x,b,W)}{|a-b|^{q}} \right]\right|}_{=:Y_n}\\ &\quad + \underbrace{\gamma\sup_{x\in\mathbb{X},a\neq b} \frac{\left|\int_\mathbb{X}(\widehat V_n-V^*)(y)\,\left( P(dy|x,a)-P(dy|x,b) \right)\right|}{|a-b|^{q}}}_{=:U_n^V}, \end{align}\tag{80}\]
We bound the two terms separately. We control \(U_n^V\) using by Assumption 6 (ii). Specifically, since \(\bar q\geq q\) and \(\mathbb{A}\) is compact, \[\label{eqn:sample95split95transition95term} \begin{align} U^V_n&\leq \gamma\left\|\widehat V_n - V^*\right\|\sup_{x\in\mathbb{X},a\neq b} \frac{d_{\mathrm{TV}}(P(\cdot|x,a),P(\cdot|x,b))}{|a-b|^{ q}}\\ &\le 2\gamma \ell_P\left\|\widehat V_n - V^*\right\| \sup_{a\neq b}|a-b|^{\bar q - q}\\ &=2\gamma \ell_P\left\|\widehat V_n - V^*\right\| \mathrm{diam}(\mathbb{A})^{\bar q -q} \end{align}\tag{81}\]
To bound \(Y_n\), let \(\Theta:=\mathbb{X}\times\mathbb{A}\times\mathbb{A}\). For \(\theta=(x,a,b)\in\Theta\), define \[H_n^V(\theta,w):= \begin{cases} \dfrac{G_n^V(x,a,w)-G_n^V(x,b,w)}{|a-b|^{q}}, & a\ne b,\\[1ex] 0, & a=b. \end{cases}\] We claim that the following lemma holds for \(H_n^V\). The proof of Lemma 6 is deferred to Appendix 9.3.1.
Lemma 6. There exists a constant \(C_H<\infty\), depending only on \((\alpha, q,\mathbb{A})\), such that \[\label{eqn:tu95H95holder} |H_n^V(\theta,w)-H_n^V(\theta',w)|\leq C_H B_n^V(w)|\theta-\theta'|^{\alpha- q},\tag{82}\] for all \(\theta,\theta'\in\Theta\), and \(w\in\mathbb{W}\).
Now we condition on \(\mathcal{F}_n^V:=\sigma(W_1^V,\dots,W_n^V)\). Then, \(H_n^V\) and \(B_n^V\) are deterministic. Note that, by Lemma 6, \(\theta\rightarrow H_n^V(\theta,w)\) is Hölder continuous in the sense of Proposition 4. Moreover, by 79 and Lemma 6 both \(|H_n^V(\cdot,w)|\) and the Hölder coefficient \(\left[ H_n^V(\cdot,w) \right]_{\alpha- q,\Theta}\) are bounded by \((\mathrm{diam}(\mathbb{A})^{\alpha- q}\vee C_H)B_n^V(w)\). Since \[B_n^V(w):= \kappa_r(w)+\gamma\ell_f^\alpha\widehat L_{\alpha,n}^V,\] and \(\kappa_r(W)\) has moments of every order, we have that for all integers \(k\ge2\), \[E\left[ B_n^V(W)^k \middle| \mathcal{F}_n^V \right]\le C_k\left( 1+\widehat L_{\alpha,n}^k \right),\] for some \(C_k\) that only depend on \((k,\mathbb{A},\alpha, q,\ell_\alpha,\gamma,E[\kappa_r(W)^k])\).
Hence, under \(E[\cdot|\mathcal{F}_n^V]\), Proposition 4 applies to the class \(\{H_n^V(\theta,\cdot):\theta\in\Theta\}\) on the compact parameter space \(\Theta\). Therefore, we conclude that for every integer \(k\ge2\), \[E\left[ Y_n^k \middle| \mathcal{F}_n^V \right] \le \frac{C_k\left( 1+\widehat L_{\alpha,n}^k \right)}{n^{k/2}},\] Taking expectations and using 75 , we obtain \[\label{eqn:sample95split95Yn95moment} E\left[ Y_n^k \right]\le \frac{C_k}{n^{k/2}}\tag{83}\] for some possibly different \(C_k\).
Combining 80 , 81 , we conclude that \[\sup_{x\in\mathbb{X}}\sup_{a\ne b} \frac{\left|\left( \widehat Q_n(x,a)-Q^*(x,a) \right)-\left( \widehat Q_n(x,b)-Q^*(x,b) \right)\right|}{|a-b|^{ q}} \le \Lambda_n( q),\] where \[\Lambda_n( q):= Y_n+2\gamma\ell_P\mathrm{diam}(\mathbb{A})^{\bar q-q}\left\|\widehat V_n - V^*\right\|+n^{-1}.\] Finally, by 83 , 76 , and 78 , we conclude that for all integers \(k\ge2\) \[E\left[ \Lambda_n( q)^k \right]\le \frac{C_k}{n^{k/2}},\] Hence, the second part of Assumption 2 follows. ◻
Proof. Let \(p:=\alpha- q\in(0,1]\). To show 82 , fix \(w\in\mathbb{W}\) and \(\theta=(x,a,b)\), \(\theta'=(x',a',b')\in\Theta\). Write \[d:=|\theta-\theta'|,\qquad s:=|a-b|,\qquad t:=|a'-b'|,\] and assume without loss of generality that \(s\ge t\).
If \(q=0\), then 79 gives \[\begin{align} |H_n^V(\theta,w)-H_n^V(\theta',w)| &\le |G_n^V(x,a,w)-G_n^V(x',a',w)|+|G_n^V(x,b,w)-G_n^V(x',b',w)| \\ &\le 2B_n^V(w)d^\alpha, \end{align}\] which is 82 with \(C_H = 2\), as \(p=\alpha\).
Assume now that \(q>0\). By 79 , \[\label{eqn:tu95H95pointwise} |H_n^V(\theta,w)|\le B_n^V(w)s^p, \qquad |H_n^V(\theta',w)|\le B_n^V(w)t^p.\tag{84}\] If \(t=0\), then \(H_n^V(\theta',w)=0\), so 84 yields \[\begin{align} |H_n^V(\theta,w)-H_n^V(\theta',w)| = |H_n^V(\theta,w)| \le B_n^V(w)s^p. \end{align}\] Since \(|u|-|v| \leq |u-v|\), we have \[\label{eqn:tu95d95ub95st} s = s-t\leq |a-a'+b'-b|\leq |a-a'| + |b-b'|\leq 2d.\tag{85}\] So, \[|H_n^V(\theta,w)-H_n^V(\theta',w)| \leq 2^pB_n^V(w)d^p,\] showing 82 with \(C_H = 2^p\).
Hence it remains to consider the case \(s\ge t>0\) and \(q>0\). Set \[D:=G_n^V(x,a,w)-G_n^V(x,b,w), \qquad D':=G_n^V(x',a',w)-G_n^V(x',b',w).\] Then, it is easy to see that \[|H_n^V(\theta,w)-H_n^V(\theta',w)| \le \underbrace{ s^{-q}|D-D'|}_{=:I_1}+\underbrace{|D'|\left|s^{-q}-t^{-q}\right|}_{=:I_2}.\] We then bound \(I_1\) and \(I_2\) separately.
For \(I_1\), 79 implies \(|D-D'|\le 2B_n^V(w)d^\alpha\), while 84 implies \[|D-D'|\le |D|+|D'|\le B_n^V(w)(s^\alpha+t^\alpha)\le 2B_n^V(w)s^\alpha.\] Hence, we have \[\label{eqn:tu95I195bd} I_1\le 2B_n^V(w)\min\{d^\alpha s^{-q},\,s^p\}\le 2B_n^V(w)d^p.\tag{86}\] Here, the last inequality is from the following two cases: if \(s\le d\), then \(s^p\le d^p\), whereas if \(s>d\), then \(d^\alpha s^{-q}\le d^{\alpha-q}=d^p\).
For \(I_2\), using \(|D'|\le B_n^V(w)t^\alpha\) and writing \(\lambda:=t/s\in(0,1]\), we obtain \[I_2\le B_n^V(w)t^\alpha(t^{-q}-s^{-q}) = B_n^V(w)s^p(\lambda^p-\lambda^\alpha).\] We claim that for \(\lambda\in [0,1]\), \[\label{eqn:tu95lambda95bd} \lambda^p-\lambda^\alpha\leq C(1-\lambda)^p\tag{87}\] for some \(C < \infty\) that only depend on \((\alpha,p)\). Indeed, consider \[\phi(\lambda):= \frac{\lambda^p-\lambda^\alpha}{(1-\lambda)^p}\] and note that \(\phi\) is continuous on \([0,1)\). Therefore, to show 87 , it suffices to check that \(\lim_{\lambda\uparrow 1} \phi(\lambda) < \infty\). By L’Hôspital’s rule, \[\lim_{\lambda\uparrow 1} \phi(\lambda) = \lim_{\lambda\uparrow 1}\frac{p\lambda^{p-1} - \alpha\lambda^{\alpha-1}}{-p(1-\lambda)^{p-1}} = \lim_{\lambda\uparrow 1}\frac{q}{p(1-\lambda)^{p-1}}\leq \frac{q}{p}.\] Hence, 87 holds and \[I_2\le CB_n^V(w)s^p(1-\lambda)^p = CB_n^V(w)(s-t)^p \le C2^p B_n^V(w)d^p,\] where the last inequality follows from 85 .
Combining the bounds for \(I_1\) and \(I_2\), we conclude that \[|H_n^V(\theta,w)-H_n^V(\theta',w)| \le C_H B_n^V(w)d^{\alpha-q}\] for some constant \(C_H<\infty\) depending only on \((\alpha,p = \alpha-q)\). This proves 82 . ◻