Stochastic optimization models sequential decision-making under uncertainty, typically assuming known input distributions. When these distributions are unknown, \citet{agarwal2026semibandit} give an online-to-offline reduction for monotone stochastic optimization under semi-bandit feedback, where only probed variables are observed. Its expected regret relative to the offline guarantee is
O ~ ( n T ) \widetilde O(n\sqrt T) O ( n T ) , where
n n n is the number of variables and
T T T the horizon. For optimal stopping and Pandora's box, \citet{liu2025improved} achieve
O ~ ( n T ) \widetilde O(\sqrt{nT}) O ( n T ) using problem-specific algorithms.
Can a general online-to-offline reduction achieve this improved rate? We give such a reduction for strongly monotone stochastic optimization, answering the corresponding open question. Strong monotonicity is defined relative to the chosen offline algorithm. Our oracle-efficient reduction achieves
O ~ ( n T ) \widetilde O(\sqrt{nT}) O ( n T ) expected regret while preserving approximation guarantees for oracles satisfying the same condition. It combines Bernstein-type optimistic distribution estimates with a Hellinger stability bound for adaptive policy transcripts, aggregating squared marginal errors weighted by the executed policy's probing probabilities. The rate is optimal up to logarithmic factors for
T ≥ n T\ge n T ≥ n , even under full feedback. Under monotonicity and uniformly bounded coordinate-wise variation, the same algorithm achieves
O ~ ( n 3 / 4 T ) \widetilde O(n^{3/4}\sqrt T) O ( n 3/4 T ) expected approximation regret, improving the previous linear dependence on
n n n . The exponent
3 / 4 3/4 3/4 is sharp for its ordinary regret over instances and exact oracle choices. Our framework applies to prophet inequality, Pandora's box, best-of-
K K K selection, stochastic knapsack, stochastic orienteering, and stochastic submodular maximization.