05 07 2024 E T

Page 1

Online Learning Applications Exam 5-07-2024 Exam of Online Learning Applications 5-07-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 5-07-2024 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 Explore-Then-Commit algorithm (ETC) and its theoretical guarantees Online Learning Applications Exam 5-07-2024 2. (4 points) Answer the following questions about pricing with discretization: • Describe an online algorithm for pricing with discretization • Find the optimal discretization size and explain why it is optimal • Provide the regret bound of the algorithm Online Learning Applications Exam 5-07-2024 3. (4 points) Answer the following questions about contextual bandits: • Describe the contextual bandit model • Define the pseudo-regret for contextual bandits • Describe an algorithm for contextual bandits with a small number of contexts • Explain why the previous algorithm performs poorly when there are many contexts Online Learning Applications Exam 5-07-2024 4. (4 points) Answer the following questions about non-stationary environments: • Explain the difference between a (slightly) non-stationary and an adversarial environment • Explain why algorithms for adversarial environments might be suboptimal in non-stationary envi- ronments • Describe how to extend a…