論文の概要: The Influence of Shape Constraints on the Thresholding Bandit Problem
- arxiv url: http://arxiv.org/abs/2006.10006v3
- Date: Tue, 23 Feb 2021 09:27:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-19 19:42:04.432705
- Title: The Influence of Shape Constraints on the Thresholding Bandit Problem
- Title（参考訳）: 形状制約がしきい値化バンディット問題に及ぼす影響
- Authors: James Cheshire, Pierre Menard, Alexandra Carpentier
- Abstract要約: 本稿では,いくつかの形状制約の下でThresholding Bandit問題(TBP)について検討する。
TBP問題において、目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
後悔の最小値は (i) $sqrtlog(K)K/T$ for TBP, (ii) $sqrtlog(K)/T$ for UTBP, (iii) $sqrtK/T$ for CTBP, (iv) であることが証明されている。
- 参考スコア（独自算出の注目度）: 74.73898216415049
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the stochastic Thresholding Bandit problem (TBP) under several
shape constraints. On top of (i) the vanilla, unstructured TBP, we consider the
case where (ii) the sequence of arm's means $(\mu_k)_k$ is monotonically
increasing MTBP, (iii) the case where $(\mu_k)_k$ is unimodal UTBP and (iv) the
case where $(\mu_k)_k$ is concave CTBP. In the TBP problem the aim is to
output, at the end of the sequential game, the set of arms whose means are
above a given threshold. The regret is the highest gap between a misclassified
arm and the threshold. In the fixed budget setting, we provide problem
independent minimax rates for the expected regret in all settings, as well as
associated algorithms. We prove that the minimax rates for the regret are (i)
$\sqrt{\log(K)K/T}$ for TBP, (ii) $\sqrt{\log(K)/T}$ for MTBP, (iii)
$\sqrt{K/T}$ for UTBP and (iv) $\sqrt{\log\log K/T}$ for CTBP, where $K$ is the
number of arms and $T$ is the budget. These rates demonstrate that the
dependence on $K$ of the minimax regret varies significantly depending on the
shape constraint. This highlights the fact that the shape constraints modify
fundamentally the nature of the TBP.
- Abstract（参考訳）: 本稿では,いくつかの形状制約の下で,確率的閾値帯域問題(TBP)について検討する。
上に
(i) バニラ型非構造型tbpの場合
(ii) arm 平均 $(\mu_k)_k$ のシーケンスは単調に mtbp を増加させる。
(iii)$(\mu_k)_k$ がユニモーダルな utbp である場合
(iv)$(\mu_k)_k$がconcave CTBPである場合。
TBP問題において、目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
後悔は、誤分類された腕と閾値の間の最も高いギャップである。
固定予算設定では、全ての設定において期待される後悔に対する問題独立ミニマックスレートと関連するアルゴリズムを提供する。
私たちは後悔のミニマックスレートが正しいことを証明します。
(i)$\sqrt{\log(K)K/T}$ for TBP,
(ii) mtbpに対して$\sqrt{\log(k)/t}$
(iii)$\sqrt{K/T}$ for UTBP and
(iv)$\sqrt{\log\log k/t}$ for ctbp ここで$k$は腕の数、$t$は予算である。
これらのレートは、ミニマックスの後悔の$k$への依存が形状の制約によって大きく異なることを示している。
これは、形状制約がtbpの性質を根本的に変えるという事実を強調している。
関連論文リスト
- Improved Bound for Robust Causal Bandits with Linear Models [16.60875994745622]
本稿では,時間的モデル変動に直面した因果包帯のロバスト性について検討する。
提案アルゴリズムは,$C$が$o(sqrtT)$の場合に,ほぼ最適な$tildemathcalO(sqrtT)$後悔を達成する。
論文 参考訳（メタデータ） (2024-05-13T14:41:28Z) - Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。
逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。
我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
論文 参考訳（メタデータ） (2023-11-02T03:41:58Z) - Robust Causal Bandits for Linear Models [20.028245872662843]
因果系における報酬関数を最適化するための実験の逐次設計は、因果包帯における介入の逐次設計(CB)により効果的にモデル化できる。
本稿では,このようなモデルゆらぎに対するCBの頑健性について述べる。
累積後悔は設計基準として採用され、その目的は、因果モデル全体とその変動を意識したオラクルに対して最小の累積後悔を引き起こす一連の介入を設計することである。
論文 参考訳（メタデータ） (2023-10-30T17:58:01Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。
我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。
本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文 参考訳（メタデータ） (2022-04-11T15:08:09Z) - Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。
当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
論文 参考訳（メタデータ） (2021-09-29T14:07:21Z) - Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。
学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
論文 参考訳（メタデータ） (2021-06-18T15:01:01Z) - Stochastic Shortest Path: Minimax, Parameter-Free and Towards
Horizon-Free Regret [144.6358229217845]
エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。
我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。
私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
論文 参考訳（メタデータ） (2021-04-22T17:20:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。