Optimization and Uncertainty - Summer 2025

Logbook Optimization and Uncertainty - Summer 2025

Lecture 17 -- 03.06.2025:
Markovian single-armed bandits, definition, charges for play, definition Gittins index, Markovian multi-armed bandits, Gittins index policy, parts of the proof of optimality (Lemmas 19 and 20)
Literature:
- Notes: Section 6.2 (until start of proof of Theorem 30)

Lecture 16 -- 02.06.2025:
Infinite Markov decision processes, definition with discounted rewards, optimal Markovian policy, value iteration, policy iteration, convergence proofs.
Literature:
- Notes: Section 6.1

Lecture 15 -- 27.05.2025:
Delegated search problem, connection to prophet inequalities, median-prophet algorithm, proof of 2-approximation w.r.t. optimal value in the undelegated search problem
Literature:
- Notes: Section 5.2
- J. Kleinberg, R. Kleinberg. Delegated Search Approximates Efficient Search. EC 2018.

Lecture 14 -- 26.05.2025:
Persuasion with IID boxes, construction of LP, rounding algorithm, proof of (1-1/e)^-1-approximation and persuasiveness. Persuasion with independent boxes, SSQ-box, construction of LP, rounding algorithm, proof of 4-approximation and persuasiveness.
Literature:
- Notes: Sections 5.1.1, 5.1.2
- N. Hahn, M. Hoefer, R. Smorodinsky. Prophet Inequalities for Bayesian Persuasion. IJCAI 2020.

Lecture 13 -- 20.05.2025:
Bayesian persuasion, model and example, there is optimal scheme φ^* that is direct and persuasive, computing φ^* via LP for explicitly represented distribution D. IID case: symmetry of φ^* and consequences
Literature:
- Notes: Sections 5.1, 5.1.1
- S. Dughmi, H. Xu. Algorithmic Bayesian Persuasion. STOC 2016.

Lecture 12 -- 19.05.2025:
Probing with opening cost, Pandora's Box problem, fair cap as an estimator of the value of the box after subtracting the opening cost, optimal policy greedily opens boxes in non-increasing order of fair cap
Literature:
- Notes: Section 4.3
- M. Weitzman. Optimal search for the best alternative. Econometrica 47(3):641-654, 1979
- Bo Waggoners Blog Post

Lecture 11 -- 13.05.2025:
Testing, k-TestMax, testing a box = refining the support region in which realization is located, testing vs. probing, testing policy for the IID case that obtains at least 1-1/e^1/4-o(1) of the expected reward of the optimal probing policy
Literature:
- Notes: Section 4.2
- M. Hoefer, K. Schewior, D. Schmand. Stochastic Probing with Increasing Precision. SIAM J. Discrete Mathematics 38(1):148-169, 2024.

Lecture 10 -- 12.05.2025:
Probing, k-ProbeMax, non-adaptive and adaptive policies, adaptivity gap, adaptivity gap for k-ProbeMax is at most 8, bounding the optimum using a linear program, deriving a non-adaptive policy from the LP optimum.
Literature:
- Notes: Section 4.1
- A. Asadpour, H. Nazerzadeh. Maximizing Stochastic Monotone Submodular Functions. Management Science 62(8):2374-2391, 2016.

Lecture 9 -- 06.05.2025:
Online independent set and the interval scheduling problem, prophet interval scheduling, 4-competitive algorithm, proof of the competitive ratio. Secretary independent set with random-order arrival, 8-competitive algorithm, proof by adjusting the arguments for the prophet case. Extensions to more general graphs (bounded inductive independence number) and graph sampling approaches
Literature:
- Notes: Sections 3.4.1, 3.4.2
- O. Göbel, M. Hoefer, T. Kesselheim, T. Schleiden, B. Vöcking. Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods. ICALP 2014.

Lecture 8 -- 05.05.2025:
Yao's principle, given any input distribution, the best deterministic algorithm for that distribution performs better than any randomized algorithm on worst-case input, lower bound of Ω(n) on the competitive ratio of any randomized algorithm for OnlineMax. Online Independent Set, interval scheduling, lower bound Ω(n) on the competitive ratio, Prophet Interval Scheduling, 4-competitive algorithm.
Literature:
- Notes: Sections 3.3, 3.4, 3.4.1
- A. C.-C. Yao. Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). FOCS 1977.
- O. Göbel, M. Hoefer, T. Kesselheim, T. Schleiden, B. Vöcking. Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods. ICALP 2014.

Lecture 7 -- 29.04.2025:
Examples for finite-time MDPs and optimal policies. SkiRental: Buy only on the first open day when there are at least ⌊((B-1)/q)+2⌋ days remaining; Prophet: accept any person as soon as it has more value than the expected value obtained by the optimal policy in the subsequent rounds.
Literature:
- Notes: Section 3.2.2

Lecture 6 -- 28.04.2025:
PrizeCollection problem, definition Markov decision process (MDP), optimal policy π^* for finite time horizon, existence of π^* that is Markovian, computation via a dynamic program (DP), example DP for PrizeCollection, alternative characterization of optimal policy: Open envelopes in non-increasing order of v_iq_i/(1-q_i)
Literature:
- Notes: Sections 3.2, 3.2.1, 3.2.2

Lecture 5 -- 22.04.2025:
OnlineMax with independent distributions, prophet inequalities in the general case, 2-competitive, tightness example; prophet inequality in the identical case, 1.58-competitive, discussion of improved approaches
Literature:
- Notes: Section 3.1
- J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, T. Vredeveld. Recent developments in prophet inequalities. SIGecom Exchanges 17(1):61–70, 2018
- E. Samuel-Cahn. Comparison of threshold stop rules and maximum for independent nonnegative random variables. Annals of Probability 12(4):1213–1216, 1984.

Lecture 4 -- 15.04.2025:
Item Allocation Problem, at least b ≥ 1 copies per item, bundles of size at most d, optimal fractional solution via linear programming, extension of the secretary algorithm is O(d^1/b)-competitive.
Literature:
- Notes: Section 2.4
- T. Kesselheim, K. Radke, A. Tönnis, B. Vöcking. An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions. ESA 2013.

Lecture 3 -- 14.04.2025:
Stochastic concepts and tools, probability distributions, events, independence, conditional probabilities, law of total probability. Random variables, expectation, linearity of expectation. Concentration: Markov inequality, Chernoff bounds.
Literature:
- Notes: Appendix A
- Linearity of Expectation
- Markov and Chebyshev Inequalities
- Chernoff bounds

Lecture 2 -- 08.04.2025:
Secretary problem, e+o(1)-competitive algorithm, proof of the ratio. Max-weight bipartite matching, motivation via sponsored search, secretary matching problem, extension of the standard algorithm is e+o(1)-competitive. Main proof steps: expected value of random selected edge in round t is at least v(M^*)/n, probability to accept any such edge is s/(t-1).
Literature:
- Notes: Sections 2.2, 2.3
- T. Kesselheim, K. Radke, A. Tönnis, B. Vöcking. An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions. ESA 2013.

Lecture 1 -- 07.04.2025:
(1) Organization and overview.
(2) Fundamentals in online algorithms: Competitive ratio, deterministic and randomized algorithms, randomization in the input.
(3) OnlineMax problem, lower bound Ω(n) on the competitive ratio. Secretary problem = OnlineMax with random-order arrival, e+o(1)-competitive algorithm.
Literature:
- Notes: Chapter 1, Sections 2, 2.1, 2.2
- Given its huge popularity, there are many surveys on the secretary problem. Here is a rather classic one:
  P.R. Freeman. The Secretary Problem and Its Extensions: A Review. Int. Stat. Rev., Vol. 51(2):189-206, 1983.