Loading Events

« All Events

  • This event has passed.

Learning Club BIU talk by Yonathan Efroni

May 23, 2021 @ 12:00 pm - 1:00 pm IDT

BIU Learning Club 23.5.2021 — Yonathan Efroni — Confidence-Budget Matching for Sequential Budgeted Learning
Yonathan Efroni from Microsoft research Israel/New York.



Meeting ID: 848 9122 3876

Passcode: 750812

Confidence-Budget Matching for Sequential Budgeted Learning

A core element in decision-making under uncertainty is the feedback on the quality of the performed actions. However, in many applications, such feedback is restricted. For example, in recommendation systems, repeatedly asking the user to provide feedback on the quality of recommendations will annoy them. In this work, we formalize decision-making problems with querying budget, where there is a (possibly time-dependent) hard limit on the number of reward queries allowed. Specifically, we consider multi-armed bandits, linear bandits, and reinforcement learning problems. We start by analyzing the performance of `greedy’ algorithms that query a reward whenever they can. We show that in fully stochastic settings, doing so performs surprisingly well, but in the presence of any adversity, this might lead to linear regret. To overcome this issue, we propose the Confidence-Budget Matching (CBM) principle that queries rewards when the confidence intervals are wider than the inverse square root of the available budget. We analyze the performance of CBM based algorithms in different settings and show that they perform well in the presence of adversity in the contexts, initial states, and budgets.

Joint work with Nadav Merlis, Aadirupa Saha and Shie Mannor (to be in ICML 2021).


The recording of Yonathan’s talk is available:
Thanks to Yonathan for presenting and to everyone who attended,


May 23, 2021
12:00 pm - 1:00 pm IDT
Event Categories:
Event Tags:

Leave a Comment