論文の概要: What Must Survive? Exact Task-Information--State Frontiers for Resource-Sufficient Learning
- arxiv url: http://arxiv.org/abs/2609.21523v1
- Date: Fri, 18 Sep 2026 09:12:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-21 18:40:16.943945
- Title: What Must Survive? Exact Task-Information--State Frontiers for Resource-Sufficient Learning
- Title（参考訳）: 生き残らなければならないものは何か?-資源に十分な学習のための具体的なタスク情報--状態フロンティア
- Abstract要約: 先行タスク情報は、共同タスクオペレーターのランクが低いパーティションを通じて状態を低減します。
ドメイン・デ・デジタル双対は、異種領域に対するインターフェイス+局所状態法則と重み付き分割問題をもたらす。
階層的なマルチタスクモデルにより、3ビットで必要な状態を336ドルから448ドルに減らす2段階のフロンティアが得られる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A system may be compressed before its downstream task is fully known. We ask how much retained state is then necessary and how much can be saved by limited advance task information. For a finite family of linear tasks, a task message is revealed before state formation and the exact task only afterwards. For an advice alphabet of size $K$, the exact frontier is \[ p^*(K)= \min_{\substack{\Pcal\text{ partition of }\U\\|\Pcal|\le K}} \max_{C\in\Pcal}\rank(T_C), \] with the $b$-bit frontier obtained by setting $K=\min(2^b,|\U|)$. Thus advance task information reduces state through partitions whose joint task operators have low rank. We also give an approximate singular-value frontier, a common-core lower bound and exact direct-sum law, and strong NP-hardness of finding an optimal advice partition. The hardness persists at every fixed positive approximation tolerance. Three examples illustrate the result. A well-conditioned softmax attention construction gives an exact $524{,}288\to1{,}024$ coordinate frontier when nine bits resolve one of $512$ continuations. A domain-decomposed digital twin yields an interface-plus-local-state law and a weighted partition problem for heterogeneous regions. A hierarchical multi-task model gives a two-stage frontier in which three bits reduce the required state from $3136$ to $448$ coordinates, with further task information approaching the irreducible $328$-coordinate single-task floor.
- Abstract（参考訳）: システムは、下流のタスクが完全に知られる前に圧縮される。
限られた事前タスク情報によって、どれだけの保持状態が必要か、どのくらい節約できるかを問う。
有限種類の線形タスクに対して、状態形成の前にタスクメッセージが明らかにされ、その後のみ正確なタスクが生成される。
K$のアドバイスアルファベットに対して、正確なフロンティアは \[p^*(K)= \min_{\substack{\Pcal\text{ partition of }\U\\|\Pcal|\le K}} \max_{C\in\Pcal}\rank(T_C), \] であり、$b$-bitフロンティアは$K=\min(2^b,|\U|)$を設定することで得られる。
このように、先行タスク情報は、共同タスクオペレーターが低いパーティションを介して状態を減少させる。
また、近似特異値フロンティア、共通コア下限法則、厳密直和法則、そして最適なアドバイス分割を見つけるためのNP硬度も与えている。
この硬さは、固定された正の近似許容度ごとに持続する。
3つの例が結果を示している。
良好な条件付きソフトマックスアテンション構成は、9ビットが512$連続の1つを解くとき、正確に524{,}288\to1{,}024$座標フロンティアを与える。
ドメイン分解されたデジタル双対は、界面+局所状態法則とヘテロジニアス領域に対する重み付き分割問題をもたらす。
階層的なマルチタスクモデルにより、3ビットで必要な状態を3,136ドルから448ドルに下げる2段階のフロンティアが実現される。
関連論文リスト
- Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。
失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
論文 参考訳（メタデータ） (2026-07-22T07:42:19Z) - Reinforcement Learning from Adversarial Preferences in Tabular MDPs [62.73758165845971]
我々は,敵対的嗜好を持つエピソードマルコフ決定プロセス(MDP)の新たな枠組みを導入する。
PbMDP では、標準的なエピソード MDP とは異なり、学習者は2つの候補アーム間の好みを観察する。
我々は、既知遷移の下で、T2/3$という残差境界を達成するアルゴリズムを開発する。
論文 参考訳（メタデータ） (2025-07-15T20:19:32Z) - Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-07T15:03:50Z) - Tight Bounds for Quantum Phase Estimation and Related Problems [0.90238471756546]
精度$delta$と誤差確率$epsilon$は$Omegaleft(frac1deltalog1epsilonright)$であることを示す。
また、多くのアドバイス(アドバイス準備ユニタリの応用)を持つことは、コストを大幅に削減することはなく、また、$U$の固有値に関する知識も少なくないことも示している。
論文 参考訳（メタデータ） (2023-05-08T17:46:01Z) - Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。
我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
論文 参考訳（メタデータ） (2022-03-29T15:27:13Z) - Decentralized Cooperative Reinforcement Learning with Hierarchical
Information Structure [14.919120396838208]
本稿では,2エージェントマルチアームバンド (MABs) とマルコフ決定プロセス (MDPs) を,アプリケーションに生じる階層的情報構造を用いて検討する。
それぞれのステップにおいて、"リーダー"はまず彼女の行動を選択し、その後に"フォロワー"はリーダーの行動を観察して自分の行動を決定する。
MDP設定の場合、$widetildemathcalO(sqrtH7S2ABT)$ regret, where $H$ is the number of episode, $S$ is the number of states。
論文 参考訳（メタデータ） (2021-11-01T09:18:07Z) - The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。
バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
論文 参考訳（メタデータ） (2021-06-18T07:54:23Z) - Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。
textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
論文 参考訳（メタデータ） (2020-10-12T17:51:19Z) - A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with
Constraints [8.849815837266977]
制約付きマルコフ決定プロセス(CMDP)は、シーケンシャルな意思決定問題を定式化する。
本稿では, 有限水平CMDPの線形計画法を利用して, 繰り返し楽観的な計画を立てるオンラインアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-23T19:30:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。