論文の概要: Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality

• arxiv url: http://arxiv.org/abs/2505.18828v1
• Date: Sat, 24 May 2025 18:55:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 16:58:42.684168
• Title: Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality
• Title（参考訳）: Pandoraのボックスと預言不平等のためのレグレトと文脈線形拡張の改善
• Authors: Junyan Liu, Ziyun Chen, Kun Wang, Haipeng Luo, Lillian J. Ratliff,
• Abstract要約: PandoraのBox問題を半帯域フィードバックによるオンライン学習環境で研究する。 各ラウンドでは、学習者は、未知の報酬分布を持つ最大$n$ボックスを開くために順次支払いを行う。 我々は,$T$ラウンド後に$widetildeO(sqrtT)$ regretを達成する新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 42.13757010124367
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the Pandora's Box problem in an online learning setting with semi-bandit feedback. In each round, the learner sequentially pays to open up to $n$ boxes with unknown reward distributions, observes rewards upon opening, and decides when to stop. The utility of the learner is the maximum observed reward minus the cumulative cost of opened boxes, and the goal is to minimize regret defined as the gap between the cumulative expected utility and that of the optimal policy. We propose a new algorithm that achieves $\widetilde{O}(\sqrt{nT})$ regret after $T$ rounds, which improves the $\widetilde{O}(n\sqrt{T})$ bound of Agarwal et al. [2024] and matches the known lower bound up to logarithmic factors. To better capture real-life applications, we then extend our results to a natural but challenging contextual linear setting, where each box's expected reward is linear in some known but time-varying $d$-dimensional context and the noise distribution is fixed over time. We design an algorithm that learns both the linear function and the noise distributions, achieving $\widetilde{O}(nd\sqrt{T})$ regret. Finally, we show that our techniques also apply to the online Prophet Inequality problem, where the learner must decide immediately whether or not to accept a revealed reward. In both non-contextual and contextual settings, our approach achieves similar improvements and regret bounds.
• Abstract（参考訳）: PandoraのBox問題を半帯域フィードバックによるオンライン学習環境で研究する。 各ラウンドで、学習者は、未知の報酬分布を持つ最大$n$ボックスを開くために順次支払い、オープニング時に報酬を観察し、いつ停止するかを決める。 学習者の効用は、オープンボックスの累積コストを抑える最大観測報酬であり、累積効用量と最適政策とのギャップとして定義される後悔を最小限に抑えることが目的である。 我々は、$\widetilde{O}(\sqrt{nT})$ regretを$T$ラウンド後に達成し、$\widetilde{O}(n\sqrt{T})$ bound of Agarwal et al [2024] を改良し、既知の下界を対数係数に一致させる新しいアルゴリズムを提案する。 実世界のアプリケーションをよりよく捉えるために、我々は結果を自然だが挑戦的な文脈の線形設定に拡張し、各ボックスの期待される報酬は既知のが時間によって変化する$d$-dimensionalコンテキストにおいて線形であり、ノイズ分布は時間とともに固定される。 我々は線形関数と雑音分布の両方を学習し、$\widetilde{O}(nd\sqrt{T})$ regretを達成するアルゴリズムを設計する。 最後に,本手法がオンライン預言不平等問題にも適用可能であることを示す。 非コンテキスト設定とコンテキスト設定の両方において、我々のアプローチは同様の改善と後悔の限界を達成する。

関連論文リスト

• In-Trajectory Inverse Reinforcement Learning: Learn Incrementally Before An Ongoing Trajectory Terminates [10.438810967483438]
  逆強化学習(IRL)は報酬関数とそれに対応するポリシーを学習することを目的としている。 現在のIRLの作業は、学習するために少なくとも1つの完全な軌跡を集めるのを待つ必要があるため、進行中の軌跡から漸進的に学習することはできない。 本稿では,現在進行中の軌跡の初期状態対を観察しながら,報酬関数と対応する政策を学習する問題について考察する。
  論文  参考訳（メタデータ） (2024-10-21T03:16:32Z)
• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  我々は,個別かつ不可逆な意思決定を対象とするオンライン学習と最適化の問題を定義した。 各期間において、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために分類モデルを更新する。 目的は,多数の施設を対象とする地平線を特徴とし,カバー対象を反映するチャンス制約の下で施設開口を最小化することである。
  論文  参考訳（メタデータ） (2024-06-20T23:00:25Z)
• 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)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Bandit Algorithms for Prophet Inequality and Pandora's Box [13.709418181148148]
  マルチアーメッド・バンディットモデルにおける預言不等式とPandoraのボックス問題について検討した。 我々の結果は、予言の不平等とPandoraのBoxの両面で、ほぼ最適の$tildeO(mathsfpoly(n)sqrtT)$トータル後悔アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-11-16T00:10:35Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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