Adversarial Bandits with Knapsacks
Offered By: IEEE via YouTube
Course Description
Overview
Explore the concept of Adversarial Bandits with Knapsacks in this 21-minute IEEE conference talk. Delve into dynamic pricing, prior work on Stochastic BwK, and various feedback models. Examine the main results, challenges, and reasons behind the complexity of BwK and Adversarial BwK. Learn about linear relaxation, Lagrange games, and the main algorithm (MAIN). Discover regret bounds, simple algorithms, and the differences between high-probability and adaptive adversary scenarios. Conclude with extensions and potential future work in this field.
Syllabus
Intro
(Motivation) Dynamic Pricing
Bandits w/ Knapsacks (BWK)
Prior Work - Stochastic BwK
Background: Feedback Models
Main Result
Why is BwK hard?
Why is Adversarial BwK harder?
Benchmark
Overview
Linear Relaxation
Lagrange Game
a: Main algorithm (MAIN)
Step 3b: Learning in Games
Regret Bound
Challenges
Simple Algorithm
High-prob. v/s Adaptive Adversary
Extensions
Future Work
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube