論文の概要: Stochastic Reset Pathfinding: Path-Level Regret for Cascading Bandits over Graph Paths
- arxiv url: http://arxiv.org/abs/2607.15440v1
- Date: Thu, 16 Jul 2026 20:20:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-20 17:56:52.696935
- Title: Stochastic Reset Pathfinding: Path-Level Regret for Cascading Bandits over Graph Paths
- Title（参考訳）: 確率的リセットパスフィニング:グラフパス上の帯域カスケーディングのためのパスレベルレグレット
- Abstract要約: リセットパスフィンディング(Reset Pathfinding, SRP)は, 未知の定常エッジ成功確率を持つ有向グラフ上のエピソード学習問題である。
我々は,グローバルリセット構造が最適ポリシをオープンループ化し,SRPをカスケードバンディットフレームワークに配置することを示す。
次に、PathTSが収束しない逆例を示し、Thompson Smpling の乗法-逆問題に対する指数的障害として知られている。
- 参考スコア（独自算出の注目度）: 8.45964131620018
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce Stochastic Reset Pathfinding (SRP), an episodic learning problem on a known directed graph with unknown stationary edge success probabilities. In each episode, the agent commits to a source-to-goal path, and any edge failure during execution resets it to the source. SRP captures settings such as entanglement distribution in quantum repeater networks, payment routing on the Lightning Network, and delivery in unreliable mesh networks. We show that the global-reset structure makes the optimal policy open-loop, placing SRP within the combinatorial cascading bandit (CCB) framework. We propose a Log-Dijkstra meta-algorithm with UCB (PathUCB) and Thompson Sampling (PathTS) instantiations. Our main technical result is a path-level regret bound for PathUCB that decomposes regret over suboptimal paths via a per-path complexity C(pi) combining each edge's prefix and suffix reliability. The bound is complementary to the edge-level CCB bound and more informative on structured graphs with polynomially many source-to-goal paths. Experiments on quantum-network, layered-DAG, grid-world, and Erdos-Renyi domains support the theory and show that PathTS typically achieves the best empirical performance among the algorithms tested. We then exhibit an adversarial instance on which PathTS fails to converge, consistent with a known exponential obstruction for combinatorial Thompson Sampling on multiplicative-reward problems. We recommend PathTS as the practical default while cautioning that adversarial instances exist.
- Abstract（参考訳）: 本稿では,未知の定常エッジ成功確率を持つ有向グラフ上のエピソード学習問題である確率的リセットパスフィンディング(SRP)を紹介する。
各エピソードにおいて、エージェントはソースからゴールへのパスにコミットし、実行中のエッジ障害はソースにリセットする。
SRPは量子リピータネットワークでの絡み合い分布、Lightningネットワークでの支払いルーティング、信頼性の低いメッシュネットワークでの配信などの設定をキャプチャする。
我々は,グローバルリセット構造が最適ポリシをオープンループにし,SRPをCCBフレームワークに配置することを示す。
UCB(PathUCB)とThompson Sampling(PathTS)インスタンスを用いたLog-Dijkstraメタアルゴリズムを提案する。
主な技術的結果はPathUCBに対するパスレベルの後悔であり、各エッジのプレフィックスと接尾辞の信頼性を組み合わせたパス毎の複雑性C(pi)を介して、最適パスに対する後悔を分解する。
境界は、エッジレベル CCB 境界と相補的であり、多項式的に多くのソース-ゴールパスを持つ構造化グラフ上でより情報的である。
量子ネットワーク、層状DAG、グリッドワールド、エルドス・レニイ領域の実験は、この理論を支持し、PathTSがテストされたアルゴリズムの中で最も優れた経験的性能を達成することを示す。
次に、PathTSが収束に失敗する逆例を示し、乗法-逆問題に対する組合せトンプソンサンプリングの指数的障害として既知のものと整合する。
PathTSを事実上のデフォルトとして推奨するとともに、敵インスタンスの存在を警告します。
関連論文リスト
- Columnar-Embedder: A Biologically Inspired Cortical Architecture for Binary Sparse Distributed Graph Representations [0.0]
グラフノードのスパース分散表現を学習するためのカラムナー・エンベッドダーアーキテクチャを提案する。
このアーキテクチャは、ポータビリティ、ノイズに対するレジリエンス、データの破損に対する堅牢性を示す。
5つのグラフベンチマークにおいて、SDRの性能は実数値密度埋め込みと競合する。
論文 参考訳（メタデータ） (2026-08-12T03:31:39Z) - GeoRouteNet: Geometry-Enhanced Non-Autoregressive Neural Solver for the Traveling Salesman Problem [5.202950948929751]
GeoRouteNetはユークリッド旅行セールスマン問題(TSP)のための幾何学強化ニューラルネットワークである
モデル側では、GeoRouteNetには、中心ノード機能、学習可能なラジアル距離基底関数、距離対応グラフアテンション、LayerNorm-SwiGLUフィードフォワードブロック、層間減衰残エンコーダミキシングが組み込まれている。
トレーニング側では,インスタンス毎に複数の候補ツアーを抽出するマルチ候補自己比較強化学習(MCS-RL)を設計する。
論文 参考訳（メタデータ） (2026-06-22T02:31:22Z) - AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network [50.69521065962045]
Anisotropic Graph Diffusion Network (AGDN) はトラベリングセールスマン問題(TSP)を解決するために設計された新しいグラフニューラルネットワークフレームワークである。
提案手法は,1) 完全連結TSPグラフにおける情報的トポロジ的事前の欠如,2) グラフスペーシフィケーション手法により最適解における接続ノードの喪失,の2つの問題に対処する。
AGDNは、競争力を維持しながら、既存の手法を一貫して上回る。
論文 参考訳（メタデータ） (2026-06-17T15:24:37Z) - Stochastic Multipath Routing for High-Throughput Entanglement Distribution in Quantum Repeater Networks [6.036769600366487]
量子リピータネットワークは損失のあるリンク上の絡み合いを分散し、多くのユーザは絡み合ったペアの限られたプールを共有している。
既存のルーティング方式の多くは、常に単一のベストパスを使用するか、あるいはリアルタイムに実行が難しいグローバル最適化に依存している。
本稿では,複数のエッジ不連続経路の1つに沿って,各絡み合い要求をランダムに送信するマルチパスルールを提案する。
論文 参考訳（メタデータ） (2026-03-26T15:36:08Z) - Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
本研究では,有限水平マルコフ決定過程(MDP)におけるオンライン学習について,包括的包括的包括的フィードバックモデルを用いて検討する。
本研究は, オンライン最短経路問題の近年の進展に触発された, 占領対策, 自己拘束技術, 新たな損失推定器の組合せに依拠する。
論文 参考訳（メタデータ） (2025-10-20T02:28:08Z) - Unsupervised Learning for the Elementary Shortest Path Problem [5.617211365270248]
プライマリ・ショート・パス問題(英語版) (ESPP) は、s から t への最小のコストパスを求め、それぞれを一度に訪問する。
本稿では,教師なしグラフニューラルネットワークによって実現された近似ESPPの確率的探索法を提案する。
論文 参考訳（メタデータ） (2025-08-03T03:03:05Z) - Find A Winning Sign: Sign Is All We Need to Win the Lottery [52.63674911541416]
既存のIP手法によって訓練されたスパースネットワークは,パラメータ記号と正規化層パラメータが保存されている場合,アトラクションの基盤を保持することができることを示す。
本手法により訓練されたスパースネットワークと正規化層パラメータとの線形経路における高い誤差障壁を防止し, 正規化層パラメータへの依存を緩和する。
論文 参考訳（メタデータ） (2025-04-07T09:30:38Z) - Enhancing Path Planning Performance through Image Representation Learning of High-Dimensional Configuration Spaces [0.4143603294943439]
障害物のある未知のシーンにおける経路計画タスクを高速化する新しい手法を提案する。
高速探索ランダムツリーアルゴリズムを用いて,衝突のない経路の経路点分布を近似した。
本実験は,臨界時間制約下での経路計画タスクを高速化する有望な結果を実証する。
論文 参考訳（メタデータ） (2025-01-11T21:14:52Z) - Exact Gradients for Stochastic Spiking Neural Networks Driven by Rough Signals [4.272515397452792]
事象不連続性を持つ微分方程式としてスパイキングニューラルネットワーク(SSNN)をモデル化するための数学的に厳密な枠組み(イベントSDE)を導入する。
我々の定式化は、解軌跡と駆動雑音の両方に潜在的なジャンプが現れるのに十分である。
我々のフレームワークは、我々の知る限り、スパイクタイミングとネットワークのダイナミクスの両方に影響を与えるノイズを伴うSSNNの勾配に基づくトレーニングを可能にする最初のものである。
論文 参考訳（メタデータ） (2024-05-22T12:34:04Z) - Robust Stochastically-Descending Unrolled Networks [85.6993263983062]
Deep Unrolling(ディープ・アンローリング)は、トレーニング可能なニューラルネットワークの層に切り捨てられた反復アルゴリズムをアンロールする、新たな学習最適化手法である。
アンロールネットワークの収束保証と一般化性は、いまだにオープンな理論上の問題であることを示す。
提案した制約の下で訓練されたアンロールアーキテクチャを2つの異なるアプリケーションで数値的に評価する。
論文 参考訳（メタデータ） (2023-12-25T18:51:23Z) - Rethinking PGD Attack: Is Sign Function Necessary? [131.6894310945647]
本稿では,このような手話に基づく更新アルゴリズムが段階的攻撃性能にどのように影響するかを理論的に分析する。
本稿では,手話の使用を排除したRGDアルゴリズムを提案する。
提案したRGDアルゴリズムの有効性は実験で広く実証されている。
論文 参考訳（メタデータ） (2023-12-03T02:26:58Z) - Regret Bounds for Noise-Free Cascaded Kernelized Bandits [45.551266812295005]
RKHS関数クラスを用いたノイズフリーグレーボックス設定において,関数ネットワークの最適化を検討する。
本研究では,(1)チェーン:スカラー値関数のカスケード,(2)マルチアウトプットチェーン:ベクトル値関数のカスケード,(3)フィードフォワードネットワーク:完全に接続されたスカラー値関数のフィードフォワードネットワークの3種類の構造について検討する。
論文 参考訳（メタデータ） (2022-11-10T09:12:55Z) - DHP: Differentiable Meta Pruning via HyperNetworks [158.69345612783198]
本稿では,ネットワークの自動プルーニングのためのハイパーネットによる識別可能なプルーニング手法を提案する。
遅延ベクトルは、バックボーンネットワーク内の畳み込み層の出力チャネルを制御し、レイヤのプルーニングのハンドルとして機能する。
画像分類、単一画像超解像、復調のための様々なネットワークで実験が行われた。
論文 参考訳（メタデータ） (2020-03-30T17:59:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。