Research map / Bandits and online learning / Online convex optimization and games
Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the Strategic Littlestone Dimension, which exactly characterizes the instance-optimal deterministic mistake bound for online strategic classification under a known manipulation graph, and extends the agnostic and unknown-graph regret bounds using only post-manipulation features.
Problem
Online binary classification where strategic agents modify features along a manipulation graph and the learner only observes post-manipulation features; prior bounds were not instance-optimal and depended on max out-degree or hypothesis class size.
Approach
A combinatorial dimension (strategic Littlestone dimension) defined via shattered trees with asymmetric false-positive/false-negative branching; a standard-optimal-style algorithm (SSOA) labels nodes based on whether a false-positive observation would reduce this dimension, and an expert-based agnostic reduction guesses in-neighbors to handle unobserved original features.
Key results
- Proves the optimal deterministic mistake bound in the realizable setting equals the Strategic Littlestone dimension SLdim(H,G), with SSOA achieving it.
- Agnostic regret bound O(Δ+·OPT + Δ+·SLdim·(log T + log Δ-)), improving on prior bounds that scale with Δ+·Ldim.
- Unknown graph class realizable setting yields Õ(Δ+·d_G + log|G|) mistake bound, optimal up to log factors per a cited lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Strategic Littlestone Dimension to characterize the optimal deterministic mistake bound | Online strategic classification in the realizable setting · Realizable online strategic classification | min-max optimal mistakes | Helped |
| Use SSOA, whose mistake bound is the Strategic Littlestone Dimension | Online strategic classification in the realizable setting · Realizable online strategic classification | mistakes | Helped |
| Replace the max-degree-based bounds with the Strategic Littlestone Dimension bound | Online strategic classification on a complete graph over an unbounded domain · Complete graph on an unbounded domain | mistake bound: \infty -> 1 | Helped |
| Use the Strategic Littlestone Dimension bound instead of the reduced-class max-degree bound | Online strategic classification on G(n,p), with p=\omega(1/n) · Random graph G(n,p), \mathcal{H}=\{\pm1\}^{n} | mistake bound: \Omega(n\log (np)) -> n | Helped |
| Use representative experts that guess manipulation directions and Biased Weighted Majority Vote | Agnostic online strategic classification with post-manipulation observations · Agnostic online strategic classification | regret | Helped |
| Use graph-specific experts and the union graph for voting | Online strategic classification with an unknown but realizable graph class · Realizable graph classes | regret | Helped |
Surprising findings
- Randomized learners can have a super-constant gap versus deterministic learners in strategic settings, unlike the classical case where they differ by a factor of 2.
Limitations
- Agnostic regret retains an extra Δ+ factor relative to the lower bound Ω(SLdim + Δ+·OPT).
- Results focus on deterministic learners; characterization for randomized learners is open.
Experimental setup
Metrics: mistake bound regret
Baselines: Ahmadi et al. 2023 max-degree bound Ghalme et al. 2021 Red2Online-PMF
Builds on: Littlestone dimension Standard Optimal Algorithm biased weighted majority vote manipulation graph model
Closest papers by meaning
- Online Strategic Classification With Noise and Partial Feedback (NeurIPS 2025 · similarity 0.89)
- Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning (NeurIPS 2025 · similarity 0.86)
- Strategic Classification With Externalities (ICLR 2025 · similarity 0.86)
- Bayesian Strategic Classification (NeurIPS 2024 · similarity 0.85)
- One-Shot Strategic Classification Under Unknown Costs (ICML 2024 · similarity 0.85)
- Strategic PAC Learnability via Geometric Definability (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.