論文の概要: 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})$ が一致する後悔の下限を示すアルゴリズムを提案する。
本研究は,長期的影響を伴う行動に対処し,公平なアルゴリズムの設計に影響を及ぼす手法を追加することで,バンディット文学を補完する。
関連論文リスト
- 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) - Bandit Social Learning: Exploration under Myopic Behavior [58.75758600464338]
オンラインプラットフォーム上でのレビューによって動機付けられた社会学習のダイナミクスについて検討する。
エージェントはまとめて単純なマルチアームのバンディットプロトコルに従うが、各エージェントは探索を伴わずにミオプティカルに振る舞う。
このような振る舞いに対して,スターク学習の失敗を導出し,好意的な結果を提供する。
論文 参考訳(メタデータ) (2023-02-15T01:57:57Z) - Dynamical Linear Bandits [45.3190496371625]
多くの実世界のシーケンシャルな意思決定問題において、アクションはすぐにフィードバックを反映せず、その効果を長い時間枠で広げる。
これまでの研究は、遅延や集約されたフィードバックの可能性について、Multi-Armed Banditフレームワークを調査してきた。
本稿では,隠れ状態に特徴付けられる線形帯域の拡張である動的線形帯域(DLB)について紹介する。
論文 参考訳(メタデータ) (2022-11-16T15:51:44Z) - 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) - Adversarial Attacks on Linear Contextual Bandits [87.08004581867537]
悪意のあるエージェントは、望ましい行動を実行するためにバンディットアルゴリズムを攻撃するインセンティブを持つ可能性がある。
悪意のあるエージェントは、線形コンテキストのバンドイットアルゴリズムに任意のアーム$T - o(T)$倍を$T$ステップで引き出すように強制することができる。
また,悪意のあるエージェントが単一コンテキストにおける帯域幅アルゴリズムの動作に影響を与えることに関心がある場合についても検討する。
論文 参考訳(メタデータ) (2020-02-10T15:04:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。