Новый метод SRP улучшает обучение на графах для квантовых сетей и Lightning Network
Ученые предложили новый метод машинного обучения — Stochastic Reset Pathfinding (SRP). Он решает задачу поиска пути на направленном графе с неизвестными вероятностями успеха ребер. Агент выбирает путь от источника к цели, и если ребро ломается, он возвращается в начало. Такая постановка актуальна для квантовых ретрансляционных сетей, маршрутизации платежей в Lightning Network и доставки данных в ненадежных mesh-сетях.
Исследователи показали, что глобальный сброс делает оптимальную политику разомкнутой, что позволяет вписать SRP в рамки комбинаторных каскадных бандитов (CCB). На основе этого разработаны два алгоритма: PathUCB (на основе Upper Confidence Bound) и PathTS (на основе Thompson Sampling).
Основной теоретический результат — граница сожаления на уровне путей для PathUCB. Она раскладывает сожаление по субоптимальным путям через сложность каждого пути, которая комбинирует надежность префикса и суффикса каждого ребра. Эта граница дополняет существующие оценки и информативна на структурированных графах с полиномиальным числом путей.
Эксперименты проводились на четырех типах графов: квантово-сетевых, слоистых DAG, решетчатых и случайных (Эрдеша — Реньи). Результаты подтвердили теорию: PathTS показал наилучшую эмпирическую производительность среди протестированных алгоритмов.
Однако на специально построенном adversarial примере PathTS не сходится. Это согласуется с известной экспоненциальной трудностью комбинаторного Thompson Sampling для задач с мультипликативной наградой. Авторы рекомендуют PathTS как практический выбор по умолчанию, предупреждая о существовании adversarial случаев.
Работа размещена в открытом доступе на arXiv и может найти применение в системах, где важна устойчивость к сбоям при последовательном прохождении узлов.
