論文の概要: Multi-Armed Bandits with Self-Information Rewards

• arxiv url: http://arxiv.org/abs/2209.02211v1
• Date: Tue, 6 Sep 2022 04:26:21 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-07 15:44:16.795975
• Title: Multi-Armed Bandits with Self-Information Rewards
• Title（参考訳）: 自己情報報酬付きマルチアームバンディット
• Authors: Nir Weinberger and Michal Yemini
• Abstract要約: 本稿では、各ラウンドでプレイヤーが腕を選択し、シンボルを観察し、シンボルの自己情報という形で未観測の報酬を受け取る情報多腕バンディット(IMAB)モデルを提案する。 アルファベットサイズが知られているという仮定のもと、IMABモデルに対して2つの UCB ベースのアルゴリズムが提案されている。
• 参考スコア（独自算出の注目度）: 18.706604251200147
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces the informational multi-armed bandit (IMAB) model in which at each round, a player chooses an arm, observes a symbol, and receives an unobserved reward in the form of the symbol's self-information. Thus, the expected reward of an arm is the Shannon entropy of the probability mass function of the source that generates its symbols. The player aims to maximize the expected total reward associated with the entropy values of the arms played. Under the assumption that the alphabet size is known, two UCB-based algorithms are proposed for the IMAB model which consider the biases of the plug-in entropy estimator. The first algorithm optimistically corrects the bias term in the entropy estimation. The second algorithm relies on data-dependent confidence intervals that adapt to sources with small entropy values. Performance guarantees are provided by upper bounding the expected regret of each of the algorithms. Furthermore, in the Bernoulli case, the asymptotic behavior of these algorithms is compared to the Lai-Robbins lower bound for the pseudo regret. Additionally, under the assumption that the \textit{exact} alphabet size is unknown, and instead the player only knows a loose upper bound on it, a UCB-based algorithm is proposed, in which the player aims to reduce the regret caused by the unknown alphabet size in a finite time regime. Numerical results illustrating the expected regret of the algorithms presented in the paper are provided.
• Abstract（参考訳）: 本稿では,各ラウンドにおいて,プレイヤーがアームを選択し,シンボルを観察し,シンボルの自己情報として観察されていない報酬を受け取る情報多腕バンディット(imab)モデルを紹介する。 したがって、腕の期待される報酬は、そのシンボルを生成する源の確率質量関数のシャノンエントロピーである。 プレイヤーは、プレーする腕のエントロピー値に関連する期待される総報酬を最大化する。 アルファベットサイズが知られているという仮定の下で、プラグインエントロピー推定器のバイアスを考慮した2つのUPBベースのアルゴリズムが提案されている。 第1のアルゴリズムはエントロピー推定におけるバイアス項を楽観的に補正する。 第2のアルゴリズムは、エントロピー値の小さいソースに対応するデータ依存の信頼区間に依存する。 性能保証は、各アルゴリズムの期待された後悔を上限にすることで提供される。 さらにベルヌーイの場合、これらのアルゴリズムの漸近的挙動は偽の後悔に対してlai-robbinsの下限と比較される。 さらに, <textit{exact} のアルファベットサイズが不明であるという仮定の下では, プレイヤーはゆるやかな上界しか知らないが, UCB ベースのアルゴリズムが提案され, プレイヤーは未知のアルファベットサイズによる後悔を有限時間体制で減らそうとしている。 論文で提示されたアルゴリズムの期待された後悔を示す数値結果を提供する。

関連論文リスト

• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。 遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
  論文  参考訳（メタデータ） (2022-10-30T22:58:22Z)
• A Non-monotonic Self-terminating Language Model [62.93465126911921]
  本稿では,不完全復号アルゴリズムによる非終端列の問題に焦点をあてる。 まず、グリーディ探索、トップ$kのサンプリング、核サンプリングを含む不完全確率復号アルゴリズムを定義する。 次に,単調な終端確率の制約を緩和する非単調な自己終端言語モデルを提案する。
  論文  参考訳（メタデータ） (2022-10-03T00:28:44Z)
• Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret [34.44347218903429]
  マルチアームバンディット設定は、最近非定常状態において研究されている。 各アクションの平均的なペイオフは、前回のプレイ以来のラウンド数の増加しない機能である。 我々は,我々のアルゴリズムがサブ線形後悔を伴う帯域幅アルゴリズムにどのように変換されるかを示す。
  論文  参考訳（メタデータ） (2022-05-29T23:55:36Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Bayesian imaging using Plug & Play priors: when Langevin meets Tweedie [13.476505672245603]
  本稿では,ベイズ推定を事前に行うための理論,方法,および証明可能な収束アルゴリズムを開発する。 モンテカルロサンプリングとMMSEに対する-ULA(Unadjusted Langevin)アルゴリズム推論と、推論のための定量的SGD(Stochastic Gradient Descent)の2つのアルゴリズムを紹介します。 このアルゴリズムは、点推定や不確実性の可視化や規則性に使用される画像のノイズ除去、インペインティング、ノイズ除去などのいくつかの問題で実証されています。
  論文  参考訳（メタデータ） (2021-03-08T12:46:53Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。 我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。 有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-21T10:35:09Z)
• Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback [32.62857394584907]
  複合および匿名フィードバックによるマルチアームバンディット(MAB)問題を研究する。 本稿では,逆の場合と非逆の場合の適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-13T12:25:41Z)
• Bandit algorithms to emulate human decision making using probabilistic distortions [20.422725678982726]
  報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。 以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
  論文  参考訳（メタデータ） (2016-11-30T17:37:51Z)

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

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