Mathematics of Online Decision Making 2020
2020-10-23..2020-10-30
-- online --
[Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016), Quantifying Uncertainty: Stochastic, Adversarial, and Beyond, Multi-Agent Reinforcement Learning and Bandit Learning, Adversarial Approaches in Machine Learning 2022, Data-Driven Decision Processes Boot Camp 2022, Algorithmic Game Theory and Practice 2015]
| title | author | length |
|---|---|---|
| Online Multiserver Convex Chasing and Optimization | Yuval Rabani | 33m |
Shows a constructive reduction that turns online k-means into a k-server style procedure and yields an order k^2 competitive algorithm (uses an order-k… | ||
| Multi-Task Optimal Experiment Design | Steffen Grunewalder | 31m |
Shows that pooling samples with the maximum likelihood / least-squares estimator gives zero improvement at epoch-2 design points unless the subspaces overlap… | ||
| Selfish Robustness and Equilibria in Multi-Player Bandits | Vianney Perchet | 37m |
Claims that decentralized protocols recover the centralized regret rate under full or statistical sensing even if one agent acts selfishly, and proves… | ||
| Pure Exploration Problems | Wouter Koolen | 29m |
Defines fixed‑confidence, instance‑dependent pure exploration where sample complexity scales like f(mu)·log(1/δ) and gives an information‑theoretic lower bound… | ||
| Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale | Lillian Ratliff | 31m |
Claim: gradient descent–ascent with a constructed finite tau_star provably makes the only locally attracting fixed points the strict local minimax (local… | ||
| Learning Outcomes in Queueing Systems | Eva Tardos | 29m |
Queues arrive at rate λ, choose one server per round, and run no-regret learning while servers serve one random or timestamp-prioritized packet per round. Main… | ||
| Pandora's Box with Correlations: Learning and Approximation | Shuchi Chawla | 34m |
Shows that with only sample access to an unknown joint distribution over costs it is possible to learn a partially adaptive probing policy that is provably… | ||
| Regret Minimization for Stochastic Shortest Paths | Yishay Mansour | 31m |
Yishay Mansour (Tel Aviv University)
Regret Minimization for Stochastic Shortest Paths
Mathematics of Online Decision Making | ||
| Robust Algorithms for Secretaries and Bandits | Anupam Gupta | 33m |
Algorithm works on a red/green model where an unknown fraction of items are adversarially timed and values are arbitrary while the rest arrive uniformly at… | ||
| The Non-Stochastic Control Framework | Naman Agarwal | 34m |
Provides an efficient algorithm for known, fully observed linear time invariant systems with adversarial bounded disturbances that guarantees O(√T) regret… | ||
| Competitive Algorithms for Online Control | Yisong Yue | 41m |
Presents a reduction from LQR-style problems (input-disturbed squared regulator) to a new online convex optimization with structured memory, then designs an… | ||
| A Unifying View of Optimism in Episodic Reinforcement Learning | Ciara Pike-Burke | 28m |
Claim: the optimization solved by model‑optimistic RL (optimize p in a confidence set) is the Lagrangian dual of a value‑optimistic dynamic program, so every… | ||
| On the Complexity of Learning Good Policies With and Without Rewards | Emilie Kaufmann | 31m |
Proposes a model-based UCB algorithm called RF-UCRL that estimates transitions from visit counts and drives exploration by maximizing a data-dependent upper… | ||
| Model-Based Reinforcement Learning with Value-Targeted Regression | Mengdi Wang | 36m |
Proposes using value-targeted regression: fit transition models only to predict next-step value estimates, then build confidence sets over models and do… | ||
| A Generalization Bound for Online Variational Inference | Pierre Alquier | 36m |
Proposes two sequential variational updates called SVA and SVB and proves regret bounds matching Bayesian online guarantees under convexity and… | ||
| Beating the Curse of Dimensionality in High-Dimensional Optimal Stopping | David Goldberg | 36m |
Claims a closed-form infinite sum representation of the optimal stopping value and shows truncating after K terms yields a tight error ≤ 1/K guarantee for… | ||
| Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization | Negin Golrezaei | 41m |
Framework converts offline greedy procedures into online learners for NP‑hard combinatorial rewards by treating each greedy stage as a Blackwell game and… | ||
| Country-Scale Bandit Implementation for Targeted COVID-19 Testing | Hamsa Bastani | 32m |
Implemented a country-scale testing system called AVA that uses an optimistic Gittins-style index with pseudo-Gittins indices (certainty-equivalent updates)… | ||
| Multi-Player Multi-Armed Bandit: Can We Still Collaborate at Homes Without "Zoom"? | Yuanzhi Li | 32m |
Models non-stochastic (oblivious adversary) multi-player bandits and gives concrete algorithms: one uses a low-switching leader plus exploration by the… | ||
| Multiplayer Bandit Learning - From Competition to Cooperation | Simina Branzei | 28m |
Two-player bandits compare safe arm p to a risky arm with prior μ and Gittins index g. Competitive play reduces exploration: there is a threshold p_star < g so… | ||
| Representation Learning and Exploration in Reinforcement Learning | Akshay Krishnamurthy | 30m |
Describes two concrete algorithms: HOMER uses a contrastive supervised reduction to decode a latent Block MDP into a tabular state space and explores with… | ||
| Corruption Robust Exploration in Episodic Reinforcement Learning | Aleksandrs Slivkins | 29m |
Proposes algorithms for episodic RL under an adversarial corruptions model where an unknown number C of whole episodes can be arbitrarily altered; main… | ||
| On the Global Convergence and Approximation Benefits of Policy Gradient Methods | Daniel Russo | 35m |
Shows that gradient descent on parameterized policies avoids suboptimal stationary points when two concrete conditions hold: the policy class is closed under… | ||
| An Alternative Softmax Operator for Reinforcement Learning | Michael L. Littman | 31m |
Introduces the Mellowmax (mellomax) operator: log of the average of e^{omega·Q}/omega (a softened Boltzmann-style average) and proves it satisfies a… | ||
| What Are the Statistical Limits of Offline Reinforcement Learning With Function Approximation? | Sham Kakade | 55m |
Assumes linear Q realizability and spectral coverage and then proves an information-theoretic lower bound: any offline algorithm can require about D^{H/2}… | ||
| nothing matches | ||