論文の概要: Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards

• arxiv url: http://arxiv.org/abs/2004.06248v2
• Date: Sat, 8 Aug 2020 12:45:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-13 08:56:48.689951
• Title: Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards
• Title（参考訳）: 確率的行動セットと逆戻りによる睡眠帯域の改善
• Authors: Aadirupa Saha, Pierre Gaillard, Michal Valko
• Abstract要約: 我々は,行動セットと敵意の報酬を伴って睡眠中の盗賊の問題を考察する。 本稿では,EXP3にインスパイアされた新しい計算効率のよいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 59.559028338399855
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider the problem of sleeping bandits with stochastic action sets and adversarial rewards. In this setting, in contrast to most work in bandits, the actions may not be available at all times. For instance, some products might be out of stock in item recommendation. The best existing efficient (i.e., polynomial-time) algorithms for this problem only guarantee an $O(T^{2/3})$ upper-bound on the regret. Yet, inefficient algorithms based on EXP4 can achieve $O(\sqrt{T})$. In this paper, we provide a new computationally efficient algorithm inspired by EXP3 satisfying a regret of order $O(\sqrt{T})$ when the availabilities of each action $i \in \cA$ are independent. We then study the most general version of the problem where at each round available sets are generated from some unknown arbitrary distribution (i.e., without the independence assumption) and propose an efficient algorithm with $O(\sqrt {2^K T})$ regret guarantee. Our theoretical results are corroborated with experimental evaluations.
• Abstract（参考訳）: 本稿では,確率的行動セットと対人報酬を併用した睡眠包帯の問題点を考察する。 この設定では、ほとんどのバンディットの作業とは対照的に、アクションはいつでも利用できない可能性がある。 例えば、一部の製品はアイテムレコメンデーションで在庫切れになるかもしれない。 この問題に対する最も効率的な(多項式時間)アルゴリズムは、後悔に対して$O(T^{2/3})$上界を保証するだけである。 しかし、EXP4に基づく非効率アルゴリズムは$O(\sqrt{T})$を達成できる。 本稿では,各アクション $i \in \ca$ が独立である場合の順序 $o(\sqrt{t})$ の後悔を満たす exp3 にインスパイアされた新しい計算効率の高いアルゴリズムを提案する。 次に、ある未知の任意の分布(すなわち独立性仮定無し)から各ラウンド利用可能な集合が生成される問題の最も一般的なバージョンを研究し、$o(\sqrt {2^k t})$ regret の効率的なアルゴリズムを提案する。 理論的結果は実験結果と相関する。

関連論文リスト

• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards [40.99322897009357]
  トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。 我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。 我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
  論文  参考訳（メタデータ） (2023-10-28T13:01:10Z)
• An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret [7.059472280274009]
  従来の非効率アルゴリズムよりも後悔度が低い新しいアルゴリズムを提案する。 N$エージェント、$K$アーム、および$T$ラウンドの場合、我々のアプローチは、$tildeO(sqrtNKT + NK)$という残念な境界を持つ。 また、効率的なアルゴリズムを $tildeO(sqrtKT + N2K)$ regret で非効率なアプローチで補完する。
  論文  参考訳（メタデータ） (2022-09-23T19:15:43Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits [27.279654173896372]
  我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。 これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
  論文  参考訳（メタデータ） (2021-11-06T16:46:55Z)
• No Regrets for Learning the Prior in Bandits [30.478188057004175]
  $tt AdaTS$は、バンディットタスクに順次適応するトンプソンサンプリングアルゴリズムである。 $tt AdaTS$は、バンドイト問題のいくつかのクラスで効率的に実装できる完全ベイズアルゴリズムである。
  論文  参考訳（メタデータ） (2021-07-13T15:51:32Z)
• Sleeping Combinatorial Bandits [15.004764451770441]
  睡眠帯域設定においてよく知られたCUCBアルゴリズムを適用し,それをCSUCBと呼ぶ。 穏やかな条件下では、CSUCBアルゴリズムが$O(sqrtT log (T)$ instance-dependent regret guaranteeを達成することを証明します。 我々の結果は極めて一般的なものであり、非付加的な報酬関数、揮発性アームの可用性、引くべきベースアームの変動数など、実用的な応用によって生じる一般的な環境下で維持されます。
  論文  参考訳（メタデータ） (2021-06-03T06:49:44Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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