中文摘要
我们考虑反复选择政策以最大化社会福利的问题。福利是私人效用与公共收入的加权和。较早的结果为较晚的政策提供信息。效用无法直接观测，而是间接推断得到。响应函数通过实验学习。我们推导出遗憾的下界，以及针对Exp3算法一个变体的匹配对抗性上界。累积遗憾以T的2/3次方的速率增长。这意味着：(i) 福利最大化比多臂老虎机问题更难（对于有限政策集合，后者的速率为T的1/2次方）；(ii) 我们的算法实现了最优速率。对于随机情形，若社会福利是凹函数，我们可以使用二分搜索算法，在连续政策集合下实现T的1/2次方的速率。我们分析了向非线性所得税的扩展，并概述了向商品税的扩展。我们将我们的设定与垄断定价（更容易）以及双边贸易中的价格设定（更困难）进行比较。
Abstract
We consider the problem of repeatedly choosing policies to maximize social welfare. Welfare is a weighted sum of private utility and public revenue. Earlier outcomes inform later policies. Utility is not observed, but indirectly inferred. Response functions are learned through experimentation. We derive a lower bound on regret, and a matching adversarial upper bound for a variant of the Exp3 algorithm. Cumulative regret grows at a rate of T 2/3 . This implies that (i) welfare maximization is harder than the multiarmed bandit problem (with a rate of T 1/2 for finite policy sets), and (ii) our algorithm achieves the optimal rate. For the stochastic setting, if social welfare is concave, we can achieve a rate of T 1/2 (for continuous policy sets), using a dyadic search algorithm. We analyze an extension to nonlinear income taxation, and sketch an extension to commodity taxation. We compare our setting to monopoly pricing (which is easier), and price setting for bilateral trade (which is harder).