論文の概要: The Role of Coordinates in Pareto Regret for Adversarial Multi-Objective Bandits

• arxiv url: http://arxiv.org/abs/2609.23092v1
• Date: Sat, 19 Sep 2026 15:59:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-22 20:29:00.674829
• Title: The Role of Coordinates in Pareto Regret for Adversarial Multi-Objective Bandits
• Title（参考訳）: 対向多目的バンドにおけるパレートレグレットにおけるコーディネートの役割
• Abstract要約: 敵対的多目的包帯は、敵が選択した多次元ベクトルである選択(アーム)を最適化するのに役立つ可能性を秘めている。 我々は、損失を1つのマイナス報酬として定義し、その上のアームの最小累積損失によって座標の容易さを測り、この量が小さくなると容易に座標を呼び出す。
• 参考スコア（独自算出の注目度）: 4.452583096196013
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Adversarial multi-objective bandits hold the potential to help us optimize choices (arms) whose reward is a multidimensional vector chosen by an adversary and whose performance is measured by Pareto regret. We define loss as one minus reward and measure the easiness of a coordinate by the smallest cumulative loss of the arms on it, and call the coordinate easier when this quantity is smaller. Existing work suggests that in theory an easier coordinate may reduce Pareto regret. However, in practice, one may not know which coordinate is easier. On the negative side, we show that this lack of information eliminates the possibility: a smaller cumulative loss does not improve the worst-case order of Pareto regret. Precisely, let \(L_d\) be the smallest cumulative loss along coordinate $d$ over $T$ rounds. For \(K\ge4\) arms, \(T\ge6\) rounds, and at least 2 coordinates, we prove that the minimax expected Pareto regret is \(Ω(\min\{T-L_0,\sqrt{K(T-L_0)}\})\). It is monotonically decreasing in \(L_0\), even when \(L_0=\min_d L_d\) itself is known. On the positive side, this result motivates the possibility that other coordinates, not just the easy one, may suffice to attain the optimal rate of Pareto regret. When $L_0$ is known, we apply Poly-INF to a fixed coordinate and obtain an upper bound on Pareto regret that exhibits the same order and thus matches the lower bound. Without such knowledge, we develop a reward-doubling version of Poly-INF that adapts to this unknown quantity while still attaining the matching minimax rate. Another implication is that it has no extra \(\log T\) factor and is independent of the number of coordinates.
• Abstract（参考訳）: 逆多目的バンディットは、相手が選択した多次元ベクトルであり、パレートが後悔する多次元ベクトルである選択(アーム)を最適化するのに役立つ可能性を秘めている。 我々は、損失を1つのマイナス報酬として定義し、その上のアームの最小累積損失によって座標の容易さを測り、この量が小さくなると容易に座標を呼び出す。 現存する研究は、理論上より簡単な座標がパレートの後悔を和らげる可能性を示唆している。 しかし実際には、どの座標が簡単かを知らないかもしれない。 負の面から、この情報の欠如は可能性を排除する: 累積損失が小さくても、パレートの最悪の順序は改善されない。 正確には、(L_d\) を座標 $d$ over $T$ ラウンドに沿って最小の累積損失とする。 \(K\ge4\) の腕、 \(T\ge6\) の円、および少なくとも2つの座標に対して、パレートの最小限の後悔は \(Ω(\min\{T-L_0,\sqrt{K(T-L_0)}\})\ であることが証明される。 \(L_0=\min_d L_d\)自体が知られている場合でも、単調に減少する。 正の面において、この結果は、単に簡単な座標ではなく他の座標がパレートの最適率を達成するのに十分である可能性を動機付けている。 L_0$が知られているとき、固定座標にpoly-INFを適用して、同じ順序を示し、従って下界と一致するパレート後悔の上界を得る。 このような知識がなければ、我々はこの未知の量に適応しつつ、一致するミニマックスレートを達成できるポリインフルエンス(Poly-INF)の報奨倍版を開発する。 もう一つの意味は、余分な \(\log T\) 因子を持たず、座標の数に依存しないことである。

関連論文リスト

• Are Stochastic Multi-objective Bandits Harder than Single-objective Bandits? [4.452583096196013]
  多目的包帯は、各腕の報酬がスカラーではなく多次元ベクトルである広い適用性とエレガンスのため、注目を集めている。 この領域における長年の疑問は、この複雑さが加わったため、パフォーマンスを最適化するのが困難であるかどうかである。 我々は注文の最小限の後悔を達成する新しいアルゴリズム (fracKlog Tgdagger) を開発する。
  論文  参考訳（メタデータ） (2026-04-08T13:48:54Z)
• A conversion theorem and minimax optimality for continuum contextual bandits [64.9814493154015]
  本研究では,学習者が側情報ベクトルを逐次受信し,凸集合内の行動を選択する,文脈連続帯域幅問題について検討する。 目標は、受信したコンテキストのすべての基盤関数を最小化することです。 サブ線形の静的な後悔を達成するアルゴリズムを拡張して、サブ線形の文脈的後悔を実現することができることを示す。
  論文  参考訳（メタデータ） (2024-06-09T10:12:08Z)
• An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
  線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。 R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-06-03T17:54:58Z)
• Learning the Pareto Front Using Bootstrapped Observation Samples [17.519167857253404]
  本研究では,非支配的な平均報酬ベクトルを持つアームの集合を同定するアルゴリズムを提案する。 提案アルゴリズムのサンプル複雑性は対数係数まで最適である。 主要なコントリビューションは、新しい推定器で、ラウンド毎に、未知のパラメータの見積もりを複数のコンテキスト方向に沿って更新する。
  論文  参考訳（メタデータ） (2023-05-31T18:15:09Z)
• Adversarial Dueling Bandits [85.14061196945599]
  本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2020-10-27T19:09:08Z)
• Stochastic Bandits with Vector Losses: Minimizing $\ell^\infty$-Norm of Relative Losses [21.085722900446257]
  マルチアームバンディットは、クリック率の最大化を目標とするレコメンデーションシステムに広く適用されている。 本稿では、この状況を複数の損失を伴って、$K$の武器付きバンディットの問題としてモデル化する。
  論文  参考訳（メタデータ） (2020-10-15T23:03:35Z)

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

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