Fast Learning of Optimal Policy Trees
James Cussens, Julia Hatamyar, Vishalie Shah, Noemi Kreif · 2025
Read Fast Learning of Optimal Policy Trees by James Cussens, Julia Hatamyar, Vishalie Shah, Noemi Kreif (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-15435.txt.
Introduction
James Cussens, Julia Hatamyar, Vishalie Shah, and Noemi Kreif speed up a method for learning optimal policy trees, simple decision rules that assign treatments or actions. Their 2025 paper builds on a popular approach published in 2021. Policy trees are prized because people can read and audit them, but finding the truly best tree is slow.
The team reimplements the method with discrete optimization techniques. In finite-sample tests, their version learns optimal trees nearly fifty times faster than the original. They release the work as a public software package for the R language, called fastpolicytree. The speedup makes optimal, explainable policies practical on larger data than before.
Catalog record
| CREATOR | James Cussens, Julia Hatamyar, Vishalie Shah, Noemi Kreif |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-15435
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fast Learning of Optimal Policy Trees James Cussens, Julia Hatamyar, Vishalie Shah, Noemi Kreif Abstract We develop and implement a version of the popular policytree method (Athey and Wager, 2021) using discrete optimisation techniques. We test the performance of our algorithm in finite samples and find an improvement in the runtime of policytree learning by a factor of nearly 50 compared to the original version. We provide an R package, fastpolicytree , for public use. 1 Introduction The problem of learning optimal policy rules that map an individual covariate profile to a treatment decision has gained significant traction in recent years. Increasing availability of rich, large-scale data has contributed to this shift away from static policymaking towards a data-driven approach ( Amram et al., 2022 ) . For example, in medicine, treatment decisions are increasingly personalised at the patient level according to patient characteristics and expected outcomes. The existing literature on statistical methods for learning optimal policy rules is vast ( Manski, 2004 ; Swaminathan and Joachims, 2015 ; Kitagawa and Tetenov, 2018 ; van der Laan and Luedtke, 2015 ; Luedtke and van der Laan, 2016b ; Luedtke and van der Laan, 2016a ; Athey and Wager, 2021 ) . Proposed approaches include those that assign a particular policy action (or treatment) to individuals whose expected benefit from being assigned to that treatment compared to a baseline treatment (estimated via the conditional average treatment effect (CATE) function) is positive, or those that directly select a policy rule that maximises expected outcomes across the population. Essentially, policy learning involves counterfactual estimation since we can only observe outcomes under the treatment actually received. In this paper, we consider the problem of learning optimal policy rules from an observational dataset of individuals i=1,\ldots,n , that are characterised by the form (X_{i},W_{i},Y_{i}) , where X_{i} is a vector of covariates including confounders and effect modifiers, W_{i} is a discrete treatment that could take one of w=1,\ldots,m values, and Y_{i} is the observed outcome. Our aim is to learn a policy rule \pi that maps X into a treatment decision X\rightarrow\pi(x)\in\{1,\dots,m\} for policies in a pre-specified policy class \pi\in\Pi . The optimal policy rule \pi^{*} is the rule that maximises (or minimises, depending on the objective function) the estimator of the policy value, often defined as the expected counterfactual mean reward \mathbb{E}[\Gamma_{iw}(\pi(X_{i}))] , where \Gamma_{iw} is the estimated counterfactual reward for each observation i under each policy action w . Depth- k decision trees are a popular class for policy learning problems since they are able to generate interpretable and transparent outputs that describe the underlying model behind the policy decision. Decision trees recursively partition the covariate vector and assign a treatment decision to the partition that is aligned with a pre-specified tree depth, also known as the leaf node. The trained tree is then used to classify observations to a treatment decision by guiding them through the path of splits and into a leaf node according to their individual covariate profile. This tree-like structure means that the reasoning behind the decision rule is explainable, which is an often important consideration in personalised decision making. Traditionally, decision trees are trained using a top-down, greedy approach, meaning that the recursive algorithm starts at the root node and finds the locally optimal split at each partition, without considering the impact of future splits on overall tree performance. The problem with the greedy heuristic, however, is that the resulting tree may not capture all of the underlying characteristics of the data, leading to a suboptimal tree. A superior decision tree can be found by considering all future splits at each partition, thus achieving a globally optimal solution that maximises the objective function. Decision tree performance can be measured in terms of scalability (i.e. maintains performance as the dimensionality of data and tree depth increases), computational intensity and speed (i.e. generates a solution in a reasonable timeframe), and accuracy of optimality (i.e. correctly maximises the policy value estimator). In recent years, there have been some notable developments in decision tree-based methods for policy learning that are globally optimal. Some of these methods embed counterfactual estimation and policy learning within the same decision tree, while others separate these two tasks by first estimating the counterfactuals using an appropriate data model, and then training a decision tree on these estimates to learn the optimal policy rule ( Amram et al., 2022 ) . We focus on methods that use the latter approach since we are only interested in the policy optimisation step in this work. Zhou et al., 2023 develop an implementation of an exhaustive tree-search based algorithm that finds an exact optimal tree. However, their tree struggles to scale well beyond shallow trees and small datasets. Based on the work of Bertsimas and Dunn, 2017 , they also consider formulating the policy learning problem as a mixed integer programme (MIP), which can be solved using commercial solvers (e.g. Gurobi ( Gurobi Optimization, LLC, 2024 ) ), however they encounter similar scaling issues using this approach. Amram et al., 2022 develop an alternative implementation of the exact tree search that uses coordinate descent to train the decision trees by repeatedly optimising each tree split until no further improvement in the overall objective function can be achieved. 2 Our implementation Our implementation is available as an R package called fastpolicytree . Its goal is simply to learn policy trees more quickly than the existing policytree R package. We start with an account of the tree-building approach found in policytree . 2.1 policytree The tree_search function provided by policytree , finds an optimal policy tree (of a given maximal depth) for any given subset of the covariate and reward data. It does this via a recursive algorithm. Given any subset of the data and depth limit d as input, tree_search considers every possible split (each split determined by a choice of covariate and covariate splitting value) thus creating a ‘left’ subset of the data and a ‘right’ subset. Once an optimal policy tree for both the left and right subsets have been found (via recursion with depth limit d-1 ), we then know the best possible reward for the given split. Since all splits are considered, this allows the algorithm to determine the optimal policy tree for its input. A key issue is how these subsets are implemented. In policytree each subset is stored as p sorted sets where p is the number of covariates. The sorted set for covariate j has (the indices) of the datapoints in the subset sorted according to their values on covariate j . A major advantage of this approach is that when generating successive splits for covariate j one can quickly find the datapoints to move from the ‘right’ to the ‘left’. A disadvantage is that each such move requires updating p sorted sets. Sverdrup et al., 2020 state that each sorted set is implemented as a binary search tree which would allow datapoints to be added and removed in O(\log n) , where n is the size of the set. However, policytree actually implements sorted sets as a sorted vector. The Boost container data type flat_set ( Boost C++ Libraries, 2018 ) is used which