論文の概要: Bandit Learning with Delayed Impact of Actions
- arxiv url: http://arxiv.org/abs/2002.10316v4
- Date: Sun, 31 Oct 2021 17:56:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-29 03:11:50.095091
- Title: Bandit Learning with Delayed Impact of Actions
- Title（参考訳）: 動作の遅延によるバンディット学習
- Authors: Wei Tang, Chien-Ju Ho, Yang Liu
- Abstract要約: 動作の遅延によるマルチアーム・バンディット(MAB)問題を考える。
私たちの設定では、過去の行動は、今後の腕の報酬に影響を与えます。
この行動の遅延した影響は、現実世界で広く見られる。
- 参考スコア（独自算出の注目度）: 25.508329225188586
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a stochastic multi-armed bandit (MAB) problem with delayed impact
of actions. In our setting, actions taken in the past impact the arm rewards in
the subsequent future. This delayed impact of actions is prevalent in the real
world. For example, the capability to pay back a loan for people in a certain
social group might depend on historically how frequently that group has been
approved loan applications. If banks keep rejecting loan applications to people
in a disadvantaged group, it could create a feedback loop and further damage
the chance of getting loans for people in that group. In this paper, we
formulate this delayed and long-term impact of actions within the context of
multi-armed bandits. We generalize the bandit setting to encode the dependency
of this "bias" due to the action history during learning. The goal is to
maximize the collected utilities over time while taking into account the
dynamics created by the delayed impacts of historical actions. We propose an
algorithm that achieves a regret of $\tilde{\mathcal{O}}(KT^{2/3})$ and show a
matching regret lower bound of $\Omega(KT^{2/3})$, where $K$ is the number of
arms and $T$ is the learning horizon. Our results complement the bandit
literature by adding techniques to deal with actions with long-term impacts and
have implications in designing fair algorithms.
- Abstract（参考訳）: 我々は,行動の遅れを伴う確率的多腕バンディット(mab)問題を考える。
私たちの設定では、過去の行動は、今後の腕の報酬に影響を与えます。
この遅延した行動の影響は現実世界で広く見られる。
例えば、ある社会集団の人々にローンを返済する能力は、そのグループがどれだけの頻度でローン申請を承認されたかによって異なります。
もし銀行が不利なグループの人々にローン申請を拒絶し続ければ、フィードバックループを作り、そのグループの人々へのローン申請の機会をさらに損なう可能性がある。
本稿では,多腕バンディットの文脈における動作の遅延と長期的影響を定式化する。
我々は、学習中の行動履歴によるこの「バイアス」の依存性を符号化するバンディット設定を一般化する。
目的は、歴史的行動の遅れた影響によって生じるダイナミクスを考慮して、収集されたユーティリティを時間とともに最大化することである。
我々は、$\tilde{\mathcal{o}}(kt^{2/3})$ の後悔を達成し、$k$ が腕の数、$t$ が学習地平線である$\omega(kt^{2/3})$ が一致する後悔の下限を示すアルゴリズムを提案する。
本研究は,長期的影響を伴う行動に対処し,公平なアルゴリズムの設計に影響を及ぼす手法を追加することで,バンディット文学を補完する。
関連論文リスト
- Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。
本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
論文 参考訳（メタデータ） (2024-09-09T18:23:07Z) - Learning for Bandits under Action Erasures [20.235500642661812]
我々は,学習者が消去チャネル上で分散エージェントにアクションを伝える必要がある,新しいマルチアーム・バンディット(MAB)について考察する。
我々のモデルでは、分散エージェントはアクションが消去されるかどうかを知っているが、中心的な学習者は知らない。
本稿では,既存のMABアルゴリズム上で動作可能な手法を提案する。
論文 参考訳（メタデータ） (2024-06-26T05:03:00Z) - Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback [11.262167746929332]
Restless Multi-armed bandits (RMAB)は、シーケンシャルな意思決定問題のモデル化において中心的な役割を果たす。
本稿では,未知の遷移関数と対向報酬を持つ表在的RMABにおける学習課題について考察する。
我々は2つの重要な貢献者による新しい強化学習アルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-05-02T02:20:19Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳（メタデータ） (2024-04-16T17:59:55Z) - Adversarial Bandits with Multi-User Delayed Feedback: Theory and
Application [17.64363983613468]
我々は,マルチユーザ遅延フィードバックを用いた逆MAB問題を定式化し,修正されたEXP3アルゴリズム MUD-EXP3 を設計する。
本稿では,複数のユーザからの遅延フィードバック結果について考察し,内部分布に制限を加えることなく検討する。
論文 参考訳（メタデータ） (2023-10-17T12:08:15Z) - Weighted Tallying Bandits: Overcoming Intractability via Repeated
Exposure Optimality [46.445321251991096]
推薦システムやクラウドソーシングアプリケーションでは、人間の好みや能力はアルゴリズムの最近の行動の関数であることが多い。
我々は、この設定を一般化するWeighted Tallying Bandit (WTB)を導入し、アクションの損失が、前回の$m$のタイムステップで腕が演奏された回数のエンフ和関数であることを要求して、この設定を一般化する。
我々は、$K$アクションと水平線$T$の問題に対して、逐次除去アルゴリズムの簡単な変更は、$O left( sqrtKT + m+)を持つことを示した。
論文 参考訳（メタデータ） (2023-05-04T15:59:43Z) - Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When
Partial Feedback Counts [53.579515853222986]
時間分割リワード(TP-MAB)を用いたマルチアーメッド・バンディット(Multi-Armed Bandit)について検討する。
この設定は、プル後の有限時間スパン上で報酬が拡張されるケースに対する遅延フィードバックバンディットの自然な拡張である。
本稿では,TP-UCB-FRとTP-UCB-EWの2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T15:56:59Z) - Addressing the Long-term Impact of ML Decisions via Policy Regret [49.92903850297013]
意思決定者が腕を引っ張るたびに、各腕からの報酬が進化する状況について検討する。
我々は、許容可能な機会の逐次配分は、成長の可能性を考慮に入れなければならないと論じている。
十分に長い時間的地平線に対して、確実にサブ線形ポリシーを後悔するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-02T17:38:10Z) - 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) - Learning by Repetition: Stochastic Multi-armed Bandits under Priming
Effect [2.5966580648312223]
マルチアーム・バンディット・セッティングにおけるエンゲージメントの持続性が学習に及ぼす影響について検討した。
時間におけるサブ線形後悔と関連する摩耗/摩耗パラメータを実現する新しいアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-06-18T08:27:23Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。