論文の概要: The Competition Complexity of Prophet Inequalities with Correlations

• arxiv url: http://arxiv.org/abs/2409.06868v1
• Date: Tue, 10 Sep 2024 21:11:37 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-12 16:16:15.065426
• Title: The Competition Complexity of Prophet Inequalities with Correlations
• Title（参考訳）: 預言不等式の競合複雑性と相関
• Authors: Tomer Ezra, Tamar Garbuz,
• Abstract要約: 我々は,資源増強の枠組みを通じて,預言不平等問題の研究を開始する。 私たちのゴールは、オンラインで必要となる追加の報酬の数を決定し、元のインスタンスの最大値を近似することです。
• 参考スコア（独自算出の注目度）: 2.325021848829375
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We initiate the study of the prophet inequality problem through the resource augmentation framework in scenarios when the values of the rewards are correlated. Our goal is to determine the number of additional rewards an online algorithm requires to approximate the maximum value of the original instance. While the independent reward case is well understood, we extend this research to account for correlations among rewards. Our results demonstrate that, unlike in the independent case, the required number of additional rewards for approximation depends on the number of original rewards, and that block-threshold algorithms, which are optimal in the independent case, may require an infinite number of additional rewards when correlations are present. We develop asymptotically optimal algorithms for the following three scenarios: (1) where rewards arrive in blocks corresponding to the different copies of the original instance; (2) where rewards across all copies are arbitrarily shuffled; and (3) where rewards arrive in blocks corresponding to the different copies of the original instance, and values within each block are pairwise independent rather than fully correlated.
• Abstract（参考訳）: 我々は、報酬の値が相関しているシナリオにおいて、資源増強フレームワークを通じて預言不等式問題の研究を開始する。 我々のゴールは、オンラインアルゴリズムが元のインスタンスの最大値を近似するために必要となる追加報酬の数を決定することである。 独立報酬のケースはよく理解されているが、報酬間の相関を考慮するためにこの研究を拡張している。 その結果、独立の場合と異なり、近似に要する追加報酬数は元の報酬数に依存しており、独立の場合において最適であるブロック閾値アルゴリズムは、相関が存在する場合、無限の追加報酬を必要とする可能性があることを示した。 1) 元のインスタンスの異なるコピーに対応するブロックに報酬が届く場合,(2) すべてのコピーに対して報酬が任意にシャッフルされる場合,(3) 元のインスタンスの異なるコピーに対応するブロックに報酬が届く場合, そしてブロック内の値が完全に相関しない場合, という3つのシナリオに対して,漸近的に最適なアルゴリズムを開発する。

関連論文リスト

• Walking the Values in Bayesian Inverse Reinforcement Learning [66.68997022043075]
  ベイズIRLの鍵となる課題は、可能な報酬の仮説空間と可能性の間の計算的ギャップを埋めることである。 本稿では,この知見に基づく新しいマルコフ連鎖モンテカルロ法であるValueWalkを提案する。
  論文  参考訳（メタデータ） (2024-07-15T17:59:52Z)
• Not All Preference Pairs Are Created Equal: A Recipe for Annotation-Efficient Iterative Preference Learning [81.69044784288005]
  反復的な選好学習には、オンラインの注釈付き選好ラベルが必要である。 コスト効率のよいアノテーションに対する応答対を選択するための戦略について検討する。
  論文  参考訳（メタデータ） (2024-06-25T06:49:16Z)
• Reinforcement Learning from Bagged Reward [46.16904382582698]
  強化学習(RL)では、エージェントが取るアクション毎に即時報奨信号が生成されることが一般的である。 多くの実世界のシナリオでは、即時報酬信号の設計は困難である。 本稿では,双方向の注意機構を備えた新たな報酬再分配手法を提案する。
  論文  参考訳（メタデータ） (2024-02-06T07:26:44Z)
• Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
  我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。 評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
  論文  参考訳（メタデータ） (2021-12-13T09:48:54Z)
• Risk-Aware Algorithms for Combinatorial Semi-Bandits [7.716156977428555]
  半帯域フィードバック下でのマルチアームバンディット問題について検討する。 本稿では,最悪の場合の報酬のみを考慮したリスク尺度であるCVaR(Conditional Value-at-Risk)の最大化の問題を検討する。 本稿では,バンディットのスーパーアームから得られる報酬のCVaRを最大化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-02T11:29:43Z)
• On the Expressivity of Markov Reward [89.96685777114456]
  本稿では,エージェントが実行するタスクをキャプチャする手段として,報酬の表現性を理解することを目的としている。 本研究は,(1)許容される行動の集合,(2)行動上の部分順序,(3)軌道上の部分順序の3つの新しい抽象概念「タスク」について考察する。
  論文  参考訳（メタデータ） (2021-11-01T12:12:16Z)
• Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback [32.62857394584907]
  複合および匿名フィードバックによるマルチアームバンディット(MAB)問題を研究する。 本稿では,逆の場合と非逆の場合の適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-13T12:25:41Z)
• On Reward-Free Reinforcement Learning with Linear Function Approximation [144.4210285338698]
  Reward-free reinforcement learning (RL) は、バッチRL設定と多くの報酬関数がある設定の両方に適したフレームワークである。 本研究では,線形関数近似を用いた報酬のないRLに対して,正と負の両方の結果を与える。
  論文  参考訳（メタデータ） (2020-06-19T17:59:36Z)
• The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity [83.81297078039836]
  インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。 我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
  論文  参考訳（メタデータ） (2020-02-03T04:58:51Z)
• Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards [10.66048003460524]
  本稿では,複数の演奏とマルコフ報酬を含む古典的マルチアームバンディット問題の拡張について検討する。 この問題に対処するために、各段階において、全てのアームのサンプル手段からの情報と、ラウンドロビン方式で選択された単一アームのクルバック・リーバー上信頼境界とを結合する適応的アロケーションルールを検討する。
  論文  参考訳（メタデータ） (2020-01-30T08:09:01Z)

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

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