論文の概要: Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits
- arxiv url: http://arxiv.org/abs/2301.13393v1
- Date: Tue, 31 Jan 2023 03:49:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-01 17:42:56.666533
- Title: Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits
- Title（参考訳）: おそらくいつでも安全な確率的組合せ半バンド
- Authors: Yunlong Hou, Vincent Y. F. Tan and Zixin Zhong
- Abstract要約: 本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案した sc PASCombUCB アルゴリズムはレコメンデーションシステムやトランスポートなどの領域に適用可能である。
- 参考スコア（独自算出の注目度）: 81.60136088841948
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Motivated by concerns about making online decisions that incur undue amount
of risk at each time step, in this paper, we formulate the probably
anytime-safe stochastic combinatorial semi-bandits problem. In this problem,
the agent is given the option to select a subset of size at most $K$ from a set
of $L$ ground items. Each item is associated to a certain mean reward as well
as a variance that represents its risk. To mitigate the risk that the agent
incurs, we require that with probability at least $1-\delta$, over the entire
horizon of time $T$, each of the choices that the agent makes should contain
items whose sum of variances does not exceed a certain variance budget. We call
this probably anytime-safe constraint. Under this constraint, we design and
analyze an algorithm {\sc PASCombUCB} that minimizes the regret over the
horizon of time $T$. By developing accompanying information-theoretic lower
bounds, we show under both the problem-dependent and problem-independent
paradigms, {\sc PASCombUCB} is almost asymptotically optimal. Our problem
setup, the proposed {\sc PASCombUCB} algorithm, and novel analyses are
applicable to domains such as recommendation systems and transportation in
which an agent is allowed to choose multiple items at a single time step and
wishes to control the risk over the whole time horizon.
- Abstract（参考訳）: 本論文では,各段階におけるリスクの未発生に関するオンライン意思決定に関する懸念に乗じて,最も安全と思われる確率的半帯域問題を定式化する。
この問題では、エージェントは、$L$グラウンドアイテムのセットから、最大で$K$のサイズのサブセットを選択するオプションが与えられる。
各項目は、そのリスクを表すばらつきと同様に、ある平均報酬に関連付けられている。
エージェントが発生するリスクを軽減するために、少なくとも1〜\delta$という確率で、t$の全時間にわたって、エージェントが選択する各選択肢には、分散の合計が特定の分散予算を超えない項目を含むべきである。
これを、おそらくいつでも安全な制約と呼ぶ。
この制約の下で、時間の地平線上での後悔を最小限に抑えるアルゴリズム {\sc PASCombUCB} を設計し、分析する。
付随する情報理論の下界を発達させることにより、問題依存パラダイムと問題非依存パラダイムの両方の下で、ほぼ漸近的に最適であることを示す。
提案する問題設定, 提案アルゴリズム, 新規解析は, エージェントが一度に複数の項目を選択できるレコメンデーションシステムやトランスポーテーションなどのドメインに適用され, リスク全体を制御したいと考えている。
関連論文リスト
- Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
N$エージェントのネットワークがローカルに通信し、期待されるコストを所定の閾値$tau$で保持しながら、全体的な後悔を最小限に抑える。
我々は、textitMA-OPLBと呼ばれる安全な分散上信頼度有界アルゴリズムを提案し、そのT$ラウンドの後悔に基づく高い確率を確立する。
我々の後悔の限界は次数$ MathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)であることを示す。
論文 参考訳（メタデータ） (2024-10-22T19:34:53Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Risk-averse Contextual Multi-armed Bandit Problem with Linear Payoffs [7.125769932993104]
リスク・逆条件下での線形ペイオフに対するコンテキスト多重武装バンディット問題について考察する。
各ラウンドにおいて、各アームのコンテキストが明らかにされ、意思決定者は1つのアームを選択して、対応する報酬を受け取ります。
解離モデルに対してトンプソンサンプリングアルゴリズムを適用し,提案アルゴリズムの変種に対する包括的後悔解析を行う。
論文 参考訳（メタデータ） (2022-06-24T18:48:35Z) - Bandits with Stochastic Experts: Constant Regret, Empirical Experts and Episodes [36.104981594178525]
エージェントが一連の専門家ポリシーを介し介入できる文脈的帯域幅問題の変種について検討する。
本稿では,D-UCB(Divergence-based Upper Confidence Bound)アルゴリズムを提案する。
また,経験的D-UCB (ED-UCB) アルゴリズムも提案する。
論文 参考訳（メタデータ） (2021-07-07T14:58:14Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - A Multi-Arm Bandit Approach To Subset Selection Under Constraints [14.543433698096667]
中央プランナーがエージェントのサブセットを選択する必要がある問題の種類を,それぞれ異なる品質とコストで検討する。
エージェントの品質が分かると、我々は問題を整数線形プログラム(ILP)として定式化する。
ILPの正確な解を提供する決定論的アルゴリズム(dpss)を提案する。
論文 参考訳（メタデータ） (2021-02-09T13:48:57Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。