| dc.description.abstract | We study regret in online learning from a welfarist perspective and explore an application of
bandit algorithms in causal inference. We introduce Nash regret, which measures the difference
between the optimal action choices and the algorithm’s performance in terms of the Nash
social welfare function. By providing bounds on Nash regret, we establish principled fairness
guarantees for online learning algorithms. We investigate different online learning settings and
derive tight bounds on Nash regret. Furthermore, we study the problem of finding optimal
interventions in causal graphs by providing theoretical guarantees within the context of the
causal bandit problem.
In the first part, we focus on the classic multi-armed bandit (MAB) framework and develop
an algorithm that achieves a tight Nash regret bound. Specifically, given a horizon of play T ,
our algorithm achieves a Nash regret of O
✓q k log T
T
◆
, where k represents the number of arms
in the MAB instance. The lower bound on average regret applies to Nash regret as well, making
our guarantee essentially tight. Additionally, we propose an anytime algorithm with a Nash
regret guarantee of O
✓q k log T
T log T
◆
.
In the second part, we study the stochastic linear bandits problem with non-negative, ⌫-sub
Poisson rewards. We present an algorithm that achieves a Nash regret bound of O
⇣q d⌫
T log(T |X|)
⌘
,
where X denotes the set of arms in ambient dimension d and T represents the number of rounds.
Furthermore, for linear bandit instances with potentially infinite arm sets, we derive a Nash re-
gret upper bound of O
⇣ d 5/4 ⌫ 1/2
pT log(T )
⌘
. Our algorithm builds upon the successive elimination
method and incorporates novel techniques such as tailored concentration bounds and sampling
via the John ellipsoid in conjunction with the Kiefer-Wolfowitz optimal design.
In the third part, we investigate Nash regret in the context of online concave optimization
and the Experts problem, assuming adversarially chosen reward functions. Our algorithm
achieves Nash regret of O log N
T
for the Experts problem where N is the number of experts.
We provide a lower bound for this setting that is essentially tight with respect to the upper
bound. Additionally, for online concave optimization, we provide a Nash regret guarantee of
O d log T
T
, where d denotes the ambient dimension.
In the final part of this thesis, we focus on the causal bandit problem, which involves iden-
tifying near-optimal interventions in a causal graph. Previous works have provided a bound of
eO(N/pT ) for simple regret for causal graphs with N vertices, constant in-degree, and Bernoulli
random variables. In this work, we present a new approach for exploration using covering in-
terventions. This allows us to achieve a significant improvement and provide a tighter simple
regret guarantee of eO(pN/T ). Furthermore, we extend our algorithm to handle the most
general case of causal graphs with unobservable variables | en_US |
