A Hierarchy of Policy Learning Problems

Hamsa Bastani; Osbert Bastani; Shihan Chen

REVIEW 2 major objections 4 minor 30 references

A Hierarchy of Policy Learning Problems

T0 review · 2 major / 4 minor · reviewed 2026-07-12 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Even when data is too sparse to find a better policy, you can still prove that one exists.

desk verdict Clean hierarchy for offline policy learning with a real (if partial) sample-complexity gap under monotonicity; solid foundational theory, not a definitive hardness result. read the letter →

arxiv 2607.03385 v1 pith:HRQF7SSZ submitted 2026-07-03 stat.ML cs.LG

Hamsa Bastani , Osbert Bastani , Shihan Chen This is my paper

classification stat.MLcs.LG

keywords policylearningsamplecomplexityofflinedecision-makingimprovingexistencereductionhierarchystatisticalvalidity

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Most offline policy-learning work asks for the best possible action rule or at least a rule that beats a simple baseline with statistical confidence. When samples are scarce both goals can fail. This paper argues that a still weaker question remains useful: does any improving policy exist at all? It builds a single statistical framework that treats all three problems as algorithms that may abstain, then measures how many samples each needs before the false-negative rate drops below a fixed false-positive budget. Within that framework the existence question reduces to the improving-policy question, which reduces to the optimal-policy question, so each is at least as easy as the next. The paper then shows the reverse gaps are strict: optimal policy is strictly harder than improving policy, and, for any algorithm that ranks types by the size of their normalized treatment-effect statistic, improving policy is polynomially harder than mere existence. Consequently a decision-maker can sometimes certify that better decisions are possible even when the data are too thin to name them.

What carries the argument

A unified validity-plus-false-negative-rate definition that lets algorithms for different output spaces (full policies, partial policies, or binary existence answers) be compared by reductions and sample-complexity bounds.

What would settle it

Exhibit a non-monotone but still valid algorithm that, on the same family of instances used in the paper's lower bound, recovers an improving policy with only a constant number of samples.

Watch

Extended reading notes

Core claim

Under a natural monotonicity condition on improving-policy algorithms, there exist families of instances (growing numbers of unit types) on which any valid monotone algorithm needs a polynomial number of samples while a simple aggregate test decides existence with a single sample per type.

Load-bearing premise

The polynomial gap between finding an improving policy and merely knowing one exists is proved only for algorithms that never treat a weaker type while skipping a stronger one.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The useful takeaway is that they cleanly formalize three nested problems—optimal policy, improving policy, and policy existence—via a shared FPR/FNR validator that lets them talk about reductions and sample complexity even when the output spaces differ. The reductions themselves (Prop 2.2) are immediate, but the framework is new relative to the Kitagawa–Tetenov / Athey–Wager / Banerjee / Chernozhukov line, and the explicit existence problem is a genuine addition.

What they do well is the technical core. Algorithms 1–3 are standard concentration (Mills + Laurent–Massart + Hoeffding) and carefully checked. The main result (Thm 3.7) constructs a swamping instance with k types where existence is solvable with n=1 while any valid monotone improving-policy algorithm needs Ω(k^{ε/2}) samples. The proof is correct under the stated condition; the concentration lemmas and validity of Algorithm 3 hold up. They are also honest that the optimal-vs-improving gap is strict while the improving-vs-existence gap is only partial.

The soft spot is exactly the one they flag: the separation lives only inside the monotone class (Def 3.1). Monotonicity is natural—assign treatment 1 only when the normalized statistic is large enough—but it is introduced for the lower bound and they never claim it for arbitrary algorithms. That keeps the paper from being a full hardness result; it is a framework paper that shows a useful gap under a reasonable restriction. The generative model is deliberately simple (finite types, known σ, balanced samples, Gaussians), which is fine for the purpose but means the numbers are illustrative rather than immediately portable.

Citations look appropriate; no circularity. This is for people already working on offline causal policy learning who want a clean way to think about what questions remain answerable when data is scarce. It deserves a serious referee. I would bring it to reading group and would cite the hierarchy and the existence problem.

Referee Report

2 major / 4 minor

Summary. The paper introduces a sample-complexity framework for offline policy learning problems that unifies heterogeneous output spaces via validators, validity (uniform FPR ≤ δ with abstention), and FNR (abstention probability). It formalizes three problems—optimal policy, improving (partial) policy that beats both constant baselines, and binary existence of an improving policy—and proves reductions showing existence ≼ improving ≼ optimal. Basic concentration-based upper/lower bounds (Theorems 3.1–3.6, Algorithms 1–3) are essentially matching on separated-effect instance classes. The main technical result (Theorem 3.7) exhibits a strict gap between optimal and improving (via instance classes containing zero effects) and a partial polynomial gap between improving and existence: under a natural monotonicity condition on algorithms (Definition 3.1), there exist instances P_k with k types on which any valid monotone improving algorithm requires n = Ω(k^{ε/2}) samples while Algorithm 3 solves existence with n = 1.

Significance. If the results hold, the work supplies a clean conceptual hierarchy and a concrete demonstration that weaker questions (existence of improvement) can remain answerable when stronger ones (producing an improving or optimal policy) are information-theoretically hard. The framework, reductions, and explicit valid algorithms are carefully developed inside a fully specified Gaussian potential-outcomes model; the concentration lemmas and the swamping construction of Theorem 3.7 are technically solid. The partial character of the improving–existence gap is stated transparently. These contributions are of genuine interest to the offline causal/policy-learning community and could usefully shape how limited observational data are interrogated in practice.

major comments (2)

[§3.2, Definition 3.1 and Theorem 3.7] Theorem 3.7 (and the surrounding discussion in §3.2) establishes the improving–existence separation only inside the monotone algorithm class of Definition 3.1. The lower-bound argument correctly uses monotonicity to force any non-abstaining algorithm to treat a negative type once it treats a positive type, destroying improvement under the swamping construction. Because the paper’s central claim is precisely this partial gap, the restriction is load-bearing: either a matching lower bound for arbitrary valid algorithms, or a short argument that monotonicity is essentially without loss of generality for the improving-policy problem, is needed to make the separation fully rigorous rather than conditional.
[Theorem 3.7 construction] The engineered instance of Theorem 3.7 relies on carefully tuned heterogeneous noise levels (c1 = k^{ε/4}, c0 = k^{2ε}, c-1 = k^{-1/2+ε/3}) together with m = ⌊k^{1-ε}⌋ positive types. While the calculations close for large k, the necessity of these heterogeneous variances is not discussed. A gap that survives homogeneous variances (or a brief argument why heterogeneous noise is unavoidable) would substantially strengthen the practical relevance of the separation.

minor comments (4)

[Abstract / §1] Abstract and introduction contain multiple typographical slips (“animproving”, “Na¨ ıvely”, “the improved policy problem”, missing spaces after periods). A careful copy-edit pass is needed.
[§1.2 vs §2.4] In the contributions paragraph the informal definition of FNR is written as the non-abstention probability, while the formal definition in §2.4 is the abstention probability. Align the two statements.
[§2.1–2.3] Algorithms 1–3 and all concentration statements assume known variances and a perfectly balanced design. A short remark on the robustness (or lack thereof) of the hierarchy under estimated propensities or unbalanced sampling would help readers assess scope.
[§1.1] Related-work discussion of treatment-effect heterogeneity testing (e.g., Shchetkina & Berman) is brief; a sentence clarifying the algorithmic novelty of Algorithm 3 relative to that literature would be useful.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: fully self-contained theoretical hierarchy with explicit reductions, concentration proofs, and a transparent monotonicity restriction.

full rationale

The paper defines policy-learning instances (finite types, Gaussian potential outcomes), three problems via output spaces and validators (optimal, improving, existence), sample complexity via FPR/FNR with abstention, and reductions (Props. 2.1–2.2) that are purely syntactic mappings preserving validity. Upper/lower bounds (Thms. 3.1–3.6) follow from standard Mill’s/Laurent-Massart/Hoeffding concentration on the well-specified model; Algorithm 3’s second stage is a likelihood-ratio-style aggregate test whose validity is proved from first principles (Lem. 4.1–4.3, Cor. 4.1). The sole non-trivial gap (Thm. 3.7) is obtained by constructing an explicit swamping instance and restricting the algorithm class to the monotone maps of Def. 3.1; the restriction is stated as an assumption, not derived from the target claim, and the lower-bound argument simply shows that any non-abstaining monotone policy must treat a negative type once it treats a positive type, destroying improvement. No parameters are fitted to data, no uniqueness theorem is imported from the authors’ prior work, and self-citations appear only in related-work discussion of improving-policy algorithms. The derivation chain is therefore independent of its own conclusions.

Assumptions & free parameters 0 free parameters · 3 assumptions · 2 invented entities

The paper works entirely inside a stylized finite-type Gaussian potential-outcomes model with known variances and balanced designs. These modeling choices, plus the ad-hoc monotonicity restriction needed for the main separation, are the only non-standard ingredients; everything else is standard concentration or reduction.

assumptions (3)

domain assumption Potential outcomes are independent Gaussians with known variances; unit types are finite and equiprobable; samples are perfectly balanced across type-treatment pairs.
Stated in §2.1–2.3; used for every concentration bound and sample-complexity claim.
ad hoc to paper An improving-policy algorithm is monotone: it never assigns treatment 1 to a type whose normalized statistic is smaller than that of another type it already treats with 1.
Definition 3.1; required for the lower bound of Theorem 3.7 and never justified beyond “natural.”
ad hoc to paper Validity is defined by a uniform FPR ≤ δ bound that must hold for every instance and every δ; sample complexity is the smallest n that also drives FNR ≤ δ.
Definitions 2.2–2.3; the entire reduction framework rests on this particular notion of correctness.

invented entities (2)

Policy-existence problem (O_exist, V_exist)
purpose: To ask only whether an improving policy exists, without producing one.
Introduced in §2.3; the main object whose sample complexity is shown to be strictly smaller under monotonicity.
Monotone algorithm class (Def. 3.1)
purpose: To obtain a non-trivial lower bound separating improving-policy learning from existence.
Ad-hoc restriction invented for Theorem 3.7; no external characterization or necessity proof is given.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Hierarchy of Policy Learning Problems." pith.science (2026). https://pith.science/paper/HRQF7SSZ

@misc{pith2026260703385,
  author       = {Pith},
  title        = {Pith review of: A Hierarchy of Policy Learning Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HRQF7SSZ}},
  note         = {Machine review of arXiv:2607.03385}
}

read the original abstract

Policy learning has received substantial attention with the goal of learning policies from observational data for decision-making. A majority of work in this space has focused on developing algorithms for computing policies that minimize regret compared to the optimal policy. However, in many practical settings, there is insufficient data to obtain low regret. As a result, recent work has shifted attention to alternative objectives, most notably, studying whether it is possible to learn an improving policy that statistically significantly outperforms baseline policies. We argue that there is substantial merit in studying a broader range of policy learning problems. When there is insufficient data to learn an improving policy, there may still be useful questions that can be answered. To this end, we provide a mathematical framework for studying the relationships between policy learning problems. We formalize three problems within our framework: beyond the optimal policy problem and the improving policy problem, we also propose the policy existence problem, which aims to determine if an improving policy exists. Within our framework, we show that the policy existence problem reduces to the improving policy problem, which in turn reduces to the optimal policy problem; these reductions prove that each problem is at least as easy as the next one (in sample complexity). A key question remains: is this hardness strict? We provide partial answers. First, the gap between the optimal policy and improving policy problems is strict. For the improving policy and policy existence problems, we prove that a sublinear polynomial gap exists under natural conditions on improving policy learning algorithms. Thus, we may be able to answer questions about the existence of an improving policy even when we cannot find one. These results highlight the value in studying a broader range of policy learning problems.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

30 extracted references · 2 linked inside Pith

[1]

arXiv preprint arXiv:2502.10653 , year=

Policy Learning with Confidence , author=. arXiv preprint arXiv:2502.10653 , year=

arXiv
[2]

arXiv preprint arXiv:2505.14388 , year=

Algorithmic Hiring and Diversity: Reducing Human-Algorithm Similarity for Better Outcomes , author=. arXiv preprint arXiv:2505.14388 , year=

arXiv
[3]

Communications of the ACM , volume=

A theory of the learnable , author=. Communications of the ACM , volume=. 1984 , publisher=

1984
[4]

Nature , volume=

Efficient and targeted COVID-19 border testing via reinforcement learning , author=. Nature , volume=. 2021 , publisher=

2021
[5]

Proceedings of the National Academy of Sciences , volume=

A 680,000-person megastudy of nudges to encourage vaccination in pharmacies , author=. Proceedings of the National Academy of Sciences , volume=. 2022 , publisher=

2022
[6]

Proceedings of the 25th ACM Conference on Economics and Computation , pages=

When Is Heterogeneity Actionable for Targeting? , author=. Proceedings of the 25th ACM Conference on Economics and Computation , pages=
[7]

Econometrica , volume=

Selecting the most effective nudge: Evidence from a large-scale experiment on immunization , author=. Econometrica , volume=. 2025 , publisher=

2025
[8]

1985 , issn =

Asymptotically efficient adaptive allocation rules , journal =. 1985 , issn =

1985

Show all 30 references

[9]

Murphy, S. A. , title =. Journal of the Royal Statistical Society Series B: Statistical Methodology , volume =. 2003 , month =

2003
[10]

Bulletin of the American Mathematical Society , volume =

Some aspects of the sequential design of experiments , author =. Bulletin of the American Mathematical Society , volume =. 1952 , month =

1952
[11]

Biometrika , volume =

THOMPSON, WILLIAM R , title =. Biometrika , volume =. 1933 , month =

1933
[12]

2014 , eprint=

Thompson Sampling for Contextual Bandits with Linear Payoffs , author=. 2014 , eprint=

2014
[13]

Proceedings of the 21st Annual Conference on Learning Theory , year =

Stochastic Linear Optimization under Bandit Feedback , author =. Proceedings of the 21st Annual Conference on Learning Theory , year =
[14]

and Kakade, Sham M

Dani, Varsha and Hayes, Thomas P. and Kakade, Sham M. , title =. Proceedings of the 21st International Conference on Neural Information Processing Systems , pages =. 2007 , isbn =

2007
[15]

Auer, Peter , title =. J. Mach. Learn. Res. , month = mar, pages =. 2003 , issue_date =

2003
[16]

International Conference on Machine Learning , year =

Miroslav Dudik and John Langford and Lihong Li , title =. International Conference on Machine Learning , year =
[17]

Biometrics , volume =

A Robust Method for Estimating Optimal Treatment Regimes , author =. Biometrics , volume =
[18]

Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics , pages =

Contextual Bandits with Linear Payoff Functions , author =. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics , pages =. 2011 , editor =

2011
[19]

Stat , volume =

Estimating Optimal Treatment Regimes from a Classification Perspective , author =. Stat , volume =
[20]

Econometrica , volume =

Who Should Be Treated? Empirical Welfare Maximization Methods for Treatment Choice , author =. Econometrica , volume =
[21]

arXiv preprint arXiv:1702.02896 , year=

Policy Learning with Observational Data , author=. arXiv preprint arXiv:1702.02896 , year=

arXiv
[22]

Proceedings of the 32nd International Conference on Machine Learning , pages =

High Confidence Policy Improvement , author =. Proceedings of the 32nd International Conference on Machine Learning , pages =. 2015 , editor =

2015
[23]

Biometrika , volume =

The Central Role of the Propensity Score in Observational Studies for Causal Effects , author =. Biometrika , volume =. 1983 , publisher =

1983
[24]

Robins and Andrea Rotnitzky and Lue Ping Zhao , journal =

James M. Robins and Andrea Rotnitzky and Lue Ping Zhao , journal =. Estimation of Regression Coefficients When Some Regressors Are Not Always Observed , urldate =
[25]

Zhao, Y. Q. and Zeng, D. and Laber, E. B. and Song, R. and Yuan, M. and Kosorok, M. R. , title =. Biometrika , volume =. 2014 , month =

2014
[26]

2025 , journal=

Beating the Winner's Curse via Inference-Aware Policy Optimization , author=. 2025 , journal=

2025
[27]

Journal of Machine Learning Research , year =

Adith Swaminathan and Thorsten Joachims , title =. Journal of Machine Learning Research , year =
[28]

Operations Research , volume =

Offline Multi-Action Policy Learning: Generalization and Optimization , author =. Operations Research , volume =
[29]

Management Science , volume =

Policy Learning with Adaptively Collected Data , author =. Management Science , volume =
[30]

The Annals of Statistics , volume =

Performance Guarantees for Individualized Treatment Rules , author =. The Annals of Statistics , volume =

Pith tools

Reviewed July 12, 2026 · model on record in the stance chip above.

[1] [1]

arXiv preprint arXiv:2502.10653 , year=

Policy Learning with Confidence , author=. arXiv preprint arXiv:2502.10653 , year=

arXiv

[2] [2]

arXiv preprint arXiv:2505.14388 , year=

Algorithmic Hiring and Diversity: Reducing Human-Algorithm Similarity for Better Outcomes , author=. arXiv preprint arXiv:2505.14388 , year=

arXiv

[3] [3]

Communications of the ACM , volume=

A theory of the learnable , author=. Communications of the ACM , volume=. 1984 , publisher=

1984

[4] [4]

Nature , volume=

Efficient and targeted COVID-19 border testing via reinforcement learning , author=. Nature , volume=. 2021 , publisher=

2021

[5] [5]

Proceedings of the National Academy of Sciences , volume=

A 680,000-person megastudy of nudges to encourage vaccination in pharmacies , author=. Proceedings of the National Academy of Sciences , volume=. 2022 , publisher=

2022

[6] [6]

Proceedings of the 25th ACM Conference on Economics and Computation , pages=

When Is Heterogeneity Actionable for Targeting? , author=. Proceedings of the 25th ACM Conference on Economics and Computation , pages=

[7] [7]

Econometrica , volume=

Selecting the most effective nudge: Evidence from a large-scale experiment on immunization , author=. Econometrica , volume=. 2025 , publisher=

2025

[8] [8]

1985 , issn =

Asymptotically efficient adaptive allocation rules , journal =. 1985 , issn =

1985