A (stochastic) bandit problem is, at its heart, an optimisation problem under uncertainty. An agent wishes to minimise some objective function $g:\Ab\to\Rb$, which is unknown to them. They can however query it sequentially at points $a_1,\ldots,a_n\in\Ab$, but crucially only observe noisy values of the function at these points, i.e. they observe $y_i = g(a_i) + \xi_i$ where $\xi_i$ is some noise. These problems exhibit 3 key properties.
Partial information: the agent only observes the value of $g$ at the points they query, and with noise.
Interactivity: the data is chosen by the agent, rather than received exogenously like in supervised learning. As a consequence, the agent must explore the space $\Ab$ to gather statistical information about $g$. This exploration will introduce long-range dependencies between the data points, which makes the statistical analysis more complex.
Evaluation through regret: the agent's performance is evaluated through their regret, i.e. the difference between the cumulative value of $g$ at the points they queried, and the cumulative value of $g$ at its optimum. This is a more stringent criterion than classical statistical ones, as it requires both optimisation and statistical efficiency.
Evaluation through regret forces the agent to exploit its knowledge of $g$ as it goes, which comes in tension with the need to explore the space $\Ab$ to learn about $g$. This exploration-exploitation tradeoff is the heart of bandit problems.
Because bandits are static, i.e. the function $g$ does not depend on time, they are often used to study reinforcement learning by stripping away the control component, while retaining most of the statistical complexity. Bandits have a well-documented history going back to the 1930s, which I won’t recount here.
What this project is interested in is the interplay between optimisation and statistics in bandit problems, and in particular I’m interested in situations where $\Ab$ is continuous and possibly infinite-dimensional. From a classical-statistics point of view, this isn’t much of an issue, non-parametric statistics is a well-developed field afterall. However, the interplay with optimisation and the nature of regret evaluation muddies this picture. I believe these corner case questions can teach us a lot about the core nature of bandit problems, and more generally of reinforcement learning, which is why I study them. Below are some of the topics on which I’ve worked in this vein.
Bandits Optimal Transport
Optimal Transport (OT) is a mathematical theory which studies the problem of transforming one probability distribution into another in an optimal way. It has found applications in many fields, principally logistics and economics more broadly, but also in machine learningFor economics see the survey Galichon et al. (2021), for machine learning, see e.g. Salimans et al. (2018).. Let $\mu,\nu$ be two probability distributions on $\Rb^d$, and $c^*:\Rb^d\x\Rb^d\to\Rb_+$ a cost function. The Kantorovich OT problem, named after its formaliser, see Kantorovich (1960), consists in finding a couplingI.e. a joint probability measure with marginals $\mu$ and $\nu$ over its first and second arguments, respectively. $\pi$ between $\mu$ and $\nu$ which minimises the expected cost of transporting mass from $\mu$ to $\nu$, i.e. \[ \inf_{\pi\in\Pi(\mu,\nu)}\int c^*(x,y)\pi(\de x,\de y), \] where $\Pi(\mu,\nu)$ is the set of couplings between $\mu$ and $\nu$.
This problem is interesting beyond its applicability because it lies in a very complex optimisation space, but is also highly regular, see e.g. Villani (2008) for a comprehensive treatment. The interesting question from a statistical standpoint is whether we can exploit this regularity, and this is what this paper aims to answer.
What does a Bandit Optimal Transport (BOT) problem look like? The agent knows $\Ab:=\Pi(\mu,\nu)$, but ignores the cost function $c^*$. They can query transport plans $\pi_1,\ldots,\pi_n\in\Ab$, and observe noisy values of the cost \[ y_i = \int c^*(x,y)\pi_i(\de x,\de y) + \xi_i \]
where $\xi_i$ is some noise. Since the functional $g:\pi\to\int c^*\de \pi$ is linear, this is an instance of the well-studied linear bandit problem, see the reference treatment in Abbasi-Yadkori et al. (2011).
However, this is where the corner case comes in: the space $\Pi(\mu,\nu)$ is not a Hilbert space, and in fact is quite complex geometrically, there is no good way to put into an inner product structure with a hypothesis class on the cost $c^*$. This turns out to be a key issue, as it breaks the careful infinite-dimensional analysis of Abbasi-Yadkori et al. (2011), which crucially relies on an inner-product structure. This begs the question, is linearity not sufficient to obtain good regret bounds in infinite dimension? Is the name linear bandits a misnomer?
While a definitive negative answer is not yet established, I have shown that the BOT problem is learnable with sub-linear regret, interpolating all the way from $\Oc(\sqrt{n})$ regret in finite dimension to $\Oc(n)$ in unlearnable instances. The interpolation is obtained through the use of infinite-dimensional statistics tools, in particular functional-regression. See Croissant (2025) for details.