論文の概要: Optimal Strategies for Graph-Structured Bandits
- arxiv url: http://arxiv.org/abs/2007.03224v2
- Date: Fri, 10 Jul 2020 09:17:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-12 20:37:47.904998
- Title: Optimal Strategies for Graph-Structured Bandits
- Title(参考訳): グラフ構造バンディットの最適戦略
- Authors: Hassan Saber (SEQUEL), Pierre M\'enard (SEQUEL), Odalric-Ambrym
Maillard (SEQUEL)
- Abstract要約: Bernoulli $!=!(nu_a,b)_a in mathcalA, b in mathcalB$ with means $(mu_a,b)_a in mathcalA, b in mathcalB$ with means $(mu_a,b)_a
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a structured variant of the multi-armed bandit problem specified by
a set of Bernoulli distributions $ \nu \!= \!(\nu\_{a,b})\_{a \in \mathcal{A},
b \in \mathcal{B}}$ with means $(\mu\_{a,b})\_{a \in \mathcal{A}, b \in
\mathcal{B}}\!\in\![0,1]^{\mathcal{A}\times\mathcal{B}}$ and by a given weight
matrix $\omega\!=\! (\omega\_{b,b'})\_{b,b' \in \mathcal{B}}$, where $
\mathcal{A}$ is a finite set of arms and $ \mathcal{B} $ is a finite set of
users. The weight matrix $\omega$ is such that for any two users
$b,b'\!\in\!\mathcal{B}, \text{max}\_{a\in\mathcal{A}}|\mu\_{a,b} \!-\!
\mu\_{a,b'}| \!\leq\! \omega\_{b,b'} $. This formulation is flexible enough to
capture various situations, from highly-structured scenarios
($\omega\!\in\!\{0,1\}^{\mathcal{B}\times\mathcal{B}}$) to fully unstructured
setups ($\omega\!\equiv\! 1$).We consider two scenarios depending on whether
the learner chooses only the actions to sample rewards from or both users and
actions. We first derive problem-dependent lower bounds on the regret for this
generic graph-structure that involves a structure dependent linear programming
problem. Second, we adapt to this setting the Indexed Minimum Empirical
Divergence (IMED) algorithm introduced by Honda and Takemura (2015), and
introduce the IMED-GS$^\star$ algorithm. Interestingly, IMED-GS$^\star$ does
not require computing the solution of the linear programming problem more than
about $\log(T)$ times after $T$ steps, while being provably asymptotically
optimal. Also, unlike existing bandit strategies designed for other popular
structures, IMED-GS$^\star$ does not resort to an explicit forced exploration
scheme and only makes use of local counts of empirical events. We finally
provide numerical illustration of our results that confirm the performance of
IMED-GS$^\star$.
- Abstract(参考訳): ベルヌーイ分布の集合によって定義される多武装バンディット問題の構造化変種について研究する。
= \!
(\nu\_{a,b})\_{a \in \mathcal{A}, b \in \mathcal{B}}$ with means $(\mu\_{a,b})\_{a \in \mathcal{A}, b \in \mathcal{B}}\!
イン!
[0,1]^{\mathcal{A}\times\mathcal{B}}$ そして与えられた重み行列$\omega\!
=\!
(\omega\_{b,b'})\_{b,b' \in \mathcal{B}}$, ここで $ \mathcal{A}$ は有限個のアームの集合、 $ \mathcal{B} $ は有限個のユーザ集合である。
重み行列 $\omega$ は、任意の 2 ユーザに対して $b,b'\!
イン!
\mathcal{B}, \text{max}\_{a\in\mathcal{A}}|\mu\_{a,b} \!
-\!
b' {\displaystyle b'}|\,b'} である。
くたばれ!
\omega\_{b,b'} $。
この定式化は、高度に構造化されたシナリオ($\omega\!
イン!
\{0,1\}^{\mathcal{b}\times\mathcal{b}}$) 完全に構造化されていないセットアップ ($\omega\!
\equiv\!
1$).
我々は,学習者が報酬をサンプリングする行動のみを選択するか,ユーザと行動の両方を選択するかの2つのシナリオを考察する。
まず、構造依存線形計画問題を含むこの一般的なグラフ構造に対する後悔に関する問題依存下限を導出する。
第2に本田と竹村(2015)が導入したindexed minimum empirical divergence(imed)アルゴリズムの設定に適応し,imed-gs$^\star$アルゴリズムを導入する。
興味深いことに、imed-gs$^\star$は、t$ステップの後に約$\log(t)$倍の線形計画問題の解を計算する必要はないが、漸近的に最適である。
また、他の一般的な構造向けに設計された既存のバンディット戦略とは異なり、imed-gs$^\star$は明示的な強制探査スキームを頼らず、経験的な事象の局所的なカウントのみを使用する。
最終的に IMED-GS$^\star$ の性能を確認する数値図式を提供する。
関連論文リスト
- Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。
我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。
このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
論文 参考訳(メタデータ) (2024-02-22T02:20:24Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。
mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
論文 参考訳(メタデータ) (2023-10-02T16:44:47Z) - Distribution-Independent Regression for Generalized Linear Models with
Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。
本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。
これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文 参考訳(メタデータ) (2023-09-20T21:41:59Z) - A/B Testing and Best-arm Identification for Linear Bandits with
Robustness to Non-stationarity [28.068960555415014]
非定常環境下での線形包帯の固定予算ベストアーム識別問題について検討する。
アルゴリズムは、可能な限り高い確率で最適な腕 $x* := argmax_xinmathcalXxtopsum_t=1Ttheta_t$ を正しく識別することを目的としている。
論文 参考訳(メタデータ) (2023-07-27T19:03:36Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Randomized and Deterministic Attention Sparsification Algorithms for
Over-parameterized Feature Dimension [18.57735939471469]
我々は注意問題のスパシフィケーションを考慮する。
超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
論文 参考訳(メタデータ) (2023-04-10T05:52:38Z) - A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。
このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。
我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
論文 参考訳(メタデータ) (2023-02-01T05:22:40Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳(メタデータ) (2021-03-10T07:33:03Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳(メタデータ) (2021-02-15T08:16:51Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳(メタデータ) (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。