論文の概要: Two-Action Apple Tasting with Switching Costs

• arxiv url: http://arxiv.org/abs/2606.03851v1
• Date: Tue, 02 Jun 2026 16:28:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-03 22:00:05.15866
• Title: Two-Action Apple Tasting with Switching Costs
• Title（参考訳）: スイッチングコストによるAppleの2アクションテイスティング
• Authors: Tommaso Cesari, Roberto Colomboni,
• Abstract要約: 本研究では,不愉快な相手に対する切り替えコストを考慮に入れた2種類のリンゴテイスティング問題について検討した。 スイッチングコストの一般的なフィードバックグラフアルゴリズムは、この問題に対して$widetilde O(T2/3)$ regret guaranteesを与える。
• 参考スコア（独自算出の注目度）: 10.610898393214175
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the two-action apple-tasting problem with switching costs against an oblivious adversary. In an equivalent normalized formulation, at each round the learner chooses between a revealing action and a blind action: the revealing action gives reward $0$ and reveals the hidden value $x_t\in[-1,1]$ of the blind action; the blind action gives reward $x_t$ but reveals nothing. The learner pays one unit whenever they switches actions, and regret is measured against the best fixed action in hindsight. General feedback-graph algorithms with switching costs give $\widetilde O(T^{2/3})$ regret guarantees for this problem. The two-action apple-tasting graph was the natural candidate for the missing $Ω(T^{2/3})$ obstruction in the switching-cost classification: such a lower bound would have transferred to a large family of still-unclassified feedback graphs. We prove that this obstruction is not there: the oblivious minimax expected regret for this problem satisfies \[ \frac{1}{2\sqrt3}\cdot\sqrt T \le R_T^\star \le 2\sqrt{3}\cdot \sqrt{T}. \]
• Abstract（参考訳）: 本研究では,不愉快な相手に対する切り替えコストを考慮に入れた2種類のリンゴテイスティング問題について検討した。 同一の正規化された定式化では、各ラウンドで学習者は、露見アクションとブラインドアクションのどちらを選択するかを選択する: 露見アクションは、$0$を与え、隠された値$x_t\in[-1,1] をブラインドアクションの$x_t\in[-1,1] 明らかにする; ブラインドアクションは$x_t$を与えるが、何も明らかにしない。 学習者は、アクションを切り替えるたびに1つのユニットを支払う。 スイッチングコストの一般的なフィードバックグラフアルゴリズムは、この問題に対して$\widetilde O(T^{2/3})$ regret guaranteesを与える。 2アクションのリンゴ味付けグラフは、スイッチングコストの分類において欠落した$Ω(T^{2/3})$障害の自然な候補であった。 この問題に対する暗黙の最小限の後悔は \[ \frac{1}{2\sqrt3}\cdot\sqrt T \le R_T^\star \le 2\sqrt{3}\cdot \sqrt{T} を満たす。 \]

関連論文リスト

• Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret [64.73231630190121]
  ゼロサムゲームを学ぶことは、ゲーム理論と機械学習の基本的な問題である。 ビジットフィードバックによるゼロサムゲームにおける対戦学習について検討し,最大戦略に対する障害を最小限に抑えることを目的とした。 我々は,Tsallis-INFアルゴリズムがゲーム依存パラメータ$c$で$O(c log T)$インスタンス依存後悔を実現することを示す。
  論文  参考訳（メタデータ） (2026-02-06T03:26:01Z)
• Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
  本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。 ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
  論文  参考訳（メタデータ） (2024-04-02T12:15:37Z)
• Apple Tasting: Combinatorial Dimensions and Minimax Rates [16.52706654413988]
  エンファップル味覚フィードバックに基づくオンライン二項分類では、学習者は1を予測した場合のみ真のラベルを観察する。 実現可能な設定では、期待されるミスの回数が$Theta$または$Theta(T)$であることを示す。
  論文  参考訳（メタデータ） (2023-10-29T16:37:51Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Better Best of Both Worlds Bounds for Bandits with Switching Costs [37.71741656687868]
  本稿では,2021年にRouryer,Seldin,Cesa-Bianchiらにより,スイッチングコストを伴うバンディットのベスト・オブ・ザ・ワールドス・アルゴリズムについて検討した。 本稿では, 極小最小の最小残差を$mathcalO(T2/3)$で同時に達成する, 驚くほど単純かつ効果的に導入する。
  論文  参考訳（メタデータ） (2022-06-07T08:22:56Z)
• The price of unfairness in linear bandits with biased feedback [62.25313751895011]
  線形帯域フィードバックによる逐次意思決定の問題点について検討する。 その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。 興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
  論文  参考訳（メタデータ） (2022-03-18T08:03:20Z)
• Adversarial Dueling Bandits [85.14061196945599]
  本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2020-10-27T19:09:08Z)

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

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