論文の概要: Contextual Bandits with Side-Observations
- arxiv url: http://arxiv.org/abs/2006.03951v2
- Date: Fri, 23 Oct 2020 21:27:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-24 21:04:56.094555
- Title: Contextual Bandits with Side-Observations
- Title（参考訳）: サイドオブザーバ付きコンテキスト帯域
- Authors: Rahul Singh, Fang Liu, Xin Liu, Ness Shroff
- Abstract要約: ソーシャルネットワークを介して接続されたユーザの推薦アルゴリズムを設計するために,両腕にサイドオブザーブメントが存在する場合のコンテキスト帯について検討する。
既存の学習アルゴリズムの素直な応用は、$Oleft(Nlog Tright)$ regretとなり、そこでは$N$がユーザ数であることを示す。
- 参考スコア（独自算出の注目度）: 10.248045133793287
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate contextual bandits in the presence of side-observations across
arms in order to design recommendation algorithms for users connected via
social networks. Users in social networks respond to their friends' activity,
and hence provide information about each other's preferences. In our model,
when a learning algorithm recommends an article to a user, not only does it
observe his/her response (e.g. an ad click), but also the side-observations,
i.e., the response of his neighbors if they were presented with the same
article. We model these observation dependencies by a graph $\mathcal{G}$ in
which nodes correspond to users, and edges correspond to social links. We
derive a problem/instance-dependent lower-bound on the regret of any consistent
algorithm. We propose an optimization (linear programming) based data-driven
learning algorithm that utilizes the structure of $\mathcal{G}$ in order to
make recommendations to users and show that it is asymptotically optimal, in
the sense that its regret matches the lower-bound as the number of rounds
$T\to\infty$. We show that this asymptotically optimal regret is upper-bounded
as $O\left(|\chi(\mathcal{G})|\log T\right)$, where $|\chi(\mathcal{G})|$ is
the domination number of $\mathcal{G}$. In contrast, a naive application of the
existing learning algorithms results in $O\left(N\log T\right)$ regret, where
$N$ is the number of users.
- Abstract（参考訳）: ソーシャルネットワークを介して接続されたユーザの推薦アルゴリズムを設計するために,両腕にサイドオブザーブメントが存在する場合のコンテキスト帯について検討する。
ソーシャルネットワークのユーザーは友人の活動に反応し、お互いの好みに関する情報を提供する。
我々のモデルでは,学習アルゴリズムがユーザに対して記事を推薦する場合,その反応(例えば広告クリック)を観察するだけでなく,隣人の反応(例えば,同じ記事が提示された場合)も観察する。
これらの観測依存性を,ノードがユーザに対応し,エッジがソーシャルリンクに対応するグラフ$\mathcal{g}$でモデル化する。
一貫性のあるアルゴリズムの後悔に基づく問題/インスタンス依存のローバウンドを導出する。
本稿では,ユーザが推奨する$\mathcal{G}$の構造を活かし,その不備がラウンド数$T\to\infty$と一致するという意味で,漸近的に最適であることを示すために,最適化(線形プログラミング)に基づくデータ駆動学習アルゴリズムを提案する。
この漸近的に最適な後悔は、$o\left(|\chi(\mathcal{g})|\log t\right)$ と上限づけられており、ここで$|\chi(\mathcal{g})|$ は$\mathcal{g}$ の支配数である。
対照的に、既存の学習アルゴリズムのナイーブな応用は、ユーザ数を$n$とする$o\left(n\log t\right)$ regretとなる。
関連論文リスト
- A statistical perspective on algorithm unrolling models for inverse
problems [2.7163621600184777]
観測値の条件分布が$bf y$で、興味のある変数が$bf x$であるような逆問題では、アルゴリズムのアンローリングを考える。
GDNsの最適統計性能に必要なアンローリング深さは、$log(n)/log(varrho_n-1)$で、$n$はサンプルサイズである。
また、潜伏変数 $bf x$ の負の対数密度が単純な近位演算子を持つとき、GDN は深さ $ でアンロールされることを示す。
論文 参考訳（メタデータ） (2023-11-10T20:52:20Z) - UniRank: Unimodal Bandit Algorithm for Online Ranking [0.0]
We create a algorithm with a expected regret matching $O(fracLlog(L)Deltalog(T))$ with $2L$ player, $T$ and a least reward gap $Delta$。
いくつかの実験結果は、これらの理論的な結果が実際に裏付けられていることを示している。
論文 参考訳（メタデータ） (2022-08-02T15:01:33Z) - A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with
Feedback Graphs [21.563733343861713]
フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。
本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T15:14:32Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - 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) - 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) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳（メタデータ） (2020-12-10T15:40:07Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。