Краткое содержание

arXiv:2511.12534v1 Тип: новая работа Аннотация: Мы определяем задачу линейного контекстного стохастического поиска кратчайшего пути (CSSP), в которой в начале каждого эпизода обучающийся алгоритм наблюдает выбранный противником контекст, определяющий МППР через фиксированную, но неизвестную линейную функцию. Цель обучающегося алгоритма — достичь целевого состояния с минимальными ожидаемыми совокупными потерями, несмотря на отсутствие априорных знаний о динамике переходов, функциях потерь или отображении контекста в МППР. В данной работе мы предлагаем алгоритм LR-CSSP, который достигает границы regret $\widetilde{O}(K^{2/3} d^{2/3} |S| |A|^{1/3} B_\star^2 T_\star \log (1/ \delta))$, где $K$ — количество эпизодов, $d$ — размерность контекста, $S$ и $A$ — множества состояний и действий соответственно, $B_\star$ ограничивает оптимальные совокупные потери, а $T_\star$, неизвестный обучающемуся, ограничивает ожидаемое время достижения цели оптимальной политикой. В случае, когда все стоимости превышают $\ell_{\min}$, LR-CSSP