論文の概要: Unimodal Mono-Partite Matching in a Bandit Setting

• arxiv url: http://arxiv.org/abs/2208.01511v1
• Date: Tue, 2 Aug 2022 14:55:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-03 13:42:40.704494
• Title: Unimodal Mono-Partite Matching in a Bandit Setting
• Title（参考訳）: バンディット設定におけるユニモーダルモノパーティタイトマッチング
• Authors: Romaric Gaudel (ENSAI, CREST), Matthieu Rodet (ENS Rennes)
• Abstract要約: We create a algorithm with a expected regret matching $O(fracLlog(L)Deltalog(T))$ with $2L$ player, $T$ and a least reward gap $Delta$。 いくつかの実験結果は、これらの理論的な結果が実際に裏付けられていることを示している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We tackle a new emerging problem, which is finding an optimal monopartite matching in a weighted graph. The semi-bandit version, where a full matching is sampled at each iteration, has been addressed by \cite{ADMA}, creating an algorithm with an expected regret matching $O(\frac{L\log(L)}{\Delta}\log(T))$ with $2L$ players, $T$ iterations and a minimum reward gap $\Delta$. We reduce this bound in two steps. First, as in \cite{GRAB} and \cite{UniRank} we use the unimodality property of the expected reward on the appropriate graph to design an algorithm with a regret in $O(L\frac{1}{\Delta}\log(T))$. Secondly, we show that by moving the focus towards the main question `\emph{Is user $i$ better than user $j$?}' this regret becomes $O(L\frac{\Delta}{\tilde{\Delta}^2}\log(T))$, where $\Tilde{\Delta} > \Delta$ derives from a better way of comparing users. Some experimental results finally show these theoretical results are corroborated in practice.
• Abstract（参考訳）: 我々は,重み付きグラフにおける最適単成分マッチングを求める新たな問題に取り組む。 半バンドバージョンは、各イテレーションで完全なマッチングがサンプリングされるが、 \cite{ADMA} によって対処され、期待される後悔のマッチングが$O(\frac{L\log(L)}{\Delta}\log(T))$で$2L$プレーヤー、$T$イテレーション、最小報酬ギャップ$\Delta$でアルゴリズムを作成する。 この制限を 2 段階減らします. まず、 \cite{GRAB} や \cite{UniRank} のように、適切なグラフ上の期待される報酬の一様性を使って、$O(L\frac{1}{\Delta}\log(T))$で後悔したアルゴリズムを設計する。 第二に、焦点をメインの質問 “\emph{Is user $i$ better than user $j$? この後悔は、$O(L\frac{\Delta}{\tilde{\Delta}^2}\log(T))$となり、$\Tilde{\Delta} > \Delta$は、ユーザーを比較するより良い方法に由来する。 いくつかの実験結果は、これらの理論的な結果が実際に裏付けられていることを示している。

関連論文リスト

• Online Matrix Completion: A Collaborative Approach with Hott Items [19.781869063637387]
  M$ユーザ,$N$アイテム,$T$ラウンド,未知のランク-$r$報酬行列$Rin mathbbRMtimes N$のオンライン設定における下位行列補完問題について検討する。
  論文  参考訳（メタデータ） (2024-08-11T18:49:52Z)
• 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)
• Delaytron: Efficient Learning of Multiclass Classifiers with Delayed Bandit Feedbacks [6.624726878647541]
  Adaptive Delaytronは、$mathcalOleft(sqrtfrac2 Kgammaleft[fracT2+left(2+fracL2R2Vert WVert_F2right)sum_t=1Td_tright)の後悔の限界を達成する。 我々は、Adaptive Delaytronが$mathcalOleft(sqrtfrac2 Kgammaleft[fracT2]の後悔の限界を達成することを示す。
  論文  参考訳（メタデータ） (2022-05-17T11:12:20Z)
• 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)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
  シャッフルモデルにおけるマルチアームバンディット(MAB)問題に対して,$(varepsilon,delta)$-differentially privateアルゴリズムを提案する。 我々の上限は、集中モデルにおいて最もよく知られたアルゴリズムの後悔とほぼ一致し、局所モデルにおいて最もよく知られたアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2021-06-05T14:11:01Z)
• 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)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)
• 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)

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

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