Functional Natural Policy Gradients

Aurélien Bibaut, Houssam Zenati, Thibaud Rahier, Nathan Kallus · 2026

Read Functional Natural Policy Gradients by Aurélien Bibaut, Houssam Zenati, Thibaud Rahier, Nathan Kallus (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-28681.txt.

Introduction

Bibaut and co-authors propose a cross-fitted debiasing device for learning policies from offline data. A key result is square-root-N regret, even for policy classes more complex than Donsker classes. That result needs a product-of-errors remainder that shrinks fast enough. The regret bound splits into two factors. One factor reflects plug-in policy error and policy class complexity. The other reflects the environment and its dynamics.

Catalog record

CREATORAurélien Bibaut, Houssam Zenati, Thibaud Rahier, Nathan Kallus
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22919
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.28681

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Functional Natural Policy Gradients Aurélien Bibaut, Houssam Zenati, Thibaud Rahier, Nathan Kallus Abstract We propose a cross-fitted debiasing device for policy learning from offline data. A key consequence of the resulting learning principle is N \sqrt{N} regret even for policy classes with complexity greater than Donsker, provided a product-of-errors nuisance remainder is O ( N − 1 / 2 ) O(N^{-1/2}) . The regret bound factors into a plug-in policy error factor governed by policy-class complexity and an environment nuisance factor governed by the complexity of the environment dynamics, making explicit how one may be traded against the other. 1 Introduction Personalized decision policies are increasingly central in areas such as healthcare ( 3 ) , education ( 20 ) , and public policy ( 18 ) , where tailoring actions to individual characteristics can improve outcomes. In many of these settings, however, actively experimenting with new policies to generate “online data” is expensive, risky, or infeasible, which motivates methods that can evaluate and optimize policies using pre-existing “offline data.” A variety of work studies semiparametric efficient estimation of the value of a fixed policy from offline data ( 22 ; 5 ; 7 ; 11 ; 14 ; 15 ; 13 ) . And, a variety of work considers selecting the policy that optimizes such estimates over policies in a given class ( 1 ; 27 ; 16 ; 28 ; 8 ; chernozhukov2019semi ) , which generally yields rates the scale with policy class complexity, e.g., O_{P}(N^{-1/2}) for VC classes. 19 get regret acceleration to o_{P}(N^{-1/2}) by leveraging an equicontinuity argument. Margin (or, noise) conditions controlling the fraction of hard decision contexts can also speed up policy-search regret ( 4 ; 10 ; 9 ; 23 ; 24 ; 17 ) . However, with the exception of 2 whose assumptions imply the optimal policy solves a smooth conditional moment restriction, none of these works leverage cross-fitting or debiasing to estimate the optimal policy itself, such as done for example when targeting a low-dimensional regular functional ( 6 ) . In this paper we show how to perform a cross-fitted policy debiasing update to an initial ERM policy fit. Specifically, we recycle the machinery of targeted maximum loss estimation (TMLE) ( 26 ; 25 ) to find a policy within a pre-specified policy class that maximally increases population-level policy value. To make the analogy clear for readers familiar with TMLE: here, the target functional is the optimal policy value, the nuisance we debias is the policy, and the efficient score equation we solve is an estimated first-order condition for value optimality at the population level. We demonstrate how to solve for the functional value-optimality condition via optimization along a one-dimensional policy subclass, which we construct in the same way van2016one construct a universal-least favorable submodel (ULFM) within a nuisance space. It turns out that, in the policy optimization setting, ULFMs are natural policy gradient (NPG) flows ( 12 ) . In that sense, our proposal can be seen as a functional NPG ascent, and is similar in spirit to functional optimization (see 21 ; khoury2025learning for example). The key statistical enablers of our results are two-fold. First, we construct estimated NPG flows / ULFMs on one split of the data and optimize the index along the estimated flow on another split of the data, which allows us to debias policies living in classes much larger than Donsker. Second, we leverage the TMLE principle: in policy learning, what we are after primarily isn’t a good estimate of the optimal value but a good estimate of a policy that realizes it. The TMLE principle allows us to merge these two objectives in one: since a TMLE is a plug-in estimate, a plug-in policy that realizes a good estimate of the optimal value must have good regret. Our results of course do not violate existing minimax results on policy learning. Our theorem provides rates in terms of an empirical process term over the one-dimensional NPG flow, which is trivially O_{P}(N^{-1/2}) and a product-of-nuisance-errors remainder term. The latter makes appear an environment-nuisance error factor and a policy error factor. What makes it possible to achieve root- N regret rate over larger-than-Donsker policy classes is that the environment dynamics are learnable. Therefore simple environment dynamics can alleviate the learning burden of complex policy class. 2 Setup We consider the contextual bandit setting. We observe i.i.d. copies of a context-action-reward triplet (X,A,Y)\in\mathcal{X}\times[K]\times[0,1] , for some K\geq 1 , generated from a context density q_{X} , logging policy \pi_{b} , and a conditional density of reward given action and context q_{Y} , where densities are w.r.t. an appropriate dominating measure. Specifically \displaystyle X \displaystyle\sim q_{X}, (1) \displaystyle A\mid X=x \displaystyle\sim\pi_{b}(\cdot\mid x), (2) \displaystyle Y\mid X=x,A=a \displaystyle\sim q_{Y}(\cdot\mid a,x). (3) For any policy \pi , generic pair of context and reward densities q=(q_{X},q_{Y}) , and f:\mathcal{X}\times[K]\times[0,1]\to\mathbb{R} , x\in\mathcal{X},~a\in[K] , define \displaystyle P_{q,\pi}f:= \displaystyle\int q_{X}(x)\sum_{a}\pi(a\mid x)q_{Y}(y\mid a,x)f(x,a,y)\,dx\,dy, (4) \displaystyle P:= \displaystyle P_{q,\pi_{b}}, (5) \displaystyle Q(a,x):= \displaystyle\int yq_{Y}(y\mid a,x)dy, (6) \displaystyle V(q,\pi):= \displaystyle\int q_{X}(x)\sum_{a}\pi(a\mid x)Q(a,x)\,dx (7) \displaystyle= \displaystyle P_{q,\pi}Y, (8) \displaystyle J_{\lambda}(q,\pi)= \displaystyle V(q,\pi)-\lambda\int q_{X}(x)\sum_{a}\pi(a\mid x)\log\pi(a\mid x)\,dx. (9) Let \Pi a class of policies. For any \pi , denote T_{\Pi}(\pi) the tangent space of \Pi at \pi , that is \displaystyle T_{\Pi}(\pi):=\left\{\left.\partial_{\epsilon}\log\pi_{\epsilon}\right|_{\epsilon=0}:\left\{\pi_{\epsilon}:\epsilon\right\}\text{ regular one-dimensional submodel of }\Pi,\pi_{\epsilon=0}=\pi\right\}. (10) 3 Semiparametric natural gradient and natural gradient flow Definition 1 (Semiparametric natural policy gradient) . For any pair of environment densities q=(q_{X},q_{Y}) and policy \pi\in\Pi , we define the semiparametric natural policy gradient at \pi under q G(q,\pi) as \displaystyle G(q,\pi)\in\argmin_{\phi\in T_{\Pi}(\pi)}\left\{P_{q,\pi}\,\frac{1}{2}\phi^{2}-\partial_{\pi}J_{\lambda}(q,\pi)(\pi\phi)\right\}. (11) Remark 1 . In the nonparametric policy class, that is when \Pi is the full simplex pointwise in x , the Riesz representer of the differential \displaystyle\phi\mapsto\partial_{\pi}J_{\lambda}(q,\pi)(\pi\phi) (12) under the inner product \displaystyle(\phi_{1},\phi_{2})\mapsto P_{q,\pi}[\phi_{1}\phi_{2}] (13) is the centered entropy-adjusted advantage \displaystyle A_{q,\pi}(x,a):=\left\{Q(a,x)-\lambda\log\pi(a\mid x)\right\}-\sum_{a^{\prime}}\pi(a^{\prime}\mid x)\left\{Q(a^{\prime},x)-\lambda\log\pi(a^{\prime}\mid x)\right\}. (14) Indeed, for any score \phi satisfying \sum_{a}\pi(a\mid x)\phi(x,a)=0 , \displaystyle\partial_{\pi}J_{\lambda}(q,\pi)(\pi\phi)=P_{q,\pi}\left[A_{q,\pi}\phi\right]. (15) For a semiparametric policy class \Pi , the natural gradient G(q,\pi) is the Riesz representer of the same differential restricted to the tangent space T_{\Pi}(\pi) . Equivalently, G(q,\pi) is the L^{2}(P_{q,\pi}) -projection of A_{q,\pi} onto T_{\Pi}(\pi) : \displaystyle G(q,\pi)\in\argmin_{\phi\in T_{\Pi}(\pi)}P_{q,\pi}\left[(\phi-A_{q,\pi})^{2}\right]. (16) Thus the nonparametric gradient is the centered entropy-adjusted advantage, while under a semiparametric policy class the gradient is its projection onto the tangent space of \Pi at \pi . Remark 2 . In higher level terms, remark 1 states that, in the nonparametric setting, the “direction” of highest value ascent is the advantage. The right notion of “directions” in optimization, and functional optimization, and in particular the space in which gradients live, is the tangent space. In the semiparametric setting, some components of the advantage are orthogonal to the tangent space. The advantage is a gradient in the sense that its inner product against scores gives the the variation of the objective. In semiparametric statistics terms, any such object is a valid gradient. The canonical gradient is the minimum norm such gradient, and it is thus the one that has no orthogonal component to the tangent space. This is why, in our setting the canonical gradient, which we also refer to here as the natural gradient to match optimization terminology, is the projection of the advantage onto the tangent space.

Read the complete text