In many settings, a decision-maker wishes to learn a rule, or policy, that
maps from observable characteristics of an individual to an action. Examples
include selecting offers, prices, advertisements, or emails to send to
consumers, as well as the problem of determining which medication to prescribe
to a patient. While there is a growing body of literature devoted to this
problem, most existing results are focused on the case where data comes from a
randomized experiment, and further, there are only two possible actions, such
as giving a drug to a patient or not. In this paper, we study the offline
multi-action policy learning problem with observational data and where the
policy may need to respect budget constraints or belong to a restricted policy
class such as decision trees. We build on the theory of efficient
semi-parametric inference in order to propose and implement a policy learning
algorithm that achieves asymptotically minimax-optimal regret. To the best of
our knowledge, this is the first result of this type in the multi-action setup,
and it provides a substantial performance improvement over the existing
learning algorithms. We then consider additional computational challenges that
arise in implementing our method for the case where the policy is restricted to
take the form of a decision tree. We propose two different approaches, one
using a mixed integer program formulation and the other using a tree-search
based algorithm.

本文主要研究基于观测数据的离线多行动策略学习问题，特别地，该策略可能需要遵守预算约束或属于受限策略类，如决策树，提出了一个算法实现，能够达到渐近最小化风险后悔，这是在多行动设置中的首次结果，对于现有的学习算法有大幅度的性能提升。该文提出了两种不同的方法来解决当策略被限制为采用决策树形式时出现的附加计算挑战，一种方法使用混合整数方案，另一种方法使用基于树搜索的算法。