論文の概要: Search as Computation Allocation

• arxiv url: http://arxiv.org/abs/2607.27871v1
• Date: Thu, 30 Jul 2026 08:45:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-31 21:37:00.466994
• Title: Search as Computation Allocation
• Title（参考訳）: 計算割当としての探索
• Abstract要約: 多くのアルゴリズムは、決定を返す前に内部リソースを使い、その端末出力の品質によってのみ評価される。 終端計算割当問題などの手順を定式化する。 ベルマン方程式は、固定予算の下での最適割り当て、価格計算、正確な認証を特徴付ける。
• 参考スコア（独自算出の注目度）: 52.080489413778
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many algorithms spend an internal resource before returning a decision and are evaluated only by the quality of that terminal output. We formalize such procedures as terminal computation-allocation problems: costly computations produce observations, update beliefs about a latent environment, and matter only through terminal decision loss. Bellman equations characterize optimal allocation under fixed budgets, priced computation, and exact certification. We then relate value of computation (VOC) to information. Mutual information equals myopic VOC under log loss, whereas under simple regret VOC is a knowledge-gradient quantity; moreover, information gain can rank computations arbitrarily poorly, although it gives a one-sided upper bound on VOC. Bandit pulls, tree simulations, and node expansions illustrate the same model under different computation topologies. Finally, under an explicit frontier-resolution and heuristic-error model, maximizing approximate VOC recovers weighted A*, with A* and greedy best-first search as limiting cases. The theory identifies a shared decision problem without asserting that one acquisition rule is universally optimal.
• Abstract（参考訳）: 多くのアルゴリズムは、決定を返す前に内部リソースを使い、その端末出力の品質によってのみ評価される。 計算コストのかかる計算によって観測結果が生成され、潜伏環境に関する信念が更新され、終末決定損失によってのみ問題が発生する。 ベルマン方程式は、固定予算の下での最適割り当て、価格計算、正確な認証を特徴付ける。 次に、計算値(VOC)を情報に関連付ける。 相互情報はログ損失下でのミオピックVOCと等しいが、単純な後悔ではVOCは知識の段階的な量であり、情報ゲインはVOC上の一方の上限を与えるが、任意に計算をランク付けすることができない。 Banditプル、ツリーシミュレーション、ノード拡張は、異なる計算トポロジの下で同じモデルを示している。 最後に、明示的なフロンティア分解能とヒューリスティックエラーモデルの下で、近似VOCはA*の重み付けを最大化し、A*とgreedyベストファーストサーチを制限ケースとして回復する。 この理論は、一つの獲得規則が普遍的に最適であると主張することなく、共有決定問題を特定する。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation [32.74649239695449]
  制約決定過程(CMDP)における強化学習問題について検討する。 本稿では,リニアCMDPに対するRLアルゴリズムを提案する。 その結果,近年の線形CMDPアルゴリズムでは,制約に違反するか,指数計算コストに悪影響を及ぼす結果が得られた。
  論文  参考訳（メタデータ） (2025-02-14T13:07:25Z)
• Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs [16.49229317664822]
  線形決定過程(MDP)を用いた無限水平平均逆強化学習の問題点について検討する。 提案手法は, 平均再帰設定を割引係数で近似し, 楽観的な値反復を適用した。
  論文  参考訳（メタデータ） (2024-05-23T20:58:33Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes [59.61248760134937]
  本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。 提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。 本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
  論文  参考訳（メタデータ） (2022-12-12T15:04:56Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。 各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。 一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-23T09:03:24Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• An Efficient Algorithm for Cooperative Semi-Bandits [0.0]
  本稿では,有名なFollow The Perturbed Leaderアルゴリズムの協調バージョンであるCoop-FTPLを紹介する。 T 時間ステップ後のアルゴリズムの期待された後悔は QT log(k)(k$alpha$ 1 /Q + m) であり、Q は総アクティベーション確率質量である。
  論文  参考訳（メタデータ） (2020-10-05T07:08:26Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• All your loss are belong to Bayes [28.393499629583786]
  ロス関数は機械学習の基盤であり、ほとんどのアルゴリズムの出発点である。 正方形ガウス過程を用いて経路が整合なソース関数を持つランダムな過程を求める。 実験の結果は、最先端技術よりも大幅に改善された。
  論文  参考訳（メタデータ） (2020-06-08T14:31:21Z)

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

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