論文の概要: Online Recommendations for Agents with Discounted Adaptive Preferences
- arxiv url: http://arxiv.org/abs/2302.06014v2
- Date: Tue, 6 Feb 2024 16:08:10 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-07 21:15:29.757826
- Title: Online Recommendations for Agents with Discounted Adaptive Preferences
- Title（参考訳）: 分散型適応選好エージェントに対するオンライン勧告
- Authors: Arpit Agarwal, William Brown
- Abstract要約: エージェントの選好が過去の選択の関数として進化するバンディットレコメンデーション問題。
本稿では,$textitentire$ item simplexに対して,効率的なサブ線形後悔を求めるアルゴリズムを示す。
- 参考スコア（独自算出の注目度）: 17.501559059079806
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a bandit recommendations problem in which an agent's preferences
(representing selection probabilities over recommended items) evolve as a
function of past selections, according to an unknown $\textit{preference
model}$. In each round, we show a menu of $k$ items (out of $n$ total) to the
agent, who then chooses a single item, and we aim to minimize regret with
respect to some $\textit{target set}$ (a subset of the item simplex) for
adversarial losses over the agent's choices. Extending the setting from Agarwal
and Brown (2022), where uniform-memory agents were considered, here we allow
for non-uniform memory in which a discount factor is applied to the agent's
memory vector at each subsequent round. In the "long-term memory" regime (when
the effective memory horizon scales with $T$ sublinearly), we show that
efficient sublinear regret is obtainable with respect to the set of
$\textit{everywhere instantaneously realizable distributions}$ (the "EIRD set",
as formulated in prior work) for any $\textit{smooth}$ preference model.
Further, for preferences which are bounded above and below by linear functions
of memory weight (we call these "scale-bounded" preferences) we give an
algorithm which obtains efficient sublinear regret with respect to nearly the
$\textit{entire}$ item simplex. We show an NP-hardness result for expanding to
targets beyond EIRD in general. In the "short-term memory" regime (when the
memory horizon is constant), we show that scale-bounded preferences again
enable efficient sublinear regret for nearly the entire simplex even without
smoothness if losses do not change too frequently, yet we show an
information-theoretic barrier for competing against the EIRD set under
arbitrary smooth preference models even when losses are constant.
- Abstract（参考訳）: 未知の$\textit{preference model}$ によれば、エージェントの好み(推奨項目よりも選択確率を示す)が過去の選択関数として進化する、バンディットの推奨問題を考える。
各ラウンドで、エージェントに$k$アイテム(合計$n$)のメニューを表示し、1つのアイテムを選択する。そして、エージェントの選択に対する敵の損失に対して、$\textit{target set}$(アイテムのサブセット)に対する後悔を最小限に抑える。
均一メモリエージェントが考慮されたagarwalとbrown(2022年)から設定を拡張することにより、次のラウンド毎にエージェントのメモリベクトルにディスカウント係数が適用される一様でないメモリを許容する。
長期記憶(long-term memory)」では、任意の$\textit{smooth}$のモデルに対して、効率的なサブリニア後悔が$\textit{everywhere instantaneally realizable distributions}$(以前の作業で定式化された"eird set")のセットに対して得られることが示される。
さらに、メモリ重みの線型関数によって上下に有界な選好(これらの「スケールバウンド」選好と呼ぶ)に対して、$\textit{entire}$ item simplex のほとんどについて効率的なサブ線形後悔を求めるアルゴリズムを与える。
EIRD以上のターゲットに拡張するためのNP-hardnessの結果を示す。
短期記憶」体制(メモリ水平線が一定である場合)において、スケールバウンドされた嗜好は、損失があまり頻繁に変化しない場合でも、スムーズさを伴わずに、ほぼすべての単純体に対して効率的なサブ線形後悔を可能にすることを示すが、損失が一定であっても任意のスムーズな選好モデルの下でEIRDと競合する情報理論上の障壁を示す。
関連論文リスト
- Order-Optimal Instance-Dependent Bounds for Offline Reinforcement Learning with Preference Feedback [56.6950165117658]
我々は、暗黙の報酬が未知パラメータの線形関数である、好みフィードバックによるオフライン強化学習について検討する。
そこで我々は,UnderlineLocally Underline Underline Weights あるいは sc RL-LOW を用いたアルゴリズムを提案する。
我々は,sc RL-LOWの次数次最適性を示すため,単純な後悔マッチングの指数において,下限と上限が順序的に一致することが観察された。
論文 参考訳（メタデータ） (2024-06-18T02:03:12Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。
疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。
後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
論文 参考訳（メタデータ） (2023-05-30T16:05:44Z) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳（メタデータ） (2023-03-15T17:59:27Z) - Sketchy: Memory-efficient Adaptive Regularization with Frequent
Directions [22.09320263962004]
ディープラーニング(DL)学習タスクにおけるKronecker-factored gradient covariance matrixのスペクトルは、小さなリード固有空間に集中している。
本稿では,行列プレコンディショナを維持するためのメモリと計算要求を低減させる汎用的手法について述べる。
ShampooやAdamと競合する手法で、第2の瞬間を追跡するにはサブ線形メモリしか必要ありません。
論文 参考訳（メタデータ） (2023-02-07T21:50:06Z) - Parameter and Feature Selection in Stochastic Linear Bandits [38.909757749493934]
線形帯域(LB)における2つのモデル選択設定について検討する。
最初の設定では、LB問題の報酬パラメータは、$mathbb Rd$の重なり合うボールとして表される$M$モデルから任意に選択される。
2つ目の設定では、LB問題の期待される報酬は、少なくとも$M$特徴写像(モデル)の1つの線形スパンにある。
論文 参考訳（メタデータ） (2021-06-09T20:37:29Z) - High-Dimensional Sparse Linear Bandits [67.9378546011416]
データ・ポーア・システマティクスにおける疎線形包帯に対して、新しい$Omega(n2/3)$ dimension-free minimax regret lower boundを導出する。
また、関連する特徴に対する信号の大きさに関する追加の仮定の下で、次元のない$O(sqrtn)$ regret上界も証明する。
論文 参考訳（メタデータ） (2020-11-08T16:48:11Z) - Stochastic Linear Bandits with Protected Subspace [51.43660657268171]
線形目的関数を最適化するが、報酬は未知の部分空間にのみ得られる線形帯域問題の変種について検討する。
特に、各ラウンドでは、学習者は、目的または保護されたサブスペースを、アクションの選択とともにクエリするかどうかを選択する必要がある。
提案アルゴリズムはOFULの原理から導かれるもので,保護された空間を推定するためにクエリのいくつかを利用する。
論文 参考訳（メタデータ） (2020-11-02T14:59:39Z) - Efficient Learning in Non-Stationary Linear Markov Decision Processes [17.296084954104415]
非定常線形(低ランク)マルコフ決定過程(MDP)におけるエピソード強化学習の研究
OPT-WLSVI は最小二乗の重み付け値に基づく楽観的なモデルフリーのアルゴリズムであり、指数重み付けを用いて過去のデータをスムーズに忘れる。
我々のアルゴリズムは、各時点で最高のポリシーと競合するときに、$d$$$widetildemathcalO(d5/4H2 Delta1/4 K3/4)$で上限付けられた後悔を実現する。
論文 参考訳（メタデータ） (2020-10-24T11:02:45Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳（メタデータ） (2020-09-04T04:10:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。