Book contents
- Frontmatter
- Contents
- Preface
- 1 Introduction and Problem Statement
- 2 Overview of Methods and History
- 3 Mathematical Tools
- 4 Bisection in One Dimension
- 5 Online Gradient Descent
- 6 Self-Concordant Regularisation
- 7 Linear and Quadratic Bandits
- 8 Exponential Weights
- 9 Cutting Plane Methods
- 10 Online Newton Step
- 11 Online Newton Step for Adversarial Losses
- 12 Gaussian Optimistic Smoothing
- 13 Submodular Minimisation
- 14 Outlook
- Appendix A Miscellaneous
- Appendix B Concentration
- Appendix C Notation
- References
- Index
7 - Linear and Quadratic Bandits
Published online by Cambridge University Press: 07 March 2026
Book contents
- Frontmatter
- Contents
- Preface
- 1 Introduction and Problem Statement
- 2 Overview of Methods and History
- 3 Mathematical Tools
- 4 Bisection in One Dimension
- 5 Online Gradient Descent
- 6 Self-Concordant Regularisation
- 7 Linear and Quadratic Bandits
- 8 Exponential Weights
- 9 Cutting Plane Methods
- 10 Online Newton Step
- 11 Online Newton Step for Adversarial Losses
- 12 Gaussian Optimistic Smoothing
- 13 Submodular Minimisation
- 14 Outlook
- Appendix A Miscellaneous
- Appendix B Concentration
- Appendix C Notation
- References
- Index
Summary
Function classes like Fb are non-parametric. In this chapter we shift gears by studying two important parametric classes: Fb,lin and Fb,quad. The main purpose of this chapter is to use the machinery designed for linear bandits to prove an upper bound on the minimax regret for quadratic bandits. On the positive side the approach is both elementary and instructive. More negatively, the resulting algorithm is not computationally efficient. Before the algorithms and regret analysis we need three tools: covering numbers, optimal experimental design and the exponential weights algorithm.
Information
- Type
- Chapter
- Information
- Bandit Convex Optimisation , pp. 79 - 93Publisher: Cambridge University PressPrint publication year: 2026
Accessibility standard: WCAG 2.1 A
Why this information is here
This section outlines the accessibility features of this content - including support for screen readers, full keyboard navigation and high-contrast display options. This may not be relevant for you.Accessibility Information
The PDF of this chapter
complies with version 2.1 of the
Web Content Accessibility Guidelines
(WCAG), covering newer accessibility requirements and improved
user experiences and meets the basic
(A)
level of WCAG compliance, addressing essential accessibility barriers.
Content Navigation
Table of contents navigation
Allows you to navigate directly to chapters, sections, or non‐text items through a linked table of contents, reducing the need for extensive scrolling.
Allows you to navigate directly to chapters, sections, or non‐text items through a linked table of contents, reducing the need for extensive scrolling.
Index navigation
Provides an interactive index, letting you go straight to where a term or subject appears in the text without manual searching.
Provides an interactive index, letting you go straight to where a term or subject appears in the text without manual searching.
Reading Order & Textual Equivalents
Single logical reading order
You will encounter all content (including footnotes, captions, etc.) in a clear, sequential flow, making it easier to follow with assistive tools like screen readers.
You will encounter all content (including footnotes, captions, etc.) in a clear, sequential flow, making it easier to follow with assistive tools like screen readers.
Short alternative textual descriptions
You get concise descriptions (for images, charts, or media clips), ensuring you do not miss crucial information when visual or audio elements are not accessible.
You get concise descriptions (for images, charts, or media clips), ensuring you do not miss crucial information when visual or audio elements are not accessible.