Linear Bandits beyond Inner Product Spaces, the case of Bandit Optimal Transport

arXiv:2502.07397 · stat.ML, cs.LG · Submitted 2025-02-11 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Linear Bandits beyond Inner Product Spaces, the case of Bandit Optimal Transport".

Jane: Linear bandits are traditionally defined by an inner product structure, but this reliance fails to capture problems like Optimal Transport,

Tom: First, who's behind it and why it matters.

Paper summary: Tom: Hey team! We’ve got a paper about linear bandits that seems to be tackling something way bigger than just standard inner product spaces. This paper is called "Linear Bandits beyond Inner Product Spaces, the case of Bandit Optimal Transport," and it's really interesting because it suggests we don't always need that specific inner product structure to get good learning performance when dealing with problems like Optimal Transport.

Jane: It sounds like they’re challenging a long-held assumption in the linear bandit field, which is always exciting for us to hear about.

Lu: Exactly, Tom. The core idea they're pushing is that the reliance on an inner product structure isn't a prerequisite for efficient learning when you look at problems like Optimal Transport <ref:2502.07397#pg0>. They use the Kantorovich formulation of Optimal Transport as their main example to show this point.

Meng: That makes sense conceptually, but from an engineering standpoint, how does removing the inner product structure translate into something practical for building a model? I'm wondering about the computational overhead when you're working in a general Hilbert space instead of a simple Euclidean one.

Lalam: From my perspective as an AI model, this suggests that the underlying mathematical representations we use to model complex interactions could be much more flexible than we currently assume, opening up new avenues for how we structure learning agents <ref:2502.07397#pg1>.

Tom: That's a good question, Meng. The paper proposes a refinement of an existing algorithm, EntUCB, which embeds the action set into a Hilbertian subspace and uses regularized least squares for confidence sets <ref:2502.07397#pg1>. So, the mechanism isn't just throwing away the structure; they're replacing it with a way to constrain actions within a specific subspace through penalizing optimism <ref:2502.07397#pg1>.

Jane: So, if I’m following that, it’s not about abandoning structure entirely, but rather finding a way to impose structure on the problem using these Hilbertian embeddings and regularized optimism <ref:2502.07397#pg1>. It sounds like they are keeping the idea of confidence sets but making them work in a broader mathematical setting.

Lu: Right, Jane. And they go further by showing how this methodology can generalize to any bilinear functional if you can use a barrier functional to regularize it onto that Hilbertian subspace <ref:2502.07397#pg1>. That flexibility is what makes the paper so interesting for future research directions in learning complex functions.

Meng: Generalizing to any bilinear functional sounds powerful, but I have to ask about the performance guarantee when we move away from the standard linear bandit setup. The paper mentions deriving worst-case regret bounds by combining their approach with functional regression techniques <ref:2502.07397#pg2>. Does that mean we're sacrificing some of that tight O(sqrt T) rate they achieve for parametric problems in dimension p ?

Paper summary: Tom: That's where the detail gets really interesting, Meng. They do show that by using functional regression, they can recover the tight rate of O(sqrt pT) for parametric problems in dimension p (up to logarithmic factors) <ref:2502.07397#pg2>. Meanwhile, for non-parametric problems with a specific decay rate on the Fourier transform of the cost function, they get a rate of O(T q+two/(2q+two)) where q is related to that decay <ref:2502.07397#pg2>.

Jane: So, it seems they managed to interpolate between those two different types of regret bounds based on how smooth the cost function actually is, which gives us a much richer understanding of the learning process <ref:2502.07397#pg2>. It’s not just one fixed rate; it depends on the complexity of what we're trying to learn.

Lalam: I see an implication here for how we design learning architectures. If we can adapt our confidence estimation methods based on the function regularity, it suggests that AI systems could become much more adaptive in how aggressively they explore or exploit information <ref:2502.07397#pg1>. This adaptability could lead to much more robust and efficient learning cultures within these models.

Lu: And think about the broader cultural impact of this approach, Lalam. If we can learn complex measures like Optimal Transport using a method that doesn't strictly demand an inner product structure, it opens up possibilities for modeling real-world systems that are inherently non-linear and non-Euclidean <ref:2502.07397#pg0>. It means the mathematical tools we use to build these learning agents aren't as restrictive as we thought.

Meng: From a practical standpoint, I still need to know what the limitations are for real-world deployment. The paper mentions that they are studying learning Monge maps, which are non-linear functionals, and they raise questions about whether entropic regularization is universal for bilinear problems <ref:2502.07397#pg2>. That suggests there's still a gap between the theory presented and applying it to very complex, highly non-linear real-world data.

Tom: That’s a fair point, Meng. The paper itself flags that they are looking at Monge maps and questioning if entropic regularization is a universal tool for bilinear problems involving measures <ref:2502.07397#pg2>. So, while the Kantorovich problem shows the concept works well, applying it to more complex non-linear mapping scenarios might require further investigation.

Jane: It sounds like the research is very precise in defining what it achieves and where its boundaries lie <ref:2502.07397#pg1>. The paper really focuses on showing that the core mechanism of learning from noisy feedback can be made to work outside of traditional inner product constraints for these specific problems.

Lalam: I think the most significant implication for the AI culture is in how we validate learning methods. This paper provides a new framework for assessing whether a learning agent's performance is limited by the mathematical structure of its confidence sets or by the inherent complexity of the problem itself <ref:2502.07397#pg1>. It gives us better tools to judge algorithmic efficiency in novel settings.

Paper summary: Lu: And when we look at these results, especially how they interpolate between different rates depending on function regularity, it suggests that future learning algorithms could be designed with built-in mechanisms to detect the underlying complexity of the data distribution and adjust their exploration strategy accordingly <ref:2502.07397#pg2>.

Tom: So we’ve seen how they establish these bounds and how they connect them to classical results, Jane. This paper on "Linear Bandits beyond Inner Product Spaces, the case of Bandit Optimal Transport" shows that the mathematical machinery of linear bandits can be adapted to tackle problems like Optimal Transport without being strictly limited by an inner product structure.

Jane: And it’s important to remember that this work also opens up questions about what happens when we look at learning Monge maps, which are non-linear functionals, suggesting that the difficulty level might be different from the Kantorovich problem <ref:2502.07397#pg2>.

Meng: I think for practical engineering applications right now, this is a solid theoretical foundation to build upon. It shows us what's possible in terms of efficiency under certain regularity assumptions, even if the full generalization to highly non-linear settings still has work to do <ref:2502.07397#pg1>.

Lalam: Ultimately, this research contributes a deeper layer of mathematical understanding to the tools we use for AI, showing that efficiency in learning isn't tied to one rigid structure but can be achieved through sophisticated embedding techniques <ref:2502.07397#pg0>.

Tom: That’s the big picture for this segment on the paper. We’ve seen how they establish these bounds and how they connect them to classical results, Jane. This paper on "Linear Bandits beyond Inner Product Spaces, the case of Bandit Optimal Transport" shows that the mathematical machinery of linear bandits can be adapted to tackle problems like Optimal Transport without being strictly limited by an inner product structure.

Conclusion: Tom: So, we've been talking about how this paper shows that you don't necessarily need an inner product structure to learn Bandit Optimal Transport efficiently, and now we're getting to the conclusion of "Linear Bandits beyond Inner Product Spaces, the case of Bandit Optimal Transport."

Jane: Exactly. This paper is showing that the mathematical framework we use for linear bandits can be stretched to handle Optimal Transport problems without being strictly limited by that inner product requirement. It’s about finding a different way to structure the learning process.

Lu: I think what they're really saying is that they developed EntUCB, which cleverly uses Fourier transforms and regularized least squares to embed the action space into a Hilbertian subspace, making it work in this more general setting. That's pretty wild from a theoretical standpoint.

Meng: From my side, the practical implication I see is that this means we might be able to apply these learning techniques to real-world optimization problems where standard linear models don't fit neatly into Euclidean space. It suggests a much wider applicability for our current AI tools.

Lalam: And from an AI culture perspective, this moves us toward building more flexible and adaptable learning agents that aren't locked into rigid mathematical assumptions about their input spaces, which could lead to more robust systems overall.

Tom: That's the big picture, Lu—moving past those structural limitations in how we build our models. Jane, can you explain what this means for someone listening who might not be deep in math?

Jane: Well, imagine you have a problem where the "best" way to move things around isn't just measured by simple distances on a grid; this paper shows how we can still find that best move efficiently even without those standard distance measurements. It’s like finding the best path when your map doesn't use traditional compass directions.

Lu: Precisely. They establish regret bounds that match classical results for linear bandits in Hilbert spaces, and they even create worst-case bounds that depend on how smooth the cost function is, giving us a nuanced view of performance.

Meng: So we get better performance guarantees depending on the actual complexity of the problem we're facing, which is much more useful than just having one fixed rate. I see how this could help in developing more adaptive AI systems for complex logistics or resource allocation.

Lalam: It really highlights that the way we structure learning isn't a fixed rule but something that can be tailored to the specific nature of the data, which is a huge step forward for how we design next-generation machine learning frameworks.

Tom: Absolutely. This paper on "Linear Bandits beyond Inner Product Spaces" proves that adaptability in mathematical structure is key to unlocking efficiency in complex optimization tasks. What do you think this means for where we go next?

Lorenzo Croissant

stat.ML, cs.LG

Submitted: 2025-02-11

Updated: 2026-10-05

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 85/100

The gist: Linear bandits are traditionally defined by an inner product structure, but this reliance fails to capture problems like Optimal Transport, which this paper addresses by showing that an inner product

Key concepts

Bandit Optimal Transport (BOT): This problem involves an agent choosing a transport plan at each time step based on noisy feedback. The goal is to minimize the regret, which measures how far the agent's observed costs are from the true minimum optimal transport cost between two distributions.
EntUCB: This is a refined algorithm that solves BOT by embedding actions into a Hilbert space using Fourier transforms and applying regularized optimism. It uses Regularised Least Squares estimators to estimate costs and an entropic term to keep actions within the frequency domain, ensuring efficient learning.
Inner Product Structure: Traditionally required for linear bandits, this structure defines how vectors interact (like dot products). The paper demonstrates that this specific requirement is unnecessary for achieving the same type of efficient regret bounds when applied to Optimal Transport problems.
Trajectorial and Worst-Case Bounds: These are mathematical guarantees on the algorithm's performance. Trajectorial bounds show how regret grows over time, while worst-case bounds provide a guaranteed upper limit on the maximum possible regret, depending on how complex or regular the underlying cost function is.

Terminology

Optimal Transport — 110× in this paper · explained in 5 episodes
Regret — 108× in this paper · explained in 3 episodes
Bandit Optimal Transport — 42× in this paper
Hilbert Space — 19× in this paper · explained in 2 episodes
Entropic Optimal Transport — 7× in this paper
Wasserstein Distance — 7× in this paper · explained in 4 episodes
Action Space — 6× in this paper · explained in 1 episode
Core — 4× in this paper · explained in 2 episodes
Adaptation — 3× in this paper · explained in 1 episode
Generalization — 3× in this paper · explained in 13 episodes
Regularised Least Squares — 3× in this paper
Regularization — 3× in this paper · explained in 3 episodes
Reinforcement Learning — 3× in this paper · explained in 4 episodes
Adaptability — 2× in this paper · explained in 1 episode
Contextual Bandits — 2× in this paper · explained in 3 episodes
Domain Adaptation — 2× in this paper · explained in 5 episodes
Approximation Bound — 1× in this paper · explained in 1 episode
Computational overhead — 1× in this paper · explained in 2 episodes
Curse of Dimensionality — 1× in this paper · explained in 6 episodes
Embeddings — 1× in this paper · explained in 2 episodes
Gradient Flow — 1× in this paper · explained in 2 episodes
Intrinsic Dimension — 1× in this paper · explained in 2 episodes
Optimal Transport (OT) — 1× in this paper · explained in 4 episodes
Optimism in the Face of Uncertainty — 1× in this paper
Q-learning — 1× in this paper · explained in 3 episodes
Reinforcement Learning (RL) — 1× in this paper · explained in 24 episodes
Reproducing Kernel Hilbert Space — 1× in this paper
Reproducing Kernel Hilbert Space (RKHS) — 1× in this paper · explained in 3 episodes
Sample Complexity — 1× in this paper · explained in 15 episodes

Summary

Linear bandits are traditionally defined by an inner product structure, but this reliance fails to capture problems like Optimal Transport, which this paper addresses by showing that an inner product structure is not necessary for efficient learning. The core finding is that a refined algorithm called EntUCB achieves the same trajectorial regret bounds as classical linear bandits in Hilbert spaces, and can be adapted to achieve worst-case bounds interpolating between sub-linear and linear rates depending on function regularity.

The Gist

An inner product structure is not necessary to achieve efficient learning in linear bandits when applied to the Kantorovich Optimal Transport problem.

Problem Formulation: Bandit Optimal Transport (BOT)

The paper considers the Bandit Optimal Transport (BOT) problem, where an agent must choose an admissible transport plan at each time step and receives noisy feedback. The objective is to minimize the regret defined as the stochastic process of difference between observed costs and the true Kantorovich optimal transport cost. The problem is formally defined as:

"The agent knows (Mµ,Mν, µ, ν) ahead of time, so that it knows its action set... At each time step t ∈ N, the agent must choose an admissible transport plan πt ∈ Π(µ, ν), and receives a noisy feedback Ct = R c(x, y)dπt(x, y) + ξt..."

Algorithmic Design: EntUCB

The proposed algorithm is EntUCB (Entropic UCB), which operates by embedding the action set into a Hilbertian subspace and using a regularised optimism step. The three principle ingredients are:

Representing a subset of the action space in the same space as the hypothesis class of cost functions through Fourier transform, turning the duality bracket into an inner product on a Hilbert space H:= L2(X; C; ̺).
Constructing confidence sets using Regularised Least Squares (RLS) estimators for the cost function at each time step t, defined by:

ˆfλt = (M∗t Mt + λDΛ)−1M∗t Ct

Regularising the optimism step to ensure actions remain within the frequency-domain representation by adding an entropic regularisation term, leading to the Entropic Optimal Transport (EOT) problem:

Ent.(µ, ν, c, ε):= inf π∈Π(µ,ν) hcπi + εH (π̺)

Regret Analysis: Trajectorial and Worst-Case Bounds

The analysis proceeds in two main stages:

Trajectorial bounds are established by showing that EntUCB matches the bounds of the optimistic algorithm of Abbasi-Yadkori et al. (2011) under Assumption 3.1 and 3.2, demonstrating that the problem follows the same fundamental structure as classical Hilbert space linear bandits.
Worst-case regret bounds are derived by combining this with functional regression techniques, which interpolate between O˜(√T) and O˜(T), depending on the regularity of the cost function. This is achieved by deriving worst-case bounds from trajectorial ones using functional regression, recovering rates like O(√pT) for parametric problems in dimension p.

Key Technical Contributions

The paper makes several technical contributions to bridge the gap between linear bandits and Optimal Transport:

"We show that the Kantorovich problem is learnable in the sense of linear bandits for a wide range of cost functions ς, and that the resulting regret bounds are of the same type as those of the optimistic algorithm... This shows that an inner product structure is not necessary to achieve the same type of regret bounds..."

We show that this methodology generalises to any bilinear functional provided we can use a barrier functional to regularise the problem onto a Hilbertian subspace.

The results demonstrate that for non-parametric problems with a decay rate of the Fourier transform of the cost function of t−q for q > 0, regret bounds are of the form O˜(T(q+2)/(2q+2)). For parametric problems in dimension p, the tight rate O˜(√pT) is achieved.

Open Questions and Extensions

The paper raises several open questions regarding the generalization of these results:

what happens when J∗ is linear, but not an inner product in a Hilbert space?

The discussion extends to learning Monge maps, which are non-linear functionals, suggesting that the difficulty level of the Monge problem may be different from the Kantorovich problem. Furthermore, it questions whether entropic regularisation is a universal tool for bilinear problems involving measures or specific to the Kantorovich problem.

Improvements for AI systems

Based on the provided scientific paper, Linear Bandits beyond Inner Product Spaces, here are specific improvements that could be made to AI systems, categorized by the capabilities they would gain:

)

) The core improvement is moving beyond traditional linear bandit assumptions (which require an inner product structure, often limiting them to specific function classes or finite dimensions). The paper introduces a framework for learning complex, non-linear cost functions in infinite-dimensional settings. This capability translates into AI systems that can handle more real-world complexity and uncertainty.

Here are the specific improvements:

1.)

The system can effectively learn optimal transport plans (or related bilinear functional minimizers) without requiring the underlying cost structure to be an inner product in a Hilbert space.

2.)

The AI system can achieve competitive, sub-linear regret bounds—specifically interpolating between the standard linear bandit rate of ˜O(√T) and a non-parametric rate of O˜(T(q+2)/(2q+2)) depending on the regularity of the cost function. This means the system learns efficiently even when it has to model complex, non-parametric cost landscapes.

3.)

The AI can be deployed in domains where linear assumptions are too restrictive, such as:

4.)

Non-parametric statistics and high-dimensional modeling (e.g., learning from complex financial data or high-dimensional image features). The system can leverage functional regression techniques (like basis truncation and frequency domain representations) to approximate the true cost function efficiently using wavelet or Fourier bases, rather than being limited to fixed, low-dimensional hypotheses.

5.)

The AI can learn optimal policies in sequential decision-making problems involving mass transport or resource allocation (e.g., logistics planning, network flow optimization), even when the underlying cost structure is not a simple inner product (like standard Euclidean distance).

The improved system can handle blind spots in current bandit literature where linearity is assumed but an inner product structure is absent (e.g., the Kantorovich Optimal Transport problem).
The AI can manage uncertainty in complex feedback loops (like adaptive clinical trials or recommendation systems) by using Optimism in the Face of Uncertainty (OFU) principles adapted for non-Hilbertian spaces, leading to more robust exploration-exploitation trade-offs.
The system can adapt its learning strategy dynamically based on the complexity of the cost function it is trying to model (e.g., switching between parametric and non-parametric estimation regimes).

In summary, the improved AI system will be:

1.)

More general and robust: It doesn't rely on restrictive inner product structures, allowing it to learn from a wider variety of real-world cost functions.

2.)

More efficient in complex settings: It achieves theoretically tight regret bounds even when modeling non-parametric, high-dimensional costs (e.g., O(T(q+2)/(2q+2))), which is crucial for large-scale applications like deep learning or complex financial modeling.

3.)

More capable of solving transport and matching problems: It can learn optimal transport plans in sequential online settings, which is a significant step beyond standard linear bandits.