論文の概要: Continuous Time Bandits With Sampling Costs
- arxiv url: http://arxiv.org/abs/2107.05289v2
- Date: Wed, 19 Apr 2023 12:36:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-20 18:36:18.452914
- Title: Continuous Time Bandits With Sampling Costs
- Title（参考訳）: サンプリングコストによる継続的時間帯
- Authors: Rahul Vaze and Manjesh K. Hanawal
- Abstract要約: 連続時間マルチアームバンディット問題 (CTMAB) を考えると, 学習者は任意の間隔で何回でもアームをサンプリングし, サンプルからランダムな報酬を得ることができる。
サンプリング周波数の関数として、大きな報酬を得ることとサンプリングコストをもたらすことにはトレードオフがある。
目的は後悔を最小限に抑える学習アルゴリズムを設計することであり、これはオラクルのポリシーと学習アルゴリズムの報酬の差として定義される。
- 参考スコア（独自算出の注目度）: 17.412117389855222
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider a continuous-time multi-arm bandit problem (CTMAB), where the
learner can sample arms any number of times in a given interval and obtain a
random reward from each sample, however, increasing the frequency of sampling
incurs an additive penalty/cost. Thus, there is a tradeoff between obtaining
large reward and incurring sampling cost as a function of the sampling
frequency. The goal is to design a learning algorithm that minimizes regret,
that is defined as the difference of the payoff of the oracle policy and that
of the learning algorithm. CTMAB is fundamentally different than the usual
multi-arm bandit problem (MAB), e.g., even the single-arm case is non-trivial
in CTMAB, since the optimal sampling frequency depends on the mean of the arm,
which needs to be estimated. We first establish lower bounds on the regret
achievable with any algorithm and then propose algorithms that achieve the
lower bound up to logarithmic factors. For the single-arm case, we show that
the lower bound on the regret is $\Omega((\log T)^2/\mu)$, where $\mu$ is the
mean of the arm, and $T$ is the time horizon. For the multiple arms case, we
show that the lower bound on the regret is $\Omega((\log T)^2 \mu/\Delta^2)$,
where $\mu$ now represents the mean of the best arm, and $\Delta$ is the
difference of the mean of the best and the second-best arm. We then propose an
algorithm that achieves the bound up to constant terms.
- Abstract（参考訳）: 連続時間マルチアームバンディット問題 (CTMAB) を考えると、学習者は任意の間隔でアームを何回でもサンプリングでき、各サンプルからランダムな報酬を得ることができるが、サンプリング頻度の増加は付加的なペナルティ/コストをもたらす。
したがって、サンプリング周波数の関数として、大きな報酬を得ることと、かかるサンプリングコストとのトレードオフが生じる。
目的は後悔を最小限に抑える学習アルゴリズムを設計することであり、これはオラクルのポリシーと学習アルゴリズムの報酬の差として定義される。
CTMABは、通常のマルチアームバンディット問題(MAB)と根本的に異なる、例えば、単一アームの場合でさえCTMABでは、最適なサンプリング周波数が推定される腕の平均に依存するため、非自明である。
まず,任意のアルゴリズムで達成可能な後悔の限界を低く設定し,対数的要因までの範囲を低くするアルゴリズムを提案する。
単腕の場合、後悔の上の下限は$\omega((\log t)^2/\mu)$であり、ここで$\mu$は腕の平均であり、$t$は時間軸である。
多重腕の場合、後悔の上の下限は$\omega((\log t)^2 \mu/\delta^2)$であり、ここで$\mu$は最高の腕の平均を表し、$\delta$は最高の腕と2番目の腕の平均の差である。
次に,定数項へのバウンドを達成するアルゴリズムを提案する。
関連論文リスト
- A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
最適な腕識別問題に対する最適トップ2型アルゴリズムを提案する。
提案アルゴリズムは$delta rightarrow 0$として最適であることを示す。
論文 参考訳（メタデータ） (2024-03-14T06:14:07Z) - Combinatorial Bandits for Maximum Value Reward Function under Max
Value-Index Feedback [9.771002043127728]
本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。
有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。
我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
論文 参考訳（メタデータ） (2023-05-25T14:02:12Z) - Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。
我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
論文 参考訳（メタデータ） (2023-04-25T09:31:20Z) - Revisiting Simple Regret Minimization in Multi-Armed Bandits [33.88679679593314]
単純な後悔は、最高の腕や$epsilon$-good腕を欠く確率よりもあまり一般的ではない。
本稿では,データ豊かさ (Tge n$) とデータ貧弱さ (T le n$) の両面において,単純な後悔の上限を改良した。
より困難なデータ・ポーア・レシエーションのために、少なくとも1回は各腕をサンプリングすることなく、同じ改善を享受できるブラッケティングSH(BSH)を提案する。
論文 参考訳（メタデータ） (2022-10-30T18:31:03Z) - PAC Best Arm Identification Under a Deadline [101.10352416022559]
我々は、$(epsilon, delta)$-PACベストアーム識別について研究し、意思決定者は、アームプル(サンプル)の数を最小化しながら、少なくとも1 - delta$の確率で最適なアームを識別しなければならない。
この作業では、決定者はT$ラウンドの期限が与えられ、各ラウンドで、どのアームを引っ張るか、何回引っ張るかを適応的に選ぶことができる。
本稿では,この設定のための新しいアルゴリズムであるElastic Batch Racing (EBR)を提案する。
論文 参考訳（メタデータ） (2021-06-06T19:48:32Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Quantum exploration algorithms for multi-armed bandits [15.666205208594567]
我々は、$tildeObigl(sqrtsum_i=2nDeltasmash-2_ibigr)$quantum query.sqrtsum_i=2nDeltasmash-2_ibigr)を用いて、信頼度の高い最適なアームを見つけることができることを示す。
このアルゴリズムは、可変時間振幅増幅と推定に基づいて、可能な限りの古典的な結果と比較して二次的なスピードアップを与える。
論文 参考訳（メタデータ） (2020-07-14T14:15:20Z) - Blocking Bandits [33.14975454724348]
我々は、腕を弾くことで固定時間帯で使用できなくなる、新しいマルチアームバンディット・セッティングについて考察する。
全ての武器の報酬と遅延の事前知識により、累積報酬を最適化する問題は擬似多項式時間アルゴリズムを含まないことを示した。
我々は,このアルゴリズムに対して,$c log T + o(log T)$ cumulative regret を持つ UCB ベースのアルゴリズムを設計する。
論文 参考訳（メタデータ） (2019-07-27T20:42:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。