13 06 2024 E T

Page 1

Online Learning Applications Exam 13-06-2024 Exam of Online Learning Applications 13-06-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 13-06-2024 1. (4 points) Answer the following questions about adversarial multi-armed bandits: • Define the regret • Show that any deterministic algorithm suffers linear regret in adversarial bandits • Describe an algorithm for adversarial bandits with full feedback and its guarantees Online Learning Applications Exam 13-06-2024 2. (4 points) Answer the following questions about non-truthful auctions: • Define a first-price auction • Describe the differences between truthful and not-truthful auctions • Describe an algorithm for online bidding in first-price auctions Online Learning Applications Exam 13-06-2024 3. (4 points) Answer the following questions about combinatorial bandits: • Describe the online matching problem • Show why online matching is a special case of combinatorial bandits • Describe the combinatorial Thompson sampling algorithm and its guarantees Online Learning Applications Exam 13-06-2024 4. (4 points) Answer the following questions about non-stationary environments: • Describe the properties of a non-stationary environment with abrupt changes • Explain why UCB1 fails in non-stationary environments • Provide an extension of UCB1 for non-stationary environments