Anytime-valid Optimal Policy Identification

Technical Summary: Anytime-Valid Optimal Policy Identification

1. Problem Statement

The paper addresses the challenge of identifying an optimal policy ($\pi^\star$) from a finite candidate class $\Pi = \{\pi_1, \dots, \pi_m\}$ using logged contextual bandit data. In many practical settings, data are generated by an externally determined logging policy ($h_t$) that the analyst does not control. This logging policy may be a fixed randomization or an adaptive algorithm tuned for objectives other than the analyst's specific goal (e.g., maximizing user engagement rather than minimizing misinformation).

The core difficulty lies in two constraints:

1. Off-Policy Setting: The analyst must infer the value of target policies $\nu(\pi)$ using data collected under a different policy $h_t$, without the ability to steer data collection toward the identification goal.
2. Sequential Monitoring: Practitioners often wish to monitor evidence continuously, eliminate clearly suboptimal policies as data accrue, and stop data collection once the optimal policy is identified, rather than committing to a fixed sample size ($N$) in advance.

Existing literature on optimal policy identification typically assumes the analyst controls data collection (adaptive sampling) or provides inferential guarantees only at a fixed, pre-specified sample size. This paper seeks to bridge the gap by providing anytime-valid guarantees for off-policy optimal policy identification.

2. Methodology

The proposed framework constructs a time-indexed set of candidate optimal policies, $S_t$, which evolves as data arrives. The methodology relies on three main components:

A. Doubly Robust Pseudo-Outcomes
To estimate policy values $\nu(\pi)$ from logged data, the method utilizes importance weights $w_t(\pi) = \pi(A_t|X_t) / h_t(A_t|X_t)$. To improve efficiency and stability, these are combined with a reward model $b_{rt}(x,a)$ to construct doubly robust (DR) pseudo-outcomes. Specifically, lower and upper pseudo-outcomes ($\phi^{DRL}_t$ and $\phi^{DRU}_t$) are defined such that their conditional expectations equal the true policy value $\nu(\pi)$ and $1-\nu(\pi)$, respectively. Crucially, validity does not depend on the reward model being correctly specified, only on the known logging probabilities.

B. Anytime-Valid Confidence Sequences (CS)
Building on the work of Waudby-Smith et al. (2024), the paper constructs confidence sequences for the policy values. A sequence of intervals $[L_t(\pi), U_t(\pi)]$ is a $(1-\alpha)$-CS if the true value $\nu(\pi)$ remains within the interval for all $t \geq 1$ with probability at least $1-\alpha$. These intervals are constructed using the DR pseudo-outcomes and a variance process $V_t(\pi)$ that accounts for the accumulation of evidence. The width of these intervals shrinks at a rate of $O(\sqrt{(\log \log t + \log m)/t})$.

C. Sequential Elimination and Stopping Rule
Using a union bound over the policy class $\Pi$, the method constructs simultaneous confidence sequences for all policies. The candidate set $S_t$ is defined as:
$$S_t := \left\{ \pi \in \Pi : U_t\left(\pi; \frac{\alpha}{m}\right) \geq \max_{\pi' \in \Pi} L_t\left(\pi'; \frac{\alpha}{m}\right) \right\}$$
A policy is eliminated from $S_t$ if its upper confidence bound falls below the maximum lower confidence bound of any competing policy. The procedure stops at a data-dependent time $\tau$ when $S_\tau$ becomes a singleton (containing only one policy).

3. Key Contributions

The paper makes two primary theoretical contributions:

1. Anytime-Valid Coverage Guarantee: The authors prove that the constructed set $S_t$ satisfies a uniform coverage guarantee:
   $$P(\Pi^\star \subseteq S_t \text{ for all } t \geq 1) \geq 1 - \alpha$$
   where $\Pi^\star$ is the set of true optimal policies. This ensures that with high probability, no optimal policy is ever eliminated, regardless of when the analyst chooses to stop.

2. Sample Complexity Bounds: When the optimal policy $\pi^\star$ is unique, the paper defines a stopping time $\tau$ for its identification. Under a regularity condition of linear variance growth (Assumption 1), the sample complexity is derived as:
   $$\tau = O\left( \frac{\log m + \log \log(1/\Delta_{\min})}{\Delta_{\min}^2} \right)$$
   where $\Delta_{\min}$ is the gap between the best and second-best policy values. This bound indicates that the number of samples required scales logarithmically with the policy class size and inversely with the square of the suboptimality gap.

4. Empirical Results

The paper validates the framework through three empirical demonstrations:

• Synthetic Illustration: In a simulated contextual bandit setting with six policies, the framework successfully eliminated clearly suboptimal policies early in the data stream while retaining the optimal policy until it was uniquely identified. The confidence sequences for policy values converged to the true values as expected.
• Sample Efficiency: Comparing the anytime-valid procedure against a fixed-$N$ design (where $N$ is calculated based on a target gap), the authors found substantial sample savings when the true suboptimality gap was larger than the target gap. For instance, if the true gap was twice the target gap, the anytime-valid method saved 60–80% of the planned sample size on average.
• Real-World Application: The method was applied to a large adaptive experiment (Offer-Westort et al., 2024) involving 15,292 users in Kenya and Nigeria, aimed at reducing misinformation sharing. The framework replicated the original study's conclusion (identifying "accuracy nudge" and "Facebook tips" as top performers) but provided a dynamic view of the evidence accumulation. It showed that the worst-performing policies could be eliminated with only a fraction of the final data, while the top candidates remained in the candidate set throughout.

5. Significance and Limitations

Significance:
The paper provides a rigorous inferential framework for sequential monitoring in off-policy settings. It allows analysts to make data-dependent stopping decisions without invalidating statistical guarantees, addressing a key limitation of fixed-$N$ approaches. This is particularly valuable in real-world applications where data collection is constrained by external logging policies and resources are limited.

Limitations:
The authors explicitly note two limitations:

1. Time-Invariance: The framework assumes policy values are constant over time. It does not currently handle non-stationary environments where treatment effects evolve (e.g., due to novelty or fatigue).
2. Overlap Requirement: The method requires that every target policy be absolutely continuous with respect to the logging policy (strict overlap). This excludes scenarios where the logging policy deterministically assigns zero probability to actions that a target policy would take, which can occur in highly concentrated adaptive algorithms (e.g., UCB-style).

The paper concludes that while these limitations exist, the framework offers a robust solution for a broad class of stochastic logging policies commonly found in practice.