28 08 2024 E T

Page 1

Online Learning Applications Exam 28-08-2024 Exam of Online Learning Applications 28-08-2024 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 28-08-2024 1. (4 points) Answer the following questions about adversarial multi-armed bandits: • Define the regret • Explain the differences between full and bandit feedback • Provide an algorithm for the adversarial expert problem (i.e., full feedback) • Show how to extend the previous algorithm to bandit feedback Online Learning Applications Exam 28-08-2024 2. (4 points) Answer the following questions about auctions: • Explain the difference between truthful and non-truthful auctions • Provide an example of a truthful auction • Describe an algorithm for online bidding in truthful auctions with a single slot and a budget constraint Online Learning Applications Exam 28-08-2024 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-UCB algorithm Online Learning Applications Exam 28-08-2024 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 Thompson Sampling algorithm using a sliding window approach