Lipschitz Contextual Bandits

Lipschitz Contextual Bandits

Lipschitz contextual bandits are contextual bandit problems where contexts and actions live in metric spaces, and similar context-action pairs are assumed to have similar expected rewards.

Key points

  • Lu, Pál, and Pál model sponsored search as a Lipschitz contextual multi-armed bandit: search queries are contexts, ads are actions, and click-through rate is the unknown payoff function [src-020].
  • The model assumes a metric over queries and a metric over ads. The expected payoff changes smoothly with respect to each metric, so similar queries for the same ad and similar ads for the same query should have close rewards [src-020].
  • This makes the problem richer than a context-free bandit. The learner must generalise across both context similarity and action similarity instead of treating every query-ad pair as unrelated [src-020].
  • The paper allows query sequences to be fixed in advance by an oblivious adversary, so the setting is not merely IID personalisation [src-020].
  • Regret depends on the geometric complexity of the query and ad spaces: upper bounds use covering dimensions; lower bounds use packing dimensions [src-020].

Related entities

_(none yet)_

Related concepts

Source references

  • [src-020] Tyler Lu, David Pál, Martin Pál — “Contextual Multi-Armed Bandits” (AISTATS 2010)

Robin Cartier perspective

This page is part of Robin Cartier's working AI knowledge graph: a practical research layer for production AI, recommendation systems, experimentation, GEO, and agentic web readiness.

The useful next step is to connect this concept back to applied product leadership and operating models.

Recommended next

Keep reading from this thread

From 491 indexed pages and articles.

  1. Wiki concept Contextual Bandits Bandit problems where each decision arrives with observable context, and the algorithm learns which actions work best for which contexts from Related by contextual
  2. Wiki concept Multi-Armed Bandits A framework for algorithms that make repeated decisions under uncertainty, learning from partial feedback while balancing exploration of uncertain actions against Related by contextual
  3. Insight Recommendation Systems in Production How recommendation systems become production decisioning systems through signals, ranking, constraints, feedback loops, and experimentation Readers have engaged with this next