PaperlayerView exact revision on arXiv

Source-linked AI summary

Offline Multi-Action Policy Learning: Generalization and Optimization

Zhengyuan Zhou, Susan Athey, Stefan Wager

arXiv:1810.04778v2stat.MLcs.LGecon.EM

TL;DR

The paper studies the optimal sample complexity of multi-action policy learning in the observational setting. It tackles this problem with policy-optimization strategies that achieve minimax-optimal regret decay, while tree-based implementations face computational limits.

  • Problem

    The paper asks for the optimal sample complexity of multi-action policy learning in the observational setting.

  • Method

    The paper tackles multi-action policy learning and implements tree-search variants with exact or approximate policy optimization.

  • Results

    The proposed strategy achieves minimax-optimal O_p(1/√n) regret decay.

  • Takeaways & Limitations

    The work contributes to the broader landscape of multi-action offline policy learning.

  • Takeaways & Limitations

    For a depth-3 tree, using mixed integer programming beyond low thousands for n is not possible.

Abstract

from arXiv · show

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.

1. Introduction

The paper studies offline learning of multi-action policies from observational data, addressing counterfactual outcomes, selection bias, unknown treatment assignment, and restricted policy classes. It develops doubly robust learning methods with minimax-optimal regret and practical optimization procedures for tree policies.

  • 1. Introduction: The paper frames policy learning as choosing future treatments from individual characteristics using a batch of observational features, actions, and outcomes.The learned policy maps characteristics to treatments for future use.
  • 1. Introduction: Observational policy learning is difficult because counterfactual outcomes are unobserved and treatment selection can bias estimates of alternative policies.Ignoring selection effects can produce inconsistent estimates of policy benefits and the optimal treatment assignment rule.
  • 1. Introduction: The paper addresses offline multi-action policy learning when treatment assignment is observational, potentially unknown, and policies face practical restrictions.These restrictions include fairness, budget, interpretability, and functional-form constraints.
  • 1.1. Our Contributions: The proposed doubly robust approach achieves the minimax-optimal O_p(1/√n) regret rate even when nuisance regressions converge more slowly than 1/√n.The result is presented as the paper’s main generalization contribution for multi-action offline policy learning.
  • 1.1. Our Contributions: The authors provide mixed-integer-program and tree-search implementations for optimizing policies restricted to decision trees.The tree-search method finds an exact optimal tree and scales to larger problems than the MIP strategy in the applications.

2. Problem Setup

The setup uses offline observational data with multiple actions, potential outcomes, and policies that map features to actions or action distributions. Policy value is defined by expected reward under the selected policy.

  • 2. Problem Setup: A policy maps a feature vector to a point in the action simplex, allowing randomized action choices in the general formulation.The action set is represented using d-dimensional standard basis vectors.
  • 2. Problem Setup: Each observation contains features, a selected action, and its observed reward, while rewards under unselected actions remain unobserved.The model represents these unobserved alternatives through potential outcomes.
  • 2. Problem Setup: The framework makes no structural assumption on the action-specific conditional mean rewards and treats the data as previously collected in one batch.This distinguishes the setting from online contextual bandits and permits general underlying data-generating distributions.

1. Unconfoundedness: (Yi(a1),Yi(a2),...,Yi(ad))

The policy-learning objective relies on observational identification assumptions and evaluates policies through expected reward and regret. Unconfoundedness and overlap support causal comparison, while bounded rewards simplify the theory.

  • 1. Unconfoundedness: (Yi(a1),Yi(a2),...,Yi(ad)): Unconfoundedness requires observed actions to be as good as random conditional on features, while overlap requires every action to have positive selection probability.These assumptions enable identification of causal effects in observational studies.
  • 1. Unconfoundedness: (Yi(a1),Yi(a2),...,Yi(ad)): The framework assumes bounded potential rewards, which simplifies notation and proofs and is described as realistic for many applications.The authors note that the assumption could be generalized to unbounded sub-Gaussian variables.
  • 1. Unconfoundedness: (Yi(a1),Yi(a2),...,Yi(ad)): Inverse-propensity methods can estimate policy value at √n rates when unconfoundedness holds and propensity scores are known.The propensity score is the conditional probability of receiving an action given features.
  • 1. Unconfoundedness: (Yi(a1),Yi(a2),...,Yi(ad)): The objective is to learn a policy in Π that maximizes expected reward, equivalently minimizing regret relative to the best policy in that class.Regret is written as R(π)=Q(π*)−Q(π).

3. Algorithm: Cross-fitted Augmented Inverse Propensity Weighted Learning

CAIPWL combines AIPW policy-value estimation, K-fold cross-fitting, and policy optimization for offline multi-action learning. Cross-fitting keeps estimated scores independent of outcomes, supporting generalization guarantees and practical performance.

  • Algorithm overview: CAIPWL combines AIPW policy-value estimation, K-fold cross-fitting, and policy optimization into an offline multi-action learning algorithm.Its policy-optimization implementation depends on the chosen policy class and achieves exact optimality for decision trees.
  • Guarantees: Cross-fitting’s independence property is crucial for the theoretical guarantees and reduces generalization error in practice.The paper distinguishes this use from cross-validation for selecting hyperparameters or tuning models.
  • Cross-fitting: K-fold cross-fitting estimates propensity and outcome models on other folds, keeping each observation’s estimated score independent of its outcome.This structure is used for score construction rather than hyperparameter tuning.
  • Estimation conditions: The required estimation condition allows trading off propensity-model and outcome-model accuracy when their product error remains sufficiently small.The paper gives examples based on parametric, Holder, Sobolev, and RKHS function classes.
  • AIPW estimation: The AIPW estimator evaluates counterfactual policy values using estimated action propensities and conditional expected outcomes.The approach permits multiple estimator choices, including parametric, semi-parametric, and non-parametric methods.

4. Oracle Regret Bound for CAIPWL

The oracle analysis bounds regret when propensity and outcome functions are known by controlling uniform deviations of influence-function differences over the policy class. Its proof uses policy approximations, chaining, Rademacher complexity, and concentration inequalities.

  • Oracle policy: The oracle policy ˜π is selected by maximizing the influence-function value when e_a(x) and µ_a(x) are known.The resulting guarantee is an intermediate oracle regret bound.
  • Rademacher complexity: The proof bounds policy-class complexity through Rademacher complexity and a sequence of progressively finer policy approximations.Coarse approximation terms are negligible, while the effective regime supplies the non-negligible contribution.
  • Concentration refinement: Talagrand’s inequality sharpens the lower-range bound by replacing a data-dependent maximization with a tighter population quantity.Combining this refinement with the chaining steps yields the final concentration bound.
  • Uniform concentration: Uniform concentration of influence differences controls deviations over all policy pairs rather than only a fixed pair.Lemma 2 establishes concentration around the mean, enabling tight regret analysis.
  • Oracle guarantee: The resulting oracle analysis establishes a high-probability regret guarantee for the policy optimized under known nuisance functions.The theorem states the guarantee for any δ > 0 under the paper’s assumptions.

5. Regret Bound for (Feasible) CAIPWL

The feasible CAIPWL analysis replaces oracle nuisance functions with cross-fitted estimates and establishes the final regret bound. The paper reports optimal sample-size dependence and stronger guarantees than several existing approaches, including in binary-action settings.

  • Estimated nuisances: Cross-fitting extends uniform concentration from known nuisance functions to their estimates, closing the gap between oracle and feasible regret guarantees.The analysis controls influence-function differences uniformly over the policy class.
  • Proof structure: Each error component is Op(1/√n), so the combined difference analysis yields the final regret result.The proof interprets the components as products involving noise and estimation-error terms.
  • Comparisons: Existing binary-action methods rely on comparing two actions or embedding them into special encodings, making their extension to multiple actions unclear.This motivates the multi-action formulation analyzed by CAIPWL.
  • Comparisons: In a binary-action comparison, the proposed regret scales as Op(1/n^0.5), whereas one existing bound can scale as Op(1/n^0.25).The paper also states that its bound is independent of the additional action-separation parameter.

6. Exact Policy Learning with Decision Trees

The section develops exact decision-tree policy learning using CAIPWL, first via mixed-integer optimization and then via a more computationally efficient tree-search algorithm. Simulations show CAIPWL improves estimation efficiency over IPWL, while greedy optimization performs worse than exact or skip-based optimization.

  • Exact policy learning with decision trees: The MIP formulation finds an exact optimal policy for CAIPWL, combining regret guarantees with computationally optimal optimization for tree-restricted policies.This addresses the lack of both statistical and computational optimality in existing tree-based approaches.
  • Policy learning via tree search: The customized tree-search algorithm improves scalability: it handles tens of thousands of observations in seconds and millions within hours on the same laptop.A depth-3 problem with 500 observations in 10 dimensions takes MIP about three hours, whereas the provided solver reaches much larger scales.
  • Policy learning via tree search: The tree-search method supports an efficiency–accuracy trade-off through approximation and can handle deeper trees and larger datasets while remaining more accurate than greedy learning.It is also faster for discrete features, whereas MIP does not gain comparable computational efficiency from discreteness.
  • Empirical regret comparisons: With optimization fixed, CAIPWL is more statistically efficient than IPWL and has lower variance because its additional model estimate mitigates instability from small propensities.With 2,500 observations, CAIPWL is described as already close to optimal.
  • Empirical regret comparisons: Greedy optimization performs much worse than opt or skip, while opt and skip are comparable with opt slightly better; CAIPWL-skip is recommended for computationally efficient learning in low-signal regimes.The simulations support combining strong estimation and optimization when either component is otherwise limiting.

7. Application on a Voting Dataset

The voting application evaluates five-action policy learning with cross-validation and AIPW estimates. CAIPWL matches the best fixed policy on the original data and outperforms IPWL when heterogeneity is injected.

  • 7. Application on a Voting Dataset: The study uses a 180002-voter, five-action dataset and evaluates depth-3 CAIPWL and IPWL trees through five-fold cross-validation with AIPW estimates.The five actions include Nothing, Civic, Monitored, Self History, and Neighbors.
  • 7.2. Direct Application of CAIPWL: CAIPWL and IPWL both outperform each of the first five comparison policies, while CAIPWL is comparable to the best fixed policy, Neighbors.On the original voting data, IPWL performs significantly worse than Neighbors, whereas CAIPWL is not significantly different from it.
  • 7.2. Direct Application of CAIPWL: The original dataset shows no significant heterogeneity: CAIPWL reaches Neighbors-level performance, while IPWL fails to do so.The CAIPWL–Neighbors difference is insignificant with p-value 0.47, whereas IPWL is significantly worse than Neighbors.
  • 7.2. Direct Application of CAIPWL: The CAIPWL tree can recommend milder actions for subgroups while retaining performance comparable to always choosing Neighbors.For example, it recommends Self History for some larger households and a milder action for young voters who previously voted.
  • 7.3. Application of CAIPWL on the Dataset with Injected Heterogenity: With injected heterogeneity, both learned policies outperform all six fixed-policy comparisons, and CAIPWL significantly outperforms IPWL.CAIPWL learns the correct subgroup assignments consistently across training folds, while IPWL learns a suboptimal tree.
  • 7. Application on a Voting Dataset: The application illustrates that policy learning can exploit heterogeneity to improve decisions, with CAIPWL superior to IPWL in the modified data.The authors summarize these empirical results as demonstrating both the role of heterogeneity-aware policy learning and CAIPWL’s superiority.

8. Conclusion and Future Work

The paper presents a framework for multi-action offline policy learning using observational data and identifies broader applications as future directions. Extending the framework to more expressive policy classes, continuous actions, and additional empirical settings remains open.

  • The framework contributes to data-driven decision making by providing guidance for service-decision provisioning from observational data.
  • Future work includes computational methods for more expressive policy classes such as neural networks and a broader framework for continuous actions.
  • Applying the framework to different empirical applications is left for future work.

Endnotes

The endnotes clarify policy-class assumptions, computational boundaries, and distinctions between offline and adversarial settings. They also record practical limits on exact optimization and program runtime.

  • Policy assumptions: In the iid fixed-distribution setting, deterministic policies can achieve the optimal value even when randomized policies are allowed.
  • Policy assumptions: The paper distinguishes its offline setting from adversarial contextual bandits, where randomized policies can have strictly better values.
  • Modeling scope: The policy class is assumed to contain the policies under discussion, while the developed mixed-integer program includes a classification formulation as a special case.
  • Computational boundaries: Exact optimality is unavailable for deep trees, and beyond 1000 points the program does not finish within a day.

A. Auxiliary Results

The auxiliary material supplies concentration inequalities and background definitions used in the theoretical analysis. It also reviews growth functions, shattering, and VC dimension for policy classes.

  • Concentration inequalities: The auxiliary results state Bernstein’s, Hoeffding’s, and Talagrand’s inequalities for independent random variables and bounded function classes.
  • VC dimension: The growth function records the number of distinct labelings a policy class can produce over m points.
  • VC dimension: A set is shattered when the policy class realizes all 2^m labelings on its m points, and VC dimension is the largest size of such a set.

B. Proof of Lemma 1

The proof constructs multiscale policy approximations and shows that finite Hamming covers also control inner-product distance. This yields the stated covering-number relationship.

  • Step 1: Policy approximations: For any policy π, some member of a finite Hamming cover lies within ε in inner-product distance.The resulting bound is N_IΓ(ε, Π, {x_1,...,x_n}) ≤ K = N_H(ε^2, Π).
  • Step 1: Policy approximations: The proof constructs nested policy classes S_j that 2^-j-cover Π under the inner-product distance.Each class is chosen with cardinality N_IΓ(2^-j, Π, {X_1,...,X_n}).
  • Step 1: Policy approximations: A backward selection scheme defines approximation operators A_j mapping policies into progressively finer classes.The construction verifies approximation, membership, inter-level distance, and consistency properties.
  • Concentration steps: The remaining steps combine chaining, Hoeffding concentration, union bounds, and Talagrand’s inequality to control deviations across the policy class.The proof separates negligible and effective regimes and refines the lower-range bound.

D. Proof of Theorem 2

The proof establishes unbiasedness of the estimated policy-value difference and then applies Rademacher-complexity and Talagrand arguments to obtain deviation bounds.

  • Step 1: Expected uniform bound on maximum deviation: The estimated value difference is unbiased: E[˜Δ(π_1,π_2)] = Δ(π_1,π_2).The equality follows by taking expectations of the estimated values.
  • Step 1: Expected uniform bound on maximum deviation: Rademacher-complexity results and Theorem 1 provide the expected uniform deviation control over policy comparisons.The proof then strengthens this control using Talagrand’s inequality.
  • Step 2: High probability bound on maximum deviation: The high-probability argument bounds policy-value deviations using bounded influence differences, cross-fitting, and the overlap assumptions.The proof applies concentration inequalities after conditioning on training folds.

E. Proof of Lemma 3

The proof analyzes cross-fitted doubly robust estimator differences by decomposing them into terms controlled through conditioning, boundedness, and concentration inequalities.

  • Proof of Lemma 3: The influence difference is decomposed into separate terms before each contribution is bounded.The proof explicitly introduces notation to handle the three resulting terms.
  • Proof of Lemma 3: The K-fold estimator is analyzed fold by fold, with nuisance functions trained on the other K−1 folds.This conditioning structure supports the subsequent deviation bounds.
  • Proof of Lemma 3: The argument uses overlap and nuisance-estimation assumptions together with Cauchy–Schwarz and Markov inequalities to obtain uniform bounds.The final displayed bounds apply uniformly over policy pairs.

F. Proof of Lemma 4

The proof builds universal approximations for decision-tree policies by discretizing threshold values and combining the resulting path approximations. It then counts the resulting finite tree class.

  • Step 1: Universal approximations of tree paths: Threshold indicators can be approximated on fixed sample points by selecting representatives from intervals between observed split values.Indicators with thresholds in the same interval have zero Hamming distance.
  • Step 1: Universal approximations of tree paths: A tree path is a conjunction of threshold clauses, so approximating each indicator yields an approximation of the entire path.The path is represented by multiplying its L indicator functions.
  • Step 2: Universal approximations of trees: A depth-L tree is specified by split variables, split thresholds, and leaf actions, which determines the finite-class counting argument.There are 2L − 1 branch nodes and 2L leaves.
  • Step 2: Universal approximations of trees: The resulting covering-number bound is NH(ε, Π_L) ≤ 2^(L−1)d^(2L), with logarithm bounded by terms involving p, L, ε, and d.The proof states the corresponding logarithmic bound explicitly.

G. Complexity Discussion of Tree Search Algorithm

The tree-search algorithm offers exact and approximate approaches whose computational cost depends on tree depth, data size, feature dimension, and action count. For fixed depth, exact-search running time is polynomial, while discrete features and controlled skipping can substantially reduce computation.

  • Approximate search: The approximation parameter A trades accuracy for speed: A = 1 gives exact search, while larger A skips more points and accelerates execution.Skipping A points reduces the number of recursive calls by a factor of A at each node; small A can have negligible impact when features are densely packed.
  • Exact-search complexity: O(2L−1(np)L−1d + pnlog n) is the exact-search running time for L ≥2, with O(nd) when L = 1.For L ≥3, the dominant term is O(2L−1(np)L−1d).
  • Exact-search complexity: For fixed depth L, tree-search running time is polynomial in n, p, and d, despite exponential dependence on L.The recurrence searches O(np) split possibilities at each level and recursively evaluates shallower subtrees.
  • Discrete features: Discrete feature values improve complexity because the search considers only points where features change.The L = 2 case remains O(npd + pnlog n), while the recursive term depends on the number of possible feature values.
  • Discrete features: Binary features reduce the running time to O(2L−1pL−1nd + pnlog n), essentially linear in the number of data points.More generally, near-linear time is obtained when the feature domain is small and the dimension is not too high.
Loading 1810.04778v2…