Scholarlink

<p>We introduce FVRL (Fleming–Viot reinforcement learning), a reinforcement learning algorithm for optimisation problems where a long-term objective is largely influenced by states that are very rarely observed under all policies. In this context, usual discovery techniques including importance sampling are inapplicable because no alternative policy exists that increases the observed frequency of the rare states. We instead propose a novel approach that uses Fleming–Viot particle systems, a family of stochastic processes evolving simultaneously under the same law, that exploits prior knowledge of the environment to boost exploration of the rare states. A renewal theory argument allows us to consistently estimate the stationary probability of the rare states from excursions that have considerably lower sample complexity than usual Monte Carlo explorations. We demonstrate how to combine this estimator with policy gradient learning to construct the FVRL algorithm, which is suited to efficiently solve problems where the optimisation function is expressed as a long-run expectation, such as the long-run expected reward. We show that the FVRL algorithm converges to a local optimiser of the parameterised objective function, and illustrate the method on two optimisation problems that aim at minimising the long-run expected cost under admission control policies of threshold type: a simple <i>M</i>/<i>M</i>/1 queue system and a two-job-class loss network. Our experimental results show that, under the same sample complexity, FVRL outperforms a vanilla Monte Carlo reinforcement learning method by converging to the optimum thresholds considerably faster.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Fast-exploring reinforcement learning with applications to stochastic networks

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年9月9日

查看全文
  • D. Mastropietro,
  • U. Ayesta,
  • M. Jonckheere,
  • S. Majewski

摘要

We introduce FVRL (Fleming–Viot reinforcement learning), a reinforcement learning algorithm for optimisation problems where a long-term objective is largely influenced by states that are very rarely observed under all policies. In this context, usual discovery techniques including importance sampling are inapplicable because no alternative policy exists that increases the observed frequency of the rare states. We instead propose a novel approach that uses Fleming–Viot particle systems, a family of stochastic processes evolving simultaneously under the same law, that exploits prior knowledge of the environment to boost exploration of the rare states. A renewal theory argument allows us to consistently estimate the stationary probability of the rare states from excursions that have considerably lower sample complexity than usual Monte Carlo explorations. We demonstrate how to combine this estimator with policy gradient learning to construct the FVRL algorithm, which is suited to efficiently solve problems where the optimisation function is expressed as a long-run expectation, such as the long-run expected reward. We show that the FVRL algorithm converges to a local optimiser of the parameterised objective function, and illustrate the method on two optimisation problems that aim at minimising the long-run expected cost under admission control policies of threshold type: a simple M/M/1 queue system and a two-job-class loss network. Our experimental results show that, under the same sample complexity, FVRL outperforms a vanilla Monte Carlo reinforcement learning method by converging to the optimum thresholds considerably faster.