Algorithms & Complexity

Computer Science 1

Group

Research

Teaching

Misc

back to main page

Logbook Optimization and Uncertainty - Summer 2025

• Lecture 21 -- 24.06.2025:
  Online convex optimization, convexity properties, Follow-the-Regularized-Leader (FTRL), bound on the total regret, Experts problem as a special case of online convex optimization, Euclidean and Entropical regularizers, Lipschitz condition, σ-strong convexity, upper bound on the regret of FTRL.

  Literature:
  • Notes: Sections 7.3, 7.3.2



• Lecture 20 -- 23.06.2024:
  Adversarial Multi-Armed Bandits, Exp3-Algorithm, regret at most 3$\sqrt{n\; T\; ln\; n}$, Exp3 is a no-(external)-regret algorithm, proof of upper bound on total expected cost.

  Literature:
  • Notes: Section 7.2
  • P. Auer, N. Cesa-Bianchi, Y. Freund, R. Schapire. The Nonstochastic Multiarmed Bandit Problem. SIAM Journal on Computing 32(1):48-77, 2003.



• Lecture 19 -- 17.06.2025:
  Expert classification, Weighted Majority algorithm, proof of upper bound on the number of mistakes in terms of mistakes of the best classifier. Experts problem, Randomized Weighted Majority algorithm (RWM), definition regret, regret of RWM is at most 2$\sqrt{T\; ln\; n}$, RWM is a no-(external)-regret algorithm, proof of upper bound on total expected cost.

  Literature:
  • Notes: Section 7.1
  • N. Littlestone, M. Warmuth. The Weighted Majority Algorithm. Information and Computation 108(2):212-261, 1994.



• Lecture 18 -- 16.06.2025:
  Markovian MAB, proof of optimality of the Gittins index policy. Stochastic multi-armed bandits, definition, regret, simple explore-then-exploit algorithm, regret sublinear in T; UCB1 algorithm, regret bound of O(n log T) when best expectation of any arm has a constant leading margin.

  Literature:
  • Notes: Section 6.2 (Proof of Theorem 30), Section 6.3 (until start of proof of Lemma 21)
  • P. Auer, N. Cesa-Bianchi, P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning 47(2):235–256, 2002



• 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, randomi­za­tion 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.