Collective Welfare as a Metric in Algorithmic Decision Making
Abstract: Regret minimization is a pre-eminent objective in the study of decision making under uncertainty. Indeed, regret is a central notion in multi-armed bandits, reinforcement learning, game theory, decision theory, and causal inference. In this talk, I will present our recent work that extends the formulation of regret with a welfarist perspective.
In particular, we quantify the performance of a decision maker by applying a fundamental welfare function--namely the Nash social welfare (NSW)--and study Nash regret, defined as the difference between the (a priori unknown) optimum and the decision maker’s performance. Since NSW is known to satisfy fairness axioms, our approach complements the utilitarian considerations of average (cumulative) regret, wherein the algorithm is evaluated via the arithmetic mean of its expected rewards. I will present our recent works that obtains essentially tight Nash regret guarantees for stochastic multi-armed bandits (MAB) as well as linear bandits.
Including joint works with Arindam Khan, Arnab Maiti, and Ayush Sawarni, and Soumyabrata Pal.
In particular, we quantify the performance of a decision maker by applying a fundamental welfare function--namely the Nash social welfare (NSW)--and study Nash regret, defined as the difference between the (a priori unknown) optimum and the decision maker’s performance. Since NSW is known to satisfy fairness axioms, our approach complements the utilitarian considerations of average (cumulative) regret, wherein the algorithm is evaluated via the arithmetic mean of its expected rewards. I will present our recent works that obtains essentially tight Nash regret guarantees for stochastic multi-armed bandits (MAB) as well as linear bandits.
Including joint works with Arindam Khan, Arnab Maiti, and Ayush Sawarni, and Soumyabrata Pal.
Speaker Bio
Siddharth Barman is an Associate Professor at the Department of Computer Science and Automation at
the Indian Institution of Science Bengaluru.
He was the recipient of the prestigious Ramanujan Fellowship grant in 2016.
Prior to joining IISc, he was a post-doctoral researcher at Caltech.
He obtained his Ph.D. in Computer Science at the University of Wisconsin-Madison.
His research interests lie in the design, analysis, and applications of algorithms.
Much of his research focuses on areas like algorithmic game theory and approximation algorithms,
with a current focus on areas like fair division, multi-armed bandits and causality.