論文の概要: Continuous-Time Multi-Armed Bandits with Controlled Restarts

• arxiv url: http://arxiv.org/abs/2007.00081v1
• Date: Tue, 30 Jun 2020 19:50:39 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-15 05:19:30.200074
• Title: Continuous-Time Multi-Armed Bandits with Controlled Restarts
• Title（参考訳）: 再始動を制御した連続時間多腕バンディット
• Authors: Semih Cayci, Atilla Eryilmaz, R. Srikant
• Abstract要約: 時間制約決定過程に対する再起動制御による帯域幅問題について検討する。 特に、各決定がランダムな完了時間を要し、最後にランダムで相関した報酬が得られるような帯域設定を考える。 我々は,再起動戦略の有限かつ連続的な行動空間において,$O(log(tau))$と$O(sqrttaulog(tau))$後悔を用いて効率的なオンライン学習アルゴリズムを開発する。
• 参考スコア（独自算出の注目度）: 32.63624728528415
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Time-constrained decision processes have been ubiquitous in many fundamental applications in physics, biology and computer science. Recently, restart strategies have gained significant attention for boosting the efficiency of time-constrained processes by expediting the completion times. In this work, we investigate the bandit problem with controlled restarts for time-constrained decision processes, and develop provably good learning algorithms. In particular, we consider a bandit setting where each decision takes a random completion time, and yields a random and correlated reward at the end, with unknown values at the time of decision. The goal of the decision-maker is to maximize the expected total reward subject to a time constraint $\tau$. As an additional control, we allow the decision-maker to interrupt an ongoing task and forgo its reward for a potentially more rewarding alternative. For this problem, we develop efficient online learning algorithms with $O(\log(\tau))$ and $O(\sqrt{\tau\log(\tau)})$ regret in a finite and continuous action space of restart strategies, respectively. We demonstrate an applicability of our algorithm by using it to boost the performance of SAT solvers.
• Abstract（参考訳）: 時間制約決定プロセスは、物理学、生物学、計算機科学の多くの基礎的な応用において、広く使われている。 近年, 再起動戦略が注目され, 完了時間を短縮し, 時間制約プロセスの効率化が図られている。 本研究では,時間制約付き決定プロセスにおける再起動制御による帯域幅問題について検討し,優れた学習アルゴリズムを開発した。 特に,各決定が無作為な終了時間を取るバンディット設定を検討し,最終決定時の未知の値と無作為で相関のある報酬を与える。 意思決定者の目標は、時間制約$\tau$の対象となる期待総報酬を最大化することである。 追加のコントロールとして、意思決定者が進行中のタスクを中断し、より報酬のある代替案に対する報酬を放棄できるようにします。 この問題に対して,我々は,再スタート戦略の有限および連続的な動作空間において,それぞれ$o(\log(\tau))$と$o(\sqrt{\tau\log(\tau)})$という効率的なオンライン学習アルゴリズムを開発した。 そこで本研究では,satソルバの性能向上を目的としたアルゴリズムの適用性を示す。

関連論文リスト

• Exploratory Optimal Stopping: A Singular Control Formulation [2.7309692684728613]
  強化学習の観点から,連続時間と状態空間の最適停止問題について検討する。 乱数停止時間の累積残エントロピーをペナル化することにより、問題の正規化版を導入する。 実オプション問題の特定の場合には、正規化問題に対する半明示的な解を導出する。
  論文  参考訳（メタデータ） (2024-08-18T02:31:55Z)
• Online Linear Programming with Batching [18.989352151219336]
  オンライン線形プログラミング(OLP)をOmegaで研究する。 後悔によって測定されたように、意思決定を遅らせる能力は、より良い運用パフォーマンスをもたらすことが示されます。 提案されたアルゴリズムはすべて、最初のバッチと最後のバッチにのみ到着する顧客の決定を遅らせる。
  論文  参考訳（メタデータ） (2024-08-01T06:13:24Z)
• Frugal Algorithm Selection [1.079960007119637]
  問題のすべてのインスタンスにうまく機能するアルゴリズムは存在しない。 本研究では、トレーニング対象のトレーニングインスタンスのサブセットを選択することで、このコストを削減する方法について検討する。 我々は,この問題を3つの方法でアプローチする: 能動的学習を用いて予測の不確実性に基づいて決定し, アルゴリズム予測器をタイムアウト予測器で拡張し, 徐々に増加するタイムアウトを用いてトレーニングデータを収集する。
  論文  参考訳（メタデータ） (2024-05-17T19:23:30Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。 この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。 有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
  論文  参考訳（メタデータ） (2022-05-16T15:47:41Z)
• Optimal Admission Control for Multiclass Queues with Time-Varying Arrival Rates via State Abstraction [16.99621896314678]
  我々は、意思決定者がランダムに到着したタスクを受け入れ、拒否する必要があるという、新しいキュー問題を考える。 目的は、処理されたタスクの総価格が有限の地平線上で最大になるように、どのタスクを受け入れるかを決定することである。 最適値関数は特定の構造を持ち、ハイブリッドMDPを正確に解くことができることを示す。
  論文  参考訳（メタデータ） (2022-03-14T12:38:13Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Learning to Schedule [3.5408022972081685]
  本稿では,ジョブが生み出す累積保持コストを最小限に抑えるための学習・スケジューリングアルゴリズムを提案する。 各タイムスロットにおいて、サーバはシステムに残されているジョブのランダム保持コストを受信しながらジョブを処理できる。
  論文  参考訳（メタデータ） (2021-05-28T08:04:06Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• Time-varying Gaussian Process Bandit Optimization with Non-constant Evaluation Time [93.6788993843846]
  非定常評価時間を効果的に処理できる新しい時間変化ベイズ最適化アルゴリズムを提案する。 我々の限界は、評価時間列のパターンが問題の難易度に大きな影響を与えることを決定づける。
  論文  参考訳（メタデータ） (2020-03-10T13:28:33Z)

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

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