Online Learning and Optimization (EE6106)

The central question throughout: can a learning agent compete with the best fixed strategy in hindsight, and how quickly? The answer depends on what the agent observes and what the adversary knows.

Part 1: Prediction via Expert Advice

The agent observes $K$ experts at each step and must predict a sequence against an adversary. The challenge is combining expert advice optimally without knowing which expert is best.

Key result: Sub-linear regret $O(\sqrt{n \ln K})$ is achievable with convex loss or a randomized algorithm. A deterministic algorithm against a fully adaptive adversary with $0$-$1$ loss cannot escape linear regret.

Part 2: Multi-Armed Bandits

The agent pulls one arm per step and observes only its reward. Partial feedback forces a genuine exploration-exploitation tradeoff.

Adversarial Bandits

Stochastic Bandits

Lower Bounds and Pure Exploration

Key results: Logarithmic regret $O(\ln n / \Delta)$ is achievable and optimal for stochastic MABs. Adversarial bandits pay an extra $\sqrt{K}$ factor. Minimax regret is $\Omega(\sqrt{nK})$.

Part 3: Markov Decision Processes

Actions affect future states. The agent must plan, not just react. When the model is unknown, this becomes reinforcement learning.

Key results: Discounted MDPs always have an optimal stationary deterministic policy. Value Iteration and Policy Iteration converge via the Bellman contraction. The undiscounted (ETA) case requires additional structural conditions (irreducibility, bounded hitting times).

Course Arc