  We present a study on a repeated delegated choice problem, which is the first
to consider an online learning variant of Kleinberg and Kleinberg, EC'18. In
this model, a principal interacts repeatedly with an agent who possesses an
exogenous set of solutions to search for efficient ones. Each solution can
yield varying utility for both the principal and the agent, and the agent may
propose a solution to maximize its own utility in a selfish manner. To mitigate
this behavior, the principal announces an eligible set which screens out a
certain set of solutions. The principal, however, does not have any information
on the distribution of solutions in advance. Therefore, the principal
dynamically announces various eligible sets to efficiently learn the
distribution. The principal's objective is to minimize cumulative regret
compared to the optimal eligible set in hindsight. We explore two dimensions of
the problem setup, whether the agent behaves myopically or strategizes across
the rounds, and whether the solutions yield deterministic or stochastic
utility. Our analysis mainly characterizes some regimes under which the
principal can recover the sublinear regret, thereby shedding light on the rise
and fall of the repeated delegation procedure in various regimes.
