Decision analysis in correlated competition and bandits

Abstract

In this thesis, we study two decision making problems. In the first part, we consider the decision making of competitors engaged in multiple competitions. Each competition has some attributes and a reward to its winner. Since the competitions may share certain attributes, a costly effort to improve an attribute may have different effects on a competitor’s winning chances in multiple competitions, i.e., the competitions may be correlated. Furthermore, such impacts may vary for different competitors due to their abilities in the attributes. We first define the competitor-specific correlation of the competitions and model a competitor’s problem as finding a resource allocation to all the attributes that maximizes her expected total reward from all competitions, given other competitors’ decisions. We then characterize a symmetric equilibrium decision with two competitions and homogeneous competitors, which can be extended to multiple pair-wise positively or negatively correlated competitions, and asymmetric equilibrium decisions for some special cases with two types of competitors. In the second part, we provide a systematic analysis towards lower bounds in linear contextual bandits and their variants, which are usually solved using algorithms guided by parameter estimation. The Cauchy-Schwartz inequality established analytically that estimation errors dominate algorithm regrets and hence, accurate parameter estimation suffices to guarantee algorithms with low regrets. In this part, we establish the necessity of accurate estimations in effective algorithms by first constructing an estimator for any given algorithm and then showing that algorithm regrets dominate estimation errors of their induced estimators under mild conditions. That is, low-regret algorithms must imply accurate estimators and developing low-regret algorithms is equivalent to finding efficient estimators, explicitly or implicitly. Moreover, our analysis reduces the regret lower bounds to estimation errors, bridging lower bound analysis in bandit problems and regression analysis.

Date of Award	2022
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology
Supervisor	Rachel Quan ZHANG (Supervisor) & Jiheng ZHANG (Supervisor)