Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
2022-09-12..2022-09-16
Berkeley, United States
[Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016), Mathematics of Online Decision Making 2020, Adversarial Approaches in Machine Learning 2022, Optimization, Statistics and Uncertainty, Learning, Algorithm Design and Beyond Worst-Case Analysis, Real-Time Decision Making 2018]
who it's for
research scientists, algorithm engineers, reinforcement learning researchers, causal inference practitioners, experimentation platform engineers, data scientists, optimization researchers
topics
Brownian information acquisition; search as Brownian path; active sequential hypothesis testing; causal matrix completion; causal tensor completion; marketplace experimentation bias; network interference testing; corruption-robust contextual search; stochastic versus adversarial bandits; offline reinforcement learning robustness; flow time scheduling with uncertainty
| title | author | length |
|---|---|---|
| Dynamically Aggregating Diverse Information | Annie Liang | 54m |
Claims an exact, closed‑form characterization of optimal dynamic information acquisition when K Gaussian attributes are observed via Brownian motion signals… | ||
| Retrospective Search: Exploration and Ambition on Uncharted Terrain | Can Urgun | 44m |
Models search outcomes as a realized Brownian path, lets the agent choose costly variance (search speed) and a stopping time, and fully characterizes the… | ||
| Expert Advice in Complex Environments | Steve Callander | 51m |
Argues that modeling expertise as a realized Brownian motion path rather than a single parameter reverses classic cheap‑talk conclusions: using hitting‑time… | ||
| Greedy Approximation Algorithms for Active Sequential Hypothesis Testing | Kyra Gan | 43m |
Proposes greedy algorithms for active sequential hypothesis testing with approximation guarantees that are independent of the number of actions and grow only… | ||
| Causal Matrix Completion: Applications to Offline Causal Reinforcement Learning | Anish Agarwal | 47m |
Proposes a practical algorithm called synthetic nearest neighbors that combines nearest neighbors and synthetic controls to handle MNAR matrix completion… | ||
| Inference and Interference in Marketplace Experimentation | Hannah Li | 45m |
Claims that marketplace A/B tests suffer both treatment-effect and standard-error bias, quantified in a continuous-time Markov chain model of a two-sided… | ||
| Causal Inference in Complex Systems: Network Interference, Strategic Agents, and Beyond | Panos Toulis | 49m |
Argues that exact, finite-sample Fisher randomization test methods handle network interference by testing exposure contrasts (e.g., control spillovers vs pure… | ||
| Contextual Inverse Optimization: Offline and Online Learning | Ilan Lobel | 43m |
Characterizes offline performance by fitting costs on the unit sphere and computing an uncertainty angle (circumcenter gives the minimax proxy); develops an… | ||
| Corruption-Robust Contextual Search | Chara Podimata | 46m |
Contextual search algorithms become corruption-robust by modeling misbehavior as C corruptions and giving near-optimal regret that scales additively with… | ||
| Best of Both World Algorithms from I.I.D. to Adversarial Data | Julian Zimmert | 38m |
Proposes using Tsallis-Inf FTRL with adaptive learning rates to get both the adversarial sqrt(kT) bound and the stochastic logarithmic regret without extra… | ||
| Best Of Both Worlds: Stochastic & Adversarial Best-Arm Identification | Victor Gabillon | 45m |
Main claim: no single learner can be simultaneously optimal for all stochastic instances and for worst-case adversaries; a lower bound introduces the HBOB… | ||
| Flow Time Scheduling with Uncertain Processing Time | Yossi Azar | 52m |
Presents competitive guarantees when job sizes are only estimated: an distortion-oblivious deterministic algorithm for unweighted flow time with competitive… | ||
| Machine Learning for Faster Optimization | Ben Moseley | 44m |
A model augments classical algorithms with predicted parameters that are provably learnable from past instances and robust to modest input changes. Examples… | ||
| Parsimonious Learning-Augmented Algorithms | Ravi Kumar | 44m |
New results show a sublinear number of predictions suffices for meaningful gains. For online linear optimization a randomized algorithm combines FTRL with a… | ||
| Markov Persuasion Process and its Reinforcement Learning | Haifeng Xu | 46m |
Defines a Markov Persuasion Process where a planner observes the true state, a myopic actor acts on signals, and persuasion is a one-sided information control… | ||
| Attributes: Selective Learning and Influence | Arjada Bardhi | 50m |
Characterizes which K attributes to sample when attribute realizations follow a Gaussian process and two players disagree on attribute weights, using Brownian… | ||
| Incentivized Exploration | Alex Slivkins | 49m |
A planner can provably steer selfish, short‑lived users to explore by withholding history and sending suggestions, formalized as bandits plus Bayesian… | ||
| Information Collection Through Strategic Agents | Marco Ottaviani | 48m |
Papers present concrete game-theoretic models and sharp results: selective reporting of the top of K draws is often more informative than a random draw under… | ||
| Adaptive Monopoly Regulation | Modibo Camara | 50m |
Regulation proves robustly adaptive: using adversarial online learning and new solution concepts (calibration and counterfactual calibration) a simple policy… | ||
| Oracle-Efficient Online Learning or: How to Use Non-Robust Optimization for Robust Learning | Nika Haghtalab | 49m |
Claim: efficient no-regret online learning is possible by reusing a standard ERM oracle rather than redesigning algorithms from scratch, provided the adversary… | ||
| Dynamic Regret Minimization for Bandits without Prior Knowledge | Chen-Yu Wei | 46m |
Shows an algorithm that achieves the optimal dynamic regret bound sqrt(S T) (and the V^{1/3} T^{2/3} regime) without knowing the number of environment changes… | ||
| When Can We Use Weak Function Approximation to Solve Large Scale Planning Problems in MDPs? | Csaba Szepesvári | 52m |
Linear function approximation can be query‑efficient only under tight structural assumptions: with TensorPlan (a variant of optimistic constraint propagation)… | ||
| Adaptivity and Confounding in Multi-armed Bandit Experiments | Daniel Russo | 48m |
Proposes deconfounded Thompson sampling, a simple tweak that samples arms by their posterior chance of being best across the whole population (not just the… | ||
| Generalization and Robustness in Offline Reinforcement Learning | Wen Sun | 54m |
Proposes a model-based offline RL pipeline that fits a transition model by MLE then pessimism (constrain models near the MLE and plan against the worst-case… | ||
| nothing matches | ||