{
  "abstract": "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 $\\widetilde O(n\\sqrt T)$, where $n$ is the number of variables and $T$ the horizon. For optimal stopping and Pandora's box, \\citet{liu2025improved} achieve $\\widetilde O(\\sqrt{nT})$ using problem-specific algorithms. \\emph{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 $\\widetilde O(\\sqrt{nT})$ 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\\ge n$, even under full feedback. Under monotonicity and uniformly bounded coordinate-wise variation, the same algorithm achieves $\\widetilde O(n^{3/4}\\sqrt T)$ expected approximation regret, improving the previous linear dependence on $n$. The exponent $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$ selection, stochastic knapsack, stochastic orienteering, and stochastic submodular maximization.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.17320",
  "author_total": 2,
  "authors": [
    {
      "name": "Tao Hu"
    },
    {
      "name": "Rohan Ghuge"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/1m57g6nt9kkf8.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.17320",
  "fulltext_url": null,
  "id": "1m57g6nt9kkf8",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.17320",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "cs.LG"
    ],
    [
      "arxiv",
      "stat.ML"
    ],
    [
      "openalex",
      "1803|Advanced Bandit Algorithms Research"
    ]
  ],
  "openalex": "W7221786176",
  "pdf_url": "https://arxiv.org/pdf/2610.17320",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-12",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/1m57g6nt9kkf8.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:29:26Z",
      "native_id": "2610.17320",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.17320"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:stat.ML",
      "subfield": "statistics"
    }
  ],
  "title": "Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback",
  "title_text": "Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback",
  "type": "preprint",
  "updated_at": "2026-10-30T12:29:26Z",
  "url": "https://research.draconitic.com/paper/1m57g6nt9kkf8",
  "venue": "arXiv",
  "versions": []
}