Anytime-valid Optimal Policy Identification

• URL: http://arxiv.org/abs/2606.17515v1
• Date: Tue, 16 Jun 2026 04:49:19 GMT
• Title: Anytime-valid Optimal Policy Identification
• Abstract summary: We develop an anytime-valid framework for optimal policy identification from logged contextual bandit data.<n>This paper addresses challenges by constructing a time-indexed set $S_t$ that retains the true optimal policy set uniformly over time.<n>The resulting procedure allows the analyst to monitor policy values, eliminate clearly suboptimal policies, and stop at data-dependent times without invalidating inference.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop an anytime-valid framework for optimal policy identification from logged contextual bandit data. In many applied settings, the analyst wants to select the optimal policy from a candidate policy class $Π$, but data are generated by an externally determined logging policy that they do not control. The analyst may also wish to monitor evidence continuously, stopping once the optimal policy is clear rather than committing to a fixed sample size in advance. This paper addresses these challenges by constructing a time-indexed set $S_t$ that retains the true optimal policy set uniformly over time with high probability. The resulting procedure allows the analyst to monitor policy values, eliminate clearly suboptimal policies, and stop at data-dependent times without invalidating inference. When the optimal policy is unique, we define a stopping time for its identification and derive a sample-complexity bound scaling as $O\!\left(\frac{\log |Π|+\log\log(1/Δ_{\min})}{Δ_{\min}^2}\right)$, where $Δ_{\min}$ is the gap between the best and second-best policy values. Simulations demonstrate that the anytime-valid approach can yield substantial sample savings relative to fixed-$N$ designs. An application to a large adaptive experiment on reducing misinformation online illustrates how the method provides a dynamic view as evidence on the optimal policy accumulates.

Related papers

• Adaptive Policies for Resource Generation in a Quantum Network [0.5332865877117923]
  Protocols for distributed quantum systems commonly require simultaneous availability of $n$ entangled states.<n>We derive optimal policies that minimise the expected time until $n$ entangled states are available with fidelity greater than $F_mathrmapp$.
  arXiv  Detail & Related papers  (2025-09-22T11:04:12Z)
• Quantile-Optimal Policy Learning under Unmeasured Confounding [55.72891849926314]
  We study quantile-optimal policy learning where the goal is to find a policy whose reward distribution has the largest $alpha$-quantile for some $alpha in (0, 1)$.<n>Such a problem suffers from three main challenges: (i) nonlinearity of the quantile objective as a functional of the reward distribution, (ii) unobserved confounding issue, and (iii) insufficient coverage of the offline dataset.
  arXiv  Detail & Related papers  (2025-06-08T13:37:38Z)
• Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality [94.89246810243053]
  This paper studies offline policy learning, which aims at utilizing observations collected a priori to learn an optimal individualized decision rule.<n>Existing policy learning methods rely on a uniform overlap assumption, i.e., the propensities of exploring all actions for all individual characteristics must be lower bounded.<n>We propose Pessimistic Policy Learning (PPL), a new algorithm that optimize lower confidence bounds (LCBs) instead of point estimates.
  arXiv  Detail & Related papers  (2022-12-19T22:43:08Z)
• Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
  In episodic Block MDPs, the decision maker has access to rich observations or contexts generated from a small number of latent states. We are first interested in estimating the latent state decoding function based on data generated under a fixed behavior policy. We then study the problem of learning near-optimal policies in the reward-free framework.
  arXiv  Detail & Related papers  (2022-08-17T18:49:53Z)
• On Gap-dependent Bounds for Offline Reinforcement Learning [40.92345387517103]
  This paper presents a systematic study on gap-dependent sample complexity in offline reinforcement learning. Under the optimal policy coverage assumption, the rate can be improved to $Oleft(frac1epsilonright)$ when there is a positive sub-optimality gap in the optimal $Q$-function. We show when the visitation probabilities of the behavior policy are uniformly lower bounded for states where an optimal policy's visitation probabilities are positive, the sample complexity of identifying an optimal policy is independent of $frac1epsilon$.
  arXiv  Detail & Related papers  (2022-06-01T01:44:12Z)
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
  Robust decision processes (MDPs) provide a framework to model decision problems where the system dynamics are changing or only partially known. Recent work established the equivalence between texttts rectangular $L_p$ robust MDPs and regularized MDPs, and derived a regularized policy iteration scheme that enjoys the same level of efficiency as standard MDPs. In this work, we focus on the policy improvement step and derive concrete forms for the greedy policy and the optimal robust Bellman operators.
  arXiv  Detail & Related papers  (2022-05-28T04:05:20Z)
• Randomized Policy Optimization for Optimal Stopping [0.0]
  We propose a new methodology for optimal stopping based on randomized linear policies. We show that our approach can substantially outperform state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-03-25T04:33:15Z)
• Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
  We show that the preferability of optimization methods depends critically on whether exact gradients are used. Second, to explain these findings we introduce the concept of committal rate for policy optimization. Third, we show that in the absence of external oracle information, there is an inherent trade-off between exploiting geometry to accelerate convergence versus achieving optimality almost surely.
  arXiv  Detail & Related papers  (2021-10-29T06:35:44Z)
• Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning [43.61029925616256]
  offline policy evaluation in Reinforcement Learning (RL) is a critical step towards applying RL in real-life applications. We address this problem by simultaneously evaluating all policies in a policy class $Pi$ -- uniform convergence in OPE. Our results imply that the model-based planning achieves an optimal episode complexity of $widetildeO(H3/d_mepsilon2)$ in identifying an $epsilon$-optimal policy.
  arXiv  Detail & Related papers  (2020-07-07T19:44:14Z)
• Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation [49.502277468627035]
  This paper studies the statistical theory of batch data reinforcement learning with function approximation. Consider the off-policy evaluation problem, which is to estimate the cumulative value of a new target policy from logged history.
  arXiv  Detail & Related papers  (2020-02-21T19:20:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.