論文の概要: Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation

• arxiv url: http://arxiv.org/abs/2012.15584v2
• Date: Tue, 29 Aug 2023 13:35:42 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-30 19:38:44.177285
• Title: Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation
• Title（参考訳）: 完全帯域フィードバックとそれ以上の組合せ純粋探索:有限観測による不確実性下での組合せ最適化の解法
• Authors: Yuko Kuroki, Junya Honda, Masashi Sugiyama
• Abstract要約: 最適化アルゴリズムを開発する際、エッジウェイトなどのパラメータが入力として正確に知られていることが一般的である。 本稿では、最近、限られたフィードバックを伴う純粋探索問題に対する手法について概説する。
• 参考スコア（独自算出の注目度）: 70.41056265629815
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial optimization is one of the fundamental research fields that has been extensively studied in theoretical computer science and operations research. When developing an algorithm for combinatorial optimization, it is commonly assumed that parameters such as edge weights are exactly known as inputs. However, this assumption may not be fulfilled since input parameters are often uncertain or initially unknown in many applications such as recommender systems, crowdsourcing, communication networks, and online advertisement. To resolve such uncertainty, the problem of combinatorial pure exploration of multi-armed bandits (CPE) and its variants have recieved increasing attention. Earlier work on CPE has studied the semi-bandit feedback or assumed that the outcome from each individual edge is always accessible at all rounds. However, due to practical constraints such as a budget ceiling or privacy concern, such strong feedback is not always available in recent applications. In this article, we review recently proposed techniques for combinatorial pure exploration problems with limited feedback.
• Abstract（参考訳）: 組合せ最適化は、理論計算機科学と運用研究で広く研究されている基礎研究分野の1つである。 組合せ最適化アルゴリズムを開発する際、エッジウェイトなどのパラメータは入力として正確に知られている。 しかし、この仮定は、レコメンデーションシステム、クラウドソーシング、通信ネットワーク、オンライン広告など多くのアプリケーションにおいて、入力パラメータがしばしば不確実または初期不明であるため、実現できない可能性がある。 このような不確実性を解決するために、CPE(Multi-armed bandits)とその変種の組み合わせ純粋探索の問題が注目されている。 CPEに関する以前の研究は、半帯域フィードバックを研究したり、個々のエッジからの結果は、すべてのラウンドで常にアクセス可能であると仮定していた。 しかし、予算の上限やプライバシー上の懸念といった現実的な制約のため、このような強いフィードバックは最近のアプリケーションでは必ずしも利用できない。 本稿では,限定的なフィードバックを伴う組合せ純粋探索問題の手法を最近提案した。

関連論文リスト

• Combinatorial Optimization with Policy Adaptation using Latent Space Search [44.12073954093942]
  本稿では,複雑なNPハード問題を解くために,パフォーマンスアルゴリズムを設計するための新しいアプローチを提案する。 我々の検索戦略は11の標準ベンチマークタスクにおける最先端のアプローチよりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-11-13T12:24:54Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Branch & Learn with Post-hoc Correction for Predict+Optimize with Unknown Parameters in Constraints [5.762370982168012]
  ポストホックレグレ(Post-hoc Regret)は、不満足な予測を修正するコストを考慮した損失関数である。 簡単な条件を満たす再帰アルゴリズムにより解ける任意の最適化問題に対して,ポストホックレギュレットを正確に計算する方法を示す。
  論文  参考訳（メタデータ） (2023-03-12T16:23:58Z)
• Generative Slate Recommendation with Reinforcement Learning [49.75985313698214]
  強化学習アルゴリズムは、レコメンデータシステムのユーザエンゲージメントを最適化するために使用することができる。 しかし、RLアプローチはスレートレコメンデーションシナリオでは難解である。 この設定では、アクションはアイテムの組み合わせを含むことができるスレートに対応する。 本研究では,変分オートエンコーダによって学習された連続低次元ラテント空間におけるスレートの符号化を提案する。 我々は、(i)以前の作業で要求される仮定を緩和し、(ii)完全なスレートをモデル化することで、アクション選択の品質を向上させることができる。
  論文  参考訳（メタデータ） (2023-01-20T15:28:09Z)
• Pessimistic Off-Policy Optimization for Learning to Rank [9.197878514042227]
  オフ政治学習は、ポリシーをデプロイせずに最適化するためのフレームワークである。 レコメンデーションシステムでは、ログデータの不均衡のため、これは特に難しい。 我々は、ランク付け学習のための悲観的非政治最適化について研究する。
  論文  参考訳（メタデータ） (2022-06-06T12:58:28Z)
• Incentivizing Combinatorial Bandit Exploration [87.08827496301839]
  自己関心のあるユーザに対してレコメンデーションシステムでアクションを推奨するバンディットアルゴリズムを考える。 ユーザーは他のアクションを自由に選択でき、アルゴリズムの推奨に従うためにインセンティブを得る必要がある。 ユーザは悪用を好むが、アルゴリズムは、前のユーザから収集した情報を活用することで、探索にインセンティブを与えることができる。
  論文  参考訳（メタデータ） (2022-06-01T13:46:25Z)
• Parallelizing Contextual Linear Bandits [82.65675585004448]
  並列な)コンテキスト線形バンディットアルゴリズムの族を提示し、その遺残はそれらの完全シーケンシャルなアルゴリズムとほぼ同一である。 また,これらの並列アルゴリズムについて,材料発見や生物配列設計の問題など,いくつかの領域で実証評価を行った。
  論文  参考訳（メタデータ） (2021-05-21T22:22:02Z)
• Population-Based Methods: PARTICLE SWARM OPTIMIZATION -- Development of a General-Purpose Optimizer and Applications [0.0]
  この論文は、不等式制約を受ける連続、静的、単目的の最適化問題に関係している。 粒子群最適化のパラダイムは、社会で観察された協調行動の以前のシミュレーションから着想を得たものである。
  論文  参考訳（メタデータ） (2021-01-25T09:36:25Z)
• Constraint-Handling Techniques for Particle Swarm Optimization Algorithms [0.0]
  人口ベースの手法は、従来の方法よりもはるかに複雑な問題を含む、さまざまな問題に対処することができる。 本研究の目的は,アルゴリズムに汎用的な設定を組み込んだPSOに適したCHTを開発し,比較することである。
  論文  参考訳（メタデータ） (2021-01-25T01:49:10Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  我々は、最小二乗値スタイルのアルゴリズムで一般的に使用される、より標準的なベルマン誤差の概念の下での反復が、ほぼ最適値関数の学習において強力なPAC保証を提供することを示す。 そこで本稿では,任意の(線形な)報酬関数に対して,最適に近いポリシーを学習するためにどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2020-08-18T04:34:21Z)

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

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