Decision Making and Optimization under Uncertainty

Time/Place: Thursday 2-3pm at KACB 2108.

Presenting:  If you are interested in presenting one of these papers or a related one, please email me.

Theme:  Theoretical modeling and algorithms with provable guarantees for various optimization problems arising in decision making under uncertainty. This collection is by no means exhaustive, and is biased by my personal viewpoint of the area. If you have other suggestions, please email me.

Schedule:

08/21: (Kamesh Munagala) A short proof of the Gittins index theorem
09/04: (Kamesh Munagala) Sequential design of experiments via linear programming
09/18: (Georgios Kotsalis)  Optimal auction design
09/25: (Gagan Goel)           Auctions vs Negotiations
09/29: (ARC Seminar)        Approximation algorithms for restless bandit problems
10/16: (Kamesh Munagala) Optimal Mechanism Design and Money Burning

TOPIC	ALGORITHMIC TECHNIQUE	PAPERS	DATE	PRESENTER
Multi-armed Bandits (MDP)
	Dynamic Programming	A short proof of the Gittins index theorem	08/21	Kamesh Munagala
	Linear Program Rounding	Sequential design of experiments via linear programming Approximation algorithms for restless bandit problems	09/04 09/29	Kamesh Munagala Kamesh Munagala
Online Learning
	Follow the leader	Finite-time analysis of the multiarmed bandit problem Efficient algorithms for online decision problems
	Gradient descent	Online convex programming and generalized infinitesimal gradient ascent Playing games with approximation algorithms
Inventory Control
	Dual balancing	Approximation algorithms for stochastic inventory control models
	Online algorithms	Online make-to-order joint replenishment model: Primal-dual competitive algorithms
Multi-stage Optimization
	Sampling of scenarios	Sampling bounds for stochastic optimization Boosted sampling:  Approximation algorithms for stochastic optimization
Bayesian Game Theory
	Revenue Maximization	Optimal auction design Auctions vs Negotiations Optimal Mechanism Design and Money Burning	09/18 09/25 10/16	Georgios Kotsalis Gagan Goel Kamesh Munagala
	Markov Decision Processes	Optimal coordinated planning amongst self-interested agents with private state
Robust Optimization
	Linear Program Rounding	Robust combinatorial optimization with exponential scenarios
	Convex Programming	Robust solutions of uncertain linear programs