  We study principal-agent problems in which a principal commits to an
outcome-dependent payment scheme -- called contract -- in order to induce an
agent to take a costly, unobservable action leading to favorable outcomes. We
consider a generalization of the classical (single-round) version of the
problem in which the principal interacts with the agent by committing to
contracts over multiple rounds. The principal has no information about the
agent, and they have to learn an optimal contract by only observing the outcome
realized at each round. We focus on settings in which the size of the agent's
action space is small. We design an algorithm that learns an
approximately-optimal contract with high probability in a number of rounds
polynomial in the size of the outcome space, when the number of actions is
constant. Our algorithm solves an open problem by Zhu et al.[2022]. Moreover,
it can also be employed to provide a $\tilde{\mathcal{O}}(T^{4/5})$ regret
bound in the related online learning setting in which the principal aims at
maximizing their cumulative utility, thus considerably improving
previously-known regret bounds.
