16 01 2025 E T

Page 1

Online Learning Applications Exam 16-01-2025 Exam of Online Learning Applications 16-01-2025 Name: Surname: Student ID: Signature: Instructions: • The total number of points is 16. • The duration of the exam is: 2h00min. • During this exam you are not allowed to use books, notes, and electronic devices. • You are allowed to write the exam either with a pen or a pencil. • You are allowed to withdraw from the exam at any time. • Before you exit the room, you must hand in your exam. Online Learning Applications Exam 16-01-2025 1. (4 points) Answer the following questions about stochastic multi-armed bandits: • Define the pseudo-regret • Show that the greedy algorithm suffers linear pseudo-regret • Describe the UCB1 algorithm and its theoretical guarantees Online Learning Applications Exam 16-01-2025 2. (4 points) Answer the following questions about truthful auctions: • Define a second-price auction • Describe the differences between truthful and not-truthful auctions • Describe an algorithm for online bidding in second-price auctions Online Learning Applications Exam 16-01-2025 3. (4 points) Answer the following questions about combinatorial bandits: • Describe the combinatorial bandit framework • Define the pseudo-regret in combinatorial bandits • Describe the combinatorial-TS algorithm Online Learning Applications Exam 16-01-2025 4. (4 points) Answer the following questions about non-stationary environments: • Describe two types of non-stationary environments • Explain why UCB1 fails in non-stationary environments • Show how to extend the UCB1 algorithm using a sliding window approach