論文の概要: Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy

• arxiv url: http://arxiv.org/abs/2605.07171v1
• Date: Fri, 08 May 2026 03:07:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 19:43:38.766547
• Title: Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy
• Title（参考訳）: コストサブシディを有するマルチアーマッドバンドのコスト順序付実現可能性
• Authors: Ishank Juneja, Carlee Joe-Wong, Osman Yağan,
• Abstract要約: 応用において、目標は最小限の許容報酬(MAB-CS)の制約を受けるコストを最小限にすることである。 我々は、インスタンス依存の下位境界を証明することによって、任意のポリシーで要求される期待される準最適サンプルを特徴づける。 そこで我々は,安価なアームの実用性を評価するために,すべてのアームのサンプルをインテリジェントに組み合わせたコストオーダーフィジビリティ(COF)アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 17.48220873982007
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The classic multi-armed bandit (MAB) problem tackles the challenge of accruing maximum reward while making decisions under uncertainty. However, in applications, often the goal is to minimize cost subject to a constraint on the minimum permissible reward, an objective captured by multi-armed bandits with cost-subsidy (MAB-CS). Of interest to this paper is the setting where the quality (reward) constraint is specified relative to the unknown best reward and the cost of each arm is known. We characterize the expected sub-optimal samples required by any policy by proving instance-dependent lower bounds that offer new insight into the problem and are a strict generalization of prior bounds. Then, we propose an algorithm called Cost-Ordered Feasibility (COF) that leverages our insight and intelligently combine samples from all arms to gauge the feasibility of a cheap arm. Thereafter, we analyze COF to establish instance-dependent upper bounds on its expected cumulative cost and quality regret, i.e., relative to the cheapest feasible arm. Finally, we empirically validate the merits of COF, comparing it to baselines from the literature through extensive simulation experiments on the MovieLens and Goodreads datasets as well as representative synthetic instances. Not only does our paper develop qualitatively better theoretical regret upper bounds, but COF also convincingly demonstrates improved empirical performance.
• Abstract（参考訳）: 古典的なマルチアーム・バンディット(MAB)問題は、不確実性の下で意思決定をしながら最大報酬を得るという課題に取り組む。 しかし、アプリケーションでは、しばしば、最小限の許容報酬(MAB-CS)の制約を受けるコストを最小限に抑えることが目的である。 本論文の関心は、未知のベスト報酬に対する品質(逆)制約が特定され、各アームのコストが分かる設定である。 問題に対する新たな洞察を与え、先行境界の厳密な一般化であるインスタンス依存の下位境界を証明し、任意の政策で要求される期待される準最適サンプルを特徴付ける。 そこで我々は,コストオーダーフェーシビリティ (COF) と呼ばれるアルゴリズムを提案する。このアルゴリズムは我々の洞察を活用し,すべてのアームからのサンプルをインテリジェントに組み合わせて,安価なアームの実現可能性を評価する。 その後、COFを解析して、期待される累積コストと品質の後悔、すなわち最も安価な実現可能なアームに対して、インスタンス依存の上限を確立する。 最後に,COFのメリットを実証的に検証し,MovieLensおよびGoodreadsデータセットの広範なシミュレーション実験を通じて,文献のベースラインと比較した。 本論文は, 理論的に良好な上界を定性的に発達させるだけでなく, 実証性能の向上を実証的に実証する。

関連論文リスト

• Balancing Performance and Costs in Best Arm Identification [5.558508644689221]
  本研究は、推奨アームの性能と、このアームを学習することで得られるコストとを明示的にバランスさせるリスク関数を最小化する新しいフォーマリズムを提案する。 この枠組みでは、サンプリングフェーズの各観察にコストがかかり、アームを推奨すると、最適下腕を特定するためにパフォーマンスペナルティが生じる。 性能ペナルティの2つの選択のリスク、誤識別の確率、単純な後悔のリスクについて理論的に下位境界を導出し、DBCAREと呼ばれるアルゴリズムを提案し、これらの下位境界をほぼ全ての問題インスタンス上のポリログ因子に一致させる。
  論文  参考訳（メタデータ） (2025-05-26T23:33:43Z)
• Pairwise Elimination with Instance-Dependent Guarantees for Bandits with Cost Subsidy [11.389019661082415]
  マルチアーム・バンディット(Multi-armed bandits、MAB)は、オンライン意思決定において一般的に用いられる。 Pairwise-Elimination(PE)アルゴリズムは、既知の参照アームの変種に対して導入し、補助金付きベスト報酬変種に対してPEをPE-CSに一般化する。 PE と PE-CS のインスタンス依存分析により,両アルゴリズムはコストと品質レグレクトの順に対数的な上限を持つことが明らかとなった。
  論文  参考訳（メタデータ） (2025-01-17T16:34:45Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget [6.22018632187078]
  固定予算の制約付きベスト・ミックスアーム識別(CBMAI)問題を導入する。 目標は、与えられた学習予算$N$で、期待されるコストの制約によって期待される報酬を最大化する最高の混合アームを見つけることである。 我々は、(最良の混合アームの支持の)誤識別に関する理論上の上限を提供し、予算$N$で指数関数的に崩壊することを示す。
  論文  参考訳（メタデータ） (2024-05-23T22:35:11Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [59.02170783023547]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Budgeted Multi-Armed Bandits with Asymmetric Confidence Intervals [0.9831489366502302]
  予算的マルチアーマッド・バンドイット(MAB)問題について検討し、プレイヤーが期待できない報酬とコストでK$アームから選択する。 非対称な信頼区間を用いた新しいアッパー信頼境界(UCB)サンプリングポリシーである$omega$-UCBを提案する。 これらの間隔は、サンプル平均とランダム変数の境界との間の距離でスケールし、報酬コスト比をより正確かつ厳密に推定する。
  論文  参考訳（メタデータ） (2023-06-12T12:35:16Z)

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

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