論文の概要: Partial Information as Full: Reward Imputation with Sketching in Bandits

• arxiv url: http://arxiv.org/abs/2210.06719v1
• Date: Thu, 13 Oct 2022 04:26:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-14 14:40:54.600194
• Title: Partial Information as Full: Reward Imputation with Sketching in Bandits
• Title（参考訳）: 完全部分情報:バンドのスケッチによる逆流計算
• Authors: Xiao Zhang, Ninglu Shao, Zihua Si, Jun Xu, Wenha Wang, Hanjing Su, Ji-Rong Wen
• Abstract要約: コンテキストバッチバンディット(CBB)のためのスケッチを用いた効率的な報酬計算手法を提案する。 我々は、報酬計算を正規化リッジ回帰問題として定式化する。 報奨計算法は,報奨計算法を使わずに,制御可能なバイアスと,報奨計算法よりもばらつきが小さい即時後悔を達成できることを示す。
• 参考スコア（独自算出の注目度）: 43.46285006492124
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We focus on the setting of contextual batched bandit (CBB), where a batch of rewards is observed from the environment in each episode. But the rewards of the non-executed actions are unobserved (i.e., partial-information feedbacks). Existing approaches for CBB usually ignore the rewards of the non-executed actions, resulting in feedback information being underutilized. In this paper, we propose an efficient reward imputation approach using sketching for CBB, which completes the unobserved rewards with the imputed rewards approximating the full-information feedbacks. Specifically, we formulate the reward imputation as a problem of imputation regularized ridge regression, which captures the feedback mechanisms of both the non-executed and executed actions. To reduce the time complexity of reward imputation, we solve the regression problem using randomized sketching. We prove that our reward imputation approach obtains a relative-error bound for sketching approximation, achieves an instantaneous regret with a controllable bias and a smaller variance than that without reward imputation, and enjoys a sublinear regret bound against the optimal policy. Moreover, we present two extensions of our approach, including the rate-scheduled version and the version for nonlinear rewards, making our approach more feasible. Experimental results demonstrated that our approach can outperform the state-of-the-art baselines on synthetic and real-world datasets.
• Abstract（参考訳）: 本稿では,各エピソードの環境から報奨のバッチが観測されるCBBの設定に注目した。 しかし、実行されていないアクションの報酬は観察されない(つまり、部分的な情報フィードバック)。 CBBの既存のアプローチは、通常、実行されていないアクションの報酬を無視し、フィードバック情報が未利用になる。 本稿では,全情報フィードバックを近似するインプリメントを付与した非オブザーブ報酬を完結させるcbbのためのスケッチを用いた,効率的な報酬インプテーション手法を提案する。 具体的には,非実行動作と実行動作の両方のフィードバック機構を捉えたインプテーション正規化リッジ回帰問題として報酬インプテーションを定式化する。 報酬インプテーションの時間的複雑さを軽減するため,ランダムなスケッチを用いて回帰問題を解く。 報奨インプテーションアプローチは,スケッチ近似の相対的エラーバウンドを求め,報奨インプテーションなしで制御可能なバイアスとばらつきの小さい瞬時後悔を達成し,最適なポリシーに拘束されたサブリニアな後悔を享受する。 さらに,レートスケジューリング版と非線形報酬版という2つのアプローチ拡張を提案し,そのアプローチをより実現可能とした。 実験の結果,本手法は人工および実世界のデータセットにおける最先端のベースラインを上回ることができることがわかった。

関連論文リスト

• Contextual Linear Optimization with Bandit Feedback [35.692428244561626]
  文脈線形最適化(CLO)は、ランダムコスト係数の不確実性を低減するために予測的文脈特徴を用いる。 我々は,帯域幅フィードバックを用いたCLOのためのオフライン学習アルゴリズムのクラスについて検討する。 IERMに対する高速な後悔境界を示し、不特定モデルクラスと最適化推定の柔軟な選択を可能にする。
  論文  参考訳（メタデータ） (2024-05-26T13:27:27Z)
• Contextual bandits with concave rewards, and an application to fair ranking [108.48223948875685]
  CBCR (Contextual Bandits with Concave Rewards) に対する反省点のある最初のアルゴリズムを提案する。 我々は,スカラー・リワード問題に対するCBCRの後悔から,新たな縮小を導出した。 推薦の公正さによって動機づけられたCBCRの特別事例として,ランク付けと公正を意識した目的について述べる。
  論文  参考訳（メタデータ） (2022-10-18T16:11:55Z)
• Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When Partial Feedback Counts [53.579515853222986]
  時間分割リワード(TP-MAB)を用いたマルチアーメッド・バンディット(Multi-Armed Bandit)について検討する。 この設定は、プル後の有限時間スパン上で報酬が拡張されるケースに対する遅延フィードバックバンディットの自然な拡張である。 本稿では,TP-UCB-FRとTP-UCB-EWの2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-01T15:56:59Z)
• Break your Bandit Routine with LSD Rewards: a Last Switch Dependent Analysis of Satiation and Seasonality [6.146046338698175]
  そこで本研究では,腕が最後に動作を切り替えて以降の時間経過によって,腕の期待される報酬が完全に決定される,新たな非定常バンディット問題を導入する。 我々のモデルは、遅延依存報酬の概念を一般化し、報酬関数に関するほとんどの仮定を緩和する。 我々はアルゴリズムを証明し、最適な非定常ポリシーに関してその後悔を証明した。
  論文  参考訳（メタデータ） (2021-10-22T14:53:13Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。 楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。 我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
  論文  参考訳（メタデータ） (2021-10-21T15:25:15Z)
• Scalable Bayesian Inverse Reinforcement Learning [93.27920030279586]
  我々はAVRIL(Adroximate Variational Reward Imitation Learning)を紹介する。 本手法は,逆強化学習問題の誤った性質に対処する。 本手法を従来の制御シミュレーションと並行して実際の医療データに適用し,現在の手法の範囲を超えた環境におけるベイズ報酬推論を実証する。
  論文  参考訳（メタデータ） (2021-02-12T12:32:02Z)
• Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback [32.62857394584907]
  複合および匿名フィードバックによるマルチアームバンディット(MAB)問題を研究する。 本稿では,逆の場合と非逆の場合の適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-13T12:25:41Z)
• Reinforcement Learning with Trajectory Feedback [76.94405309609552]
  本研究では、この仮定を緩和する第一歩を踏み出し、より弱い形のフィードバックを必要とする。 あらゆる行動の後に得られる報酬を観察する代わりに、エージェントが観察する全軌道の質、すなわち、この軌道上で得られるすべての報酬の総和を表すスコアのみを受け取ると仮定する。 我々は、未知の遷移モデルと未知の遷移モデルの両方に対して、未知の報酬の最小二乗推定に基づいて強化学習アルゴリズムをこの設定に拡張し、それらの後悔を分析してこれらのアルゴリズムの性能について検討する。
  論文  参考訳（メタデータ） (2020-08-13T17:49:18Z)
• Counterfactual Evaluation of Slate Recommendations with Sequential Reward Interactions [18.90946044396516]
  音楽ストリーミング、ビデオストリーミング、ニュースレコメンデーション、eコマースサービスは、しばしばシーケンシャルな方法でコンテンツを扱う。 したがって、適切なレコメンデーションのシーケンスの提供と評価は、これらのサービスにとって重要な問題である。 そこで本研究では,アナルアンバイアスの少ない報酬の逐次的相互作用が可能な新しい反事実推定器を提案する。
  論文  参考訳（メタデータ） (2020-07-25T17:58:01Z)

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

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