論文の概要: Computing Complexity-aware Plans Using Kolmogorov Complexity

• arxiv url: http://arxiv.org/abs/2109.10303v2
• Date: Wed, 22 Sep 2021 16:17:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-23 10:36:00.723630
• Title: Computing Complexity-aware Plans Using Kolmogorov Complexity
• Title（参考訳）: コルモゴロフ複雑性を用いた計算複雑性認識計画
• Authors: Elis Stefansson, Karl H. Johansson
• Abstract要約: 有限水平決定性有限オートマトンを出力として計算する複雑性を考慮した計画法を提案する。 本稿では,2つのアルゴリズムで低複素性ポリシーを求め,第1のアルゴリズムで低複素性最適ポリシーを求める。 移動ロボットの単純なナビゲーションタスクにおけるアルゴリズムの評価を行い,そのアルゴリズムは直感と一致する低複雑さのポリシーを導出する。
• 参考スコア（独自算出の注目度）: 0.9137554315375922
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we introduce complexity-aware planning for finite-horizon deterministic finite automata with rewards as outputs, based on Kolmogorov complexity. Kolmogorov complexity is considered since it can detect computational regularities of deterministic optimal policies. We present a planning objective yielding an explicit trade-off between a policy's performance and complexity. It is proven that maximising this objective is non-trivial in the sense that dynamic programming is infeasible. We present two algorithms obtaining low-complexity policies, where the first algorithm obtains a low-complexity optimal policy, and the second algorithm finds a policy maximising performance while maintaining local (stage-wise) complexity constraints. We evaluate the algorithms on a simple navigation task for a mobile robot, where our algorithms yield low-complexity policies that concur with intuition.
• Abstract（参考訳）: 本稿では,コルモゴロフ複雑性に基づく有限水平決定性有限オートマトンに対する複雑性を考慮した計画法を提案する。 コルモゴロフの複雑性は、決定論的最適政策の計算的正則性を検出できるため考慮される。 政策のパフォーマンスと複雑さの間に明確なトレードオフをもたらす計画目標を示す。 この目的を最大化することは、動的プログラミングが実現不可能であるという意味では非自明であることが証明されている。 そこで,第1のアルゴリズムは低複雑さの最適ポリシを,第2のアルゴリズムは局所的な(段階的な)複雑性制約を維持しつつ,性能を最大化するポリシを求める。 移動ロボットの単純なナビゲーションタスクでアルゴリズムを評価することにより,直観に合致する低複雑さポリシが実現される。

関連論文リスト

• Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint [0.0]
  本研究は,knapsack制約下での非モジュラーサイズに対する効率的な並列アルゴリズムを提案する。 我々のアルゴリズムは, 既存の並列処理を 8+epsilon$ から 7+epsilon$ に改良し, 適応複雑性を$O(log n)$ にする。
  論文  参考訳（メタデータ） (2024-09-06T17:17:52Z)
• Flow-Lenia.png: Evolving Multi-Scale Complexity by Means of Compression [0.0]
  セルオートマトン状態に対するマルチスケール複雑度を定量化する適合度尺度を提案する。 圧縮性の使用はコルモゴロフ複雑性(英語版)(Kolmogorov complexity)の概念に基づいている。
  論文  参考訳（メタデータ） (2024-08-08T04:13:17Z)
• On efficient computation in active inference [1.1470070927586016]
  計算量を大幅に減らした有限時間地平線に対する新しい計画アルゴリズムを提案する。 また、新規かつ既存のアクティブな推論計画スキームに対して適切な目標分布を設定するプロセスを簡単にする。
  論文  参考訳（メタデータ） (2023-07-02T07:38:56Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• Near-optimal Policy Identification in Active Reinforcement Learning [84.27592560211909]
  AE-LSVI はカーネル化された最小二乗値 RL (LSVI) アルゴリズムの新しい変種であり、楽観主義と悲観主義を組み合わせて活発な探索を行う。 AE-LSVIは初期状態に対するロバスト性が必要な場合、様々な環境で他のアルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-12-19T14:46:57Z)
• Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
  主アルゴリズムは、独立した関心を持つ可能性のある2つのコンポーネントから組み立てられる。 LINEARSEQの変種は、文献のどのアルゴリズムよりも小さい$O(log(n))$の適応複雑性を持つ。
  論文  参考訳（メタデータ） (2021-11-15T17:10:40Z)
• Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
  既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。 提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
  論文  参考訳（メタデータ） (2021-03-03T22:42:15Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• On the Sample Complexity of Reinforcement Learning with Policy Space Generalization [21.879621917722613]
  政策空間の一般化を伴う大規模強化学習(RL)問題における最適なサンプル複雑性について検討する。 既存の結果は、一般化モデルがなければ、RLアルゴリズムのサンプルの複雑さは必然的に状態空間と行動空間の濃度に依存することを示している。 本稿では,政策学習の本質的な複雑さを特徴付ける,政策空間におけるユーラダー次元の新たな概念を提案する。
  論文  参考訳（メタデータ） (2020-08-17T14:26:18Z)
• Jump Operator Planning: Goal-Conditioned Policy Ensembles and Zero-Shot Transfer [71.44215606325005]
  本稿では,シーケンシャルなサブゴールタスクの超指数空間における解を高速に計算するための,Jump-Operator Dynamic Programmingという新しいフレームワークを提案する。 このアプローチでは、時間的に拡張された行動として機能する、再利用可能な目標条件付き警察のアンサンブルを制御する。 すると、この部分空間上の目的関数のクラスを、解がグラウンド化に不変であるものとして特定し、最適ゼロショット移動をもたらす。
  論文  参考訳（メタデータ） (2020-07-06T05:13:20Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)

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

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