論文の概要: Online Learning for Min Sum Set Cover and Pandora's Box

• arxiv url: http://arxiv.org/abs/2202.04870v1
• Date: Thu, 10 Feb 2022 07:12:44 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-11 15:52:02.861811
• Title: Online Learning for Min Sum Set Cover and Pandora's Box
• Title（参考訳）: Min Sum Set Cover と Pandora の Box のオンライン学習
• Authors: Evangelia Gergatsouli, Christos Tzamos
• Abstract要約: 最適な探索順序のコストに対して一定の競合性を持つ計算効率の良いアルゴリズムを提案する。 本結果は,Pandora の Box および Min Sum Set Cover の他のよく研究されている変種に一般化する。
• 参考スコア（独自算出の注目度）: 18.30302893560438
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Two central problems in Stochastic Optimization are Min Sum Set Cover and Pandora's Box. In Pandora's Box, we are presented with n boxes, each containing an unknown value and the goal is to open the boxes in some order to minimize the sum of the search cost and the smallest value found. Given a distribution of value vectors, we are asked to identify a near-optimal search order. Min Sum Set Cover corresponds to the case where values are either 0 or infinity. In this work, we study the case where the value vectors are not drawn from a distribution but are presented to a learner in an online fashion. We present a computationally efficient algorithm that is constant-competitive against the cost of the optimal search order. We extend our results to a bandit setting where only the values of the boxes opened are revealed to the learner after every round. We also generalize our results to other commonly studied variants of Pandora's Box and Min Sum Set Cover that involve selecting more than a single value subject to a matroid constraint.
• Abstract（参考訳）: 確率最適化の主な問題は、Min Sum Set CoverとPandoraのBoxである。 pandoraのボックスにはn個のボックスがあり、それぞれに未知の値が含まれており、検索コストと最小の値の合計を最小化するために箱を開けることを目標としている。 値ベクトルの分布が与えられた場合、ほぼ最適探索順序を特定するよう依頼する。 Min Sum Set Cover は、値が 0 または infinity である場合に対応する。 本研究では,分布から値ベクトルが引き出されるのではなく,学習者にオンライン的に提示される場合について検討する。 最適探索順序のコストに対して一定の競合性を持つ計算効率のよいアルゴリズムを提案する。 各ラウンドの後に開き箱の値のみを学習者に公開するバンディット設定に結果を拡張します。 また、この結果は、マトロイド制約を受ける1つ以上の値を選択することを含むPandoraのBoxとMin Sum Set Coverの他のよく研究されている変種にも一般化する。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Best Arm Identification in Bandits with Limited Precision Sampling [14.011731120150124]
  学習者が腕選択の精度に限界がある多腕バンディット問題の変種における最適な腕識別について検討する。 非特異な最適アロケーションを処理するために,修正されたトラッキングベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-10T12:07:48Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Bandit Algorithms for Prophet Inequality and Pandora's Box [13.709418181148148]
  マルチアーメッド・バンディットモデルにおける預言不等式とPandoraのボックス問題について検討した。 我々の結果は、予言の不平等とPandoraのBoxの両面で、ほぼ最適の$tildeO(mathsfpoly(n)sqrtT)$トータル後悔アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-11-16T00:10:35Z)
• Contextual Pandora's Box [36.625727016146485]
  PandoraのBoxは基本的な最適化の問題です。 我々はコンテキストを取り入れつつ、PandoraのBoxをオンライン環境で研究する。 我々の主な成果は、最適なアルゴリズムに相容れない性能の非回帰アルゴリズムである。
  論文  参考訳（メタデータ） (2022-05-26T02:43:29Z)
• Optimal Algorithms for Range Searching over Multi-Armed Bandits [17.800612821499612]
  本稿では,マルチアームバンディット(MAB)のレンジ探索問題について検討する。 サンプル効率のよいアルゴリズムを開発し、高い確率で、与えられた間隔内で準最適腕を求める。 私たちの結果は、MAB設定における幾何学的構成、特に打撃集合の重要性を強調します。
  論文  参考訳（メタデータ） (2021-05-04T09:52:16Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。 我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
  論文  参考訳（メタデータ） (2021-03-03T23:08:59Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Dive Deeper Into Box for Object Detection [49.923586776690115]
  そこで我々は,より正確な位置決めを行うために,ボックスに深く潜り込むことができるボックス再構成手法(DDBNet)を提案する。 実験結果から,本手法はオブジェクト検出の最先端性能に寄与する可能性が示唆された。
  論文  参考訳（メタデータ） (2020-07-15T07:49:05Z)
• Rate-adaptive model selection over a collection of black-box contextual bandit algorithms [0.966840768820136]
  文脈的帯域設定におけるモデル選択タスクについて検討する。 我々の提案は、一般的なブラックボックス・コンテクスト・バンディットアルゴリズムの収集に適応する最初のものである。
  論文  参考訳（メタデータ） (2020-06-05T18:55:16Z)
• SetRank: A Setwise Bayesian Approach for Collaborative Ranking from Implicit Feedback [50.13745601531148]
  提案手法は,提案システムにおける暗黙的フィードバックの特性に対応するために,協調的ランキング(SeetRank)のためのセッティングワイドベイズ的手法を提案する。 具体的には、SetRankは、新しい設定された選好比較の後方確率を最大化することを目的としている。 また、SetRankの理論解析により、余剰リスクの境界が$sqrtM/N$に比例できることを示す。
  論文  参考訳（メタデータ） (2020-02-23T06:40:48Z)

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

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