The agency problem emerges in today's large scale machine learning tasks,
where the learners are unable to direct content creation or enforce data
collection. In this work, we propose a theoretical framework for aligning
economic interests of different stakeholders in the online learning problems
through contract design. The problem, termed \emph{contractual reinforcement
learning}, naturally arises from the classic model of Markov decision
processes, where a learning principal seeks to optimally influence the agent's
action policy for their common interests through a set of payment rules
contingent on the realization of next state. For the planning problem, we
design an efficient dynamic programming algorithm to determine the optimal
contracts against the far-sighted agent. For the learning problem, we introduce
a generic design of no-regret learning algorithms to untangle the challenges
from robust design of contracts to the balance of exploration and exploitation,
reducing the complexity analysis to the construction of efficient search
algorithms. For several natural classes of problems, we design tailored search
algorithms that provably achieve $\tilde{O}(\sqrt{T})$ regret. We also present
an algorithm with $\tilde{O}(T^{2/3})$ for the general problem that improves
the existing analysis in online contract design with mild technical
assumptions.

通过合同设计解决在线学习问题中不同利益相关方的经济利益一致性，提出一种理论框架来解决机器学习中的代理问题，并设计了有效的动态规划算法和无悔学习算法以实现最优合同和平衡探索与开发的挑战。

契约强化学习：用无形之手牵引力量

Contractual Reinforcement Learning: Pulling Arms with Invisible Hands

In mechanism design it is typical to impose incentive compatibility and then
derive an optimal mechanism subject to this constraint. By replacing the
incentive compatibility requirement with the goal of minimizing expected ex
post regret, we are able to adapt statistical machine learning techniques to
the design of payment rules. This computational approach to mechanism design is
applicable to domains with multi-dimensional types and situations where
computational efficiency is a concern. Specifically, given an outcome rule and
access to a type distribution, we train a support vector machine with a special
discriminant function structure such that it implicitly establishes a payment
rule with desirable incentive properties. We discuss applications to a
multi-minded combinatorial auction with a greedy winner-determination algorithm
and to an assignment problem with egalitarian outcome rule. Experimental
results demonstrate both that the construction produces payment rules with low
ex post regret, and that penalizing classification errors is effective in
preventing failures of ex post individual rationality.

本文提出了用最小化预期 ex post 遗憾取代激励相容性要求来适应统计机器学习技术以进行机制设计的方法。通过使用支持向量机和特殊的判别函数结构，可以训练得出具有良好激励性能的隐式支付规则。该方法适用于多维类型的领域，以及需要考虑计算效率的情况。实验结果表明，这种构建产生的付款规则具有低的 ex post 遗憾，并且处罚分类错误在防止 ex post 单独合理性失败方面是有效的。