THESIS
2022
1 online resource (x, 82 pages) : illustrations (some color)
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’ dec...[
Read more ]
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.
Post a Comment