2025-11-17T07:58:12.711519

Posterior Sampling for Continuing Environments

Xu, Dong, Van Roy

We develop an extension of posterior sampling for reinforcement learning (PSRL) that is suited for a continuing agent-environment interface and integrates naturally into agent designs that scale to complex environments. The approach, continuing PSRL, maintains a statistically plausible model of the environment and follows a policy that maximizes expected $Î³$-discounted return in that model. At each time, with probability $1-Î³$, the model is replaced by a sample from the posterior distribution over environments. For a choice of discount factor that suitably depends on the horizon $T$, we establish an $\tilde{O}(ÏS \sqrt{A T})$ bound on the Bayesian regret, where $S$ is the number of environment states, $A$ is the number of actions, and $Ï$ denotes the reward averaging time, which is a bound on the duration required to accurately estimate the average reward of any policy. Our work is the first to formalize and rigorously analyze the resampling approach with randomized exploration.

academic

Posterior Sampling for Continuing Environments

基本信息

论文ID: 2211.15931
标题: Posterior Sampling for Continuing Environments
作者: Wanqiao Xu (Stanford University), Shi Dong (Google DeepMind), Benjamin Van Roy (Stanford University)
分类: cs.LG stat.ML
发表会议: RLJ | RLC 2024
论文链接: https://arxiv.org/abs/2211.15931

摘要

本文提出了一种适用于持续性环境的后验采样强化学习算法(Continuing PSRL)，该算法能够自然地集成到可扩展的智能体设计中。算法维护一个统计上合理的环境模型，并遵循一个在该模型中最大化γ折扣回报的策略。在每个时间步，算法以概率1-γ从环境的后验分布中重新采样模型。通过适当选择依赖于时间范围T的折扣因子，建立了Õ(τS√AT)的贝叶斯后悔界，其中S是环境状态数，A是动作数，τ表示奖励平均时间。

研究背景与动机

核心问题

现有的后验采样强化学习算法主要针对分幕式(episodic)环境设计，依赖于维护状态-动作访问计数，这使得它们不适用于具有高维状态空间的复杂持续性环境。

问题重要性

持续性环境学习是强化学习中的基础问题，但现有的随机化探索方法主要局限于分幕式环境
可扩展性需求：传统方法依赖状态-动作访问计数，在复杂环境中不可行
理论空白：缺乏针对持续性环境的严格理论分析

现有方法局限性

TSDE (Ouyang et al., 2017)：需要复杂的重采样标准，包括访问计数翻倍条件，在大状态空间中不可行
DS-PSRL (Theocharous et al., 2018)：虽然避免了访问计数，但分析依赖于强技术假设，在没有这些假设时后悔界线性增长
传统PSRL：仅适用于分幕式环境，无法直接扩展到持续性设置

研究动机

提出一个简单、可扩展且理论上严格的持续性环境后验采样算法，能够：

避免维护状态-动作访问计数
自然集成到现有的函数逼近方法中
提供与现有最佳方法相匹配的理论保证

核心贡献

首个可扩展的持续性PSRL算法：提出了基于简单随机化方案的Continuing PSRL，避免了复杂的重采样标准
严格的理论分析：建立了Õ(τS√AT)的贝叶斯后悔界，匹配现有最佳结果
可扩展性突破：算法可以自然扩展到高维状态空间和函数逼近设置
折扣因子的新视角：将折扣因子视为算法设计工具而非环境属性，提供了理解折扣因子作用的新视角

方法详解

任务定义

考虑一个未知环境E = (A,S,ρ)建模的马尔可夫决策过程，其中：

A是有限动作空间，|A| = A
S是有限状态空间，|S| = S
ρ是状态转移概率函数
奖励函数r : S × A → 0,1是确定性的已知函数

目标是最小化累积后悔： $\text{Regret}(T,π) := \sum_{t=0}^{T-1}(λ_{*,E} - R_{t+1})$

其中λ_{*,E}是最优平均奖励。

模型架构

伪分幕构造

算法将无限时间范围学习问题分解为随机长度的伪分幕：

在每个时间步t，采样二进制指示器X_t
当X_t = 0时，开始新的伪分幕并重新采样环境模型
当X_t = 1时，继续当前伪分幕

折扣价值函数

对于环境E和策略π，γ折扣价值函数定义为： $V^γ_{π,E} := \mathbb{E}\left[\sum_{h=0}^{H-1} P^h_π r_π | E\right] = \mathbb{E}\left[\sum_{h=0}^{∞} γ^h P^h_π r_π | E\right]$

其中H是伪分幕长度，服从几何分布。

奖励平均时间

关键概念是奖励平均时间τ_{π,E}，定义为最小值τ使得： $\left|\mathbb{E}_π\left[\sum_{t=0}^{T-1} R_{t+1} | E, S_0 = s\right] - T \cdot λ_{π,E}(s)\right| \leq τ$

算法流程

Algorithm 1: Continuing PSRL

输入：先验分布f，折扣因子γ，总学习时间T
1. 初始化 t=1, k=1, X₁=0
2. for t ≤ T:
3.   if Xₜ = 0:
4.     tₖ ← t
5.     采样 Eₖ ~ f(·|H_tₖ)
6.     计算 πₖ = π^γ_Eₖ
7.     k ← k+1
8.   采样并执行 Aₜ ~ πₖ(·|Sₜ)
9.   观察 Rₜ₊₁ 和 Sₜ₊₁
10.  t ← t+1
11.  采样 Xₜ₊₁ ~ Bernoulli(γ)

技术创新点

简单重采样机制：仅使用伯努利随机数生成器，避免复杂的访问计数条件
折扣因子与重采样概率的联系：设定γ = 1-p，其中p是重采样概率
策略无关的重采样：重采样标准独立于策略，简化了分析
时变折扣因子：允许折扣因子随时间增长，实现次线性后悔

实验设置

数据集

表格式RiverSwim环境：
- 6个状态的链式结构
- 左端状态奖励0.005，右端状态奖励1.0
- 最优策略是始终向右游
连续特征RiverSwim环境：
- 类似结构但使用像素特征观察
- 特征映射：φ(s_t) = 1{x ≤ s_t} ∈ 0,1^N
- 测试函数逼近设置下的算法性能

评价指标

累积后悔(Cumulative Regret)
平均后悔随时间的变化

对比方法

TSDE (Ouyang et al., 2017)：基于访问计数的Thompson采样
DS-PSRL (Theocharous et al., 2018)：固定时间间隔的重采样方案
随机智能体：作为基线
DQN with ε-greedy：在连续特征环境中的对比

实现细节

先验分布：狄利克雷分布(转移)和正态-伽马分布(奖励)
超参数：伪计数n=1，α=1/S，μ=σ²=1
连续环境中使用Bootstrapped DQN，γ=0.99

实验结果

主要结果

表格式环境：
- Continuing PSRL与TSDE性能相当，尽管后者直接优化平均奖励
- 显著优于DS-PSRL
- 验证了理论预测的次线性后悔增长
连续特征环境：
- Bootstrapped DQN + 随机重采样实现次线性后悔
- 明显优于vanilla DQN with ε-greedy探索
- 证明了方法在复杂环境中的可扩展性