Research map / Bandits and online learning / Online convex optimization and games
Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time
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.
Gives robust dynamic pricing algorithms, a robustified binary search with safety checks and backtracking, achieving regret O(C+log T) with known corruption and O(C+log^2 T) with unknown corruption.
Problem
Dynamic pricing with binary sale/no-sale feedback where an adversary corrupts up to C feedback rounds; prior best regret O(C log log T) left open whether C and T can be decoupled.
Approach
A robust binary search over a discretized price tree, with per-node safety checks at interval endpoints and backtracking on inconsistency; known-C commitment uses a counter threshold C+1, while unknown-C commitment randomly probes the right endpoint with probability decaying as 4ln(T/δ)/s.
Key results
- Known-corruption robust pricing achieves regret O(C+log T) via robust binary search plus commit to left endpoint (total bound 5 log T + 19C + 3).
- Unknown-corruption algorithm with randomized commitment achieves regret O(C + log T log(T/δ)) with probability 1-δ, i.e., O(C+log^2 T).
- Regret lower bound Ω(C) holds for any deterministic algorithm even when C is known.
Surprising findings
- Any deterministic algorithm suffers Ω(C) regret even with known C, so linear dependence on C is unavoidable.
Limitations
- Unknown-corruption bound O(C+log^2 T) may not be tight; tightness is open.
- Analysis restricted to one-dimensional pricing; contextual extension left open.
- Commitment-phase analysis relies on high-probability events with union bounds over leaves.
Experimental setup
Metrics: cumulative regret
Baselines: O(C log log T) robust pricing algorithm of prior work O((C+log T) log log T) bound for unknown corruption
Builds on: robust binary search with erroneous answers (Rivest et al.) cautious-buyer robust pricing log log T dynamic pricing (Kleinberg-Leighton)
Closest papers by meaning
- Robust Contextual Pricing (NeurIPS 2025 · similarity 0.91)
- Dynamic Incentive-Aware Learning: Robust Pricing in Contextual Auctions (NeurIPS 2019 · similarity 0.90)
- Dynamic Pricing and Learning with Bayesian Persuasion (NeurIPS 2023 · similarity 0.88)
- Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions (ICML 2025 · similarity 0.87)
- Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand (NeurIPS 2026 · similarity 0.86)
- Improved Algorithms for Contextual Dynamic Pricing (NeurIPS 2024 · similarity 0.86)
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.