論文の概要: Online Algorithms for Repeated Optimal Stopping: Achieving Both Competitive Ratio and Regret Bounds

• arxiv url: http://arxiv.org/abs/2511.04484v1
• Date: Thu, 06 Nov 2025 16:04:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-07 20:17:53.489999
• Title: Online Algorithms for Repeated Optimal Stopping: Achieving Both Competitive Ratio and Regret Bounds
• Title（参考訳）: 反復最適停止のためのオンラインアルゴリズム:競合率とレグレト境界の両方を達成する
• Authors: Tsubasa Harada, Yasushi Kawase, Hanna Sumita,
• Abstract要約: 古典的最適停止問題を未知分布で一般化する反復最適停止問題について検討する。 我々は,各ラウンドにおける競争率を保証するアルゴリズムを設計し,全ラウンドにおけるサブ線形後悔を実現することを目的としている。 我々は,不等式,秘書問題,および逆数モデル,ランダムモデルおよびi.d.入力モデルの下でのそれらの変種など,我々のフレームワークが正準問題に広く適用可能であることを実証する。
• 参考スコア（独自算出の注目度）: 7.858819231575403
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the repeated optimal stopping problem, which generalizes the classical optimal stopping problem with an unknown distribution to a setting where the same problem is solved repeatedly over $T$ rounds. In this framework, we aim to design algorithms that guarantee a competitive ratio in each round while also achieving sublinear regret across all rounds. Our primary contribution is a general algorithmic framework that achieves these objectives simultaneously for a wide array of repeated optimal stopping problems. The core idea is to dynamically select an algorithm for each round, choosing between two candidates: (1) an empirically optimal algorithm derived from the history of observations, and (2) a sample-based algorithm with a proven competitive ratio guarantee. Based on this approach, we design an algorithm that performs no worse than the baseline sample-based algorithm in every round, while ensuring that the total regret is bounded by $\tilde{O}(\sqrt{T})$. We demonstrate the broad applicability of our framework to canonical problems, including the prophet inequality, the secretary problem, and their variants under adversarial, random, and i.i.d. input models. For example, for the repeated prophet inequality problem, our method achieves a $1/2$-competitive ratio from the second round on and an $\tilde{O}(\sqrt{T})$ regret. Furthermore, we establish a regret lower bound of $\Omega(\sqrt{T})$ even in the i.i.d. model, confirming that our algorithm's performance is almost optimal with respect to the number of rounds.
• Abstract（参考訳）: そこで本研究では,古典的最適停止問題を未知の分布で一般化し,同じ問題をT$ラウンドで繰り返し解決する手法について検討する。 本フレームワークでは,各ラウンドにおける競争率を保証するアルゴリズムを設計するとともに,全ラウンドにおけるサブ線形後悔を実現することを目的としている。 我々の主な貢献は、これらの目的を同時に達成する汎用的なアルゴリズムフレームワークである。 その中核となる考え方は,(1)観察履歴から得られた経験的最適アルゴリズム,(2)競争力の保証が証明されたサンプルベースアルゴリズムの2つの候補を選択することで,各ラウンドのアルゴリズムを動的に選択することである。 このアプローチに基づいて,各ラウンドにおける基準サンプルベースアルゴリズムよりも悪い結果が得られないアルゴリズムを設計し,全後悔が$\tilde{O}(\sqrt{T})$で束縛されることを保証する。 我々は,不等式,秘書問題,および逆数モデル,ランダムモデルおよびi.d.入力モデルの下でのそれらの変種など,我々のフレームワークが正準問題に広く適用可能であることを実証する。 例えば、反復的預言不等式問題に対して、この手法は第2ラウンド以降と$\tilde{O}(\sqrt{T})$ regretから1/2$-competitive ratioを達成している。 さらに、i.d.モデルにおいても、後悔の少ない$\Omega(\sqrt{T})$の値を確立し、このアルゴリズムの性能がラウンド数に対してほぼ最適であることを確認した。

関連論文リスト

• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。 A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-08-23T08:38:53Z)
• Contextual Decision-Making with Knapsacks Beyond the Worst Case [5.65888994172721]
  資源制約を伴う動的意思決定シナリオの枠組みについて検討する。 このフレームワークでは、エージェントがランダムな要求を観察すると、各ラウンドでアクションを選択する。 我々のアルゴリズムは最悪の場合であっても、ほぼ最適の$widetildeO(sqrtT)$ regretを維持していることを証明している。
  論文  参考訳（メタデータ） (2022-11-25T08:21:50Z)
• Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits [27.279654173896372]
  我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。 これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
  論文  参考訳（メタデータ） (2021-11-06T16:46:55Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。 最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
  論文  参考訳（メタデータ） (2020-06-16T15:33:12Z)
• Rate-adaptive model selection over a collection of black-box contextual bandit algorithms [0.966840768820136]
  文脈的帯域設定におけるモデル選択タスクについて検討する。 我々の提案は、一般的なブラックボックス・コンテクスト・バンディットアルゴリズムの収集に適応する最初のものである。
  論文  参考訳（メタデータ） (2020-06-05T18:55:16Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)
• A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate Rates [16.54912614895861]
  我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。 我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。 その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
  論文  参考訳（メタデータ） (2020-03-03T03:59:26Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。