Jiahong 的个人博客

凡事预则立,不预则废


  • Home

  • Tags

  • Archives

  • Navigation

  • Search

Python——Ray-option函数讲解


整体说明

  • 在 Ray 框架中,.option() 是用于配置 Actor 或远程函数(Task) 运行时属性的方法,其参数主要围绕资源分配、调度策略、容错机制等核心功能
  • 注意事项
    • 所有参数均需符合 Ray 框架的预定义类型,传入未支持的参数会抛出错误
    • 不同 Ray 版本可能新增或调整参数,建议结合官方文档(对应版本)查阅细节
    • 这些参数仅用于配置运行时属性,自定义业务参数需通过 Actor 初始化或 Task 函数参数传递(见前文说明)

Actor 配置示例(Task 类似)

  • Actor 使用 .option() 函数的示例
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    @ray.remote
    class MyActor:
    pass

    # 配置 Actor 资源、名称和重启策略
    actor = MyActor.options(
    num_cpus=1,
    num_gpus=0.5,
    name="my_actor",
    max_restarts=2,
    runtime_env={"env_vars": {"LOG_LEVEL": "INFO"}}
    ).remote()

通用核心参数(Actor 和 Task 均支持)

  • num_cpus 参数(类型:int 或 float)
    • 指定运行该 Actor/Task 所需的 CPU 核心数(支持小数,如 0.5 表示半核)
    • 示例:MyActor.options(num_cpus=2).remote()
  • num_gpus 参数(类型:int 或 float)
    • 指定所需的 GPU 数量(需集群实际有 GPU 资源)
    • 示例:my_task.options(num_gpus=1).remote()
  • resources 参数(类型:dict(键为资源名称,值为数量))
    • 指定自定义资源需求(如特定硬件、加速器等)
    • 示例:options(resources={"custom_accelerator": 1})
  • runtime_env 参数(类型:dict)
    • 配置运行环境(如依赖库、环境变量、工作目录等),确保 Actor/Task 在一致的环境中运行
    • 示例:options(runtime_env={"pip": ["numpy==1.21.0"]})
  • name 参数(类型:str)
    • 为 Actor/Task 指定名称,用于日志追踪或通过名称查找 Actor(仅 Actor 有效)
    • 示例:MyActor.options(name="worker-1").remote()

Actor 专属参数(仅 Actor 支持)

  • max_restarts 参数(类型:int)
    • 指定 Actor 崩溃后的最大重启次数(默认 -1 表示无限重启,0 表示不重启)
    • 示例:options(max_restarts=3)
  • max_task_retries 参数(类型:int)
    • 指定 Actor 处理单个任务时的最大重试次数(任务失败后重试)
    • 示例:options(max_task_retries=2)
  • lifetime 参数(类型:str(可选值:"detached" 或 "non_detached"))
    • 设置 Actor 生命周期。"detached" 表示 Actor 可脱离创建它的进程独立存在(进程退出后不销毁)
    • 示例:options(lifetime="detached")
  • placement_group 参数(类型:PlacementGroup 实例)
    • 将 Actor 绑定到特定的 放置组(Placement Group),优化资源 locality(本地性)

Task 专属参数(仅远程函数支持)

  • retry_exceptions 参数(类型:bool 或 tuple)
    • 指定 Task 失败时是否重试,或仅对特定异常重试
    • 示例:options(retry_exceptions=(ConnectionError,))
  • num_returns 参数(类型:int)
    • 指定 Task 返回值的数量(默认 1,用于多返回值场景)
    • 示例:@ray.remote(num_returns=2) def f(): return 1, 2

其他实用参数

  • priority 参数(类型:int)
    • 设置 Task/Actor 任务的调度优先级(数值越高越优先,仅部分调度器支持)
  • memory 参数(类型:int)
    • 指定所需的内存量(字节),超过会被终止(需集群启用内存限制)
  • object_store_memory 参数(类型:int)
    • 指定 Task 可使用的对象存储内存量(字节)

附录:runtime_env 参数的详细说明

  • 在 Ray 框架中,runtime_env 是 option() 方法中用于配置 运行时环境 的核心参数
  • runtime_env 参数的作用是确保远程任务(Task)或 Actor 在分布式集群中运行时,拥有一致的依赖环境、配置和资源,解决“本地能跑,集群跑不通”的环境一致性问题
  • runtime_env 接收一个字典作为参数,支持多种环境配置项,覆盖依赖管理、环境变量、文件同步等核心场景:
  • 工作原理:当通过 option(runtime_env=...) 配置环境后,Ray 会在任务/Actor 启动前执行以下操作:
    • 1)在 提交任务的节点 上收集 runtime_env 定义的依赖、文件和配置
    • 2)将这些资源同步到 集群中的目标节点(通过 Ray 的对象存储或分布式文件系统)
    • 3)在目标节点上自动创建隔离的运行环境(如虚拟环境、Conda 环境),安装依赖并注入环境变量
    • 4)任务/Actor 在该隔离环境中启动,确保环境一致性

更多讨论

  • 在分布式计算中,集群节点的环境可能存在差异(如依赖库版本、环境变量、工作目录等)
  • runtime_env 通过预先定义环境配置,让 Ray 自动在所有执行任务的节点上同步这些配置,确保任务/Actor 在 完全一致的环境 中运行,避免因环境差异导致的错误(如“ModuleNotFoundError”“版本不兼容”等)
  • 适用场景
    • 确保所有 worker 节点使用相同版本的框架(如 PyTorch、TensorFlow)和依赖库
    • 同步本地自定义模块或配置文件到集群,避免手动在每个节点部署代码
    • 不同任务/Actor 可使用独立的依赖环境,避免版本冲突
  • 其他问题
    • 初次加载的性能开销:首次使用 runtime_env 时,同步依赖和文件可能需要时间(尤其是大文件或复杂依赖),后续任务会复用缓存
    • 确保输入路径可读:working_dir、wheel 等路径需确保提交节点和集群节点均可访问(本地路径需为集群共享存储路径,如 NFS)
    • 至少要提前安装 conda 等包:部分配置(如 conda)需集群节点预先安装 Conda,否则会失效

依赖库管理(确保三方库版本一致)

  • pip :指定需要安装的 Python 依赖包及版本,支持通过列表或 requirements.txt 路径配置,示例如下:

    1
    2
    3
    4
    5
    # 直接指定依赖
    runtime_env={"pip": ["numpy==1.24.3", "pandas==2.0.3"]}

    # 通过 requirements.txt 配置
    runtime_env={"pip": "requirements.txt"}
  • conda :指定 Conda 环境配置,支持通过 environment.yml 路径或字典定义环境,示例如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    # 通过 environment.yml 配置
    runtime_env={"conda": "environment.yml"}

    # 直接定义 Conda 环境
    runtime_env={
    "conda": {
    "dependencies": ["python=3.9", "numpy=1.24.3"]
    }
    }
  • wheel :指定本地 Wheel 包路径,用于安装自定义或私有库(需确保集群节点可访问路径),示例如下:

    1
    runtime_env={"wheel": "./my_custom_lib-0.1.0-py3-none-any.whl"}

环境变量与配置注入

  • env_vars :定义任务/Actor 运行时的环境变量,键值对形式传递,示例如下:

    1
    2
    3
    4
    5
    6
    runtime_env={
    "env_vars": {
    "LOG_LEVEL": "INFO", # 日志级别
    "DATA_PATH": "/data/training" # 数据路径
    }
    }
  • config :传递自定义配置字典,可在任务/Actor 中通过 ray.get_runtime_context().runtime_env.get("config") 获取,用于业务参数传递,示例如下:

    1
    runtime_env={"config": {"batch_size": 32, "epochs": 10}}

文件与目录同步(确保资源可访问)

  • working_dir :指定工作目录,Ray 会将该目录下的所有文件同步到执行任务的节点,确保代码、配置文件等资源可访问。支持本地路径或 Git 仓库 URL,示例如下:

    1
    2
    3
    4
    5
    # 同步本地目录
    runtime_env={"working_dir": "./my_project"}

    # 同步 Git 仓库(支持分支/标签)
    runtime_env={"working_dir": "https://github.com/my_repo.git#branch=main"}
  • excludes :配合 working_dir 使用,指定同步时需要排除的文件/目录(如日志、缓存文件),避免冗余同步,示例如下:

    1
    2
    3
    4
    runtime_env={
    "working_dir": "./my_project",
    "excludes": ["*.log", "venv/", "data/*"] # 排除日志、虚拟环境和数据目录
    }

其他高级配置

  • py_modules :指定需要导入的自定义 Python 模块路径,支持将本地模块添加到 Python 路径(sys.path),示例如下:

    1
    runtime_env={"py_modules": ["./my_utils"]}  # 同步 my_utils 模块并添加到路径
  • env :指定预定义的环境名称(如 Ray 集群中已配置的共享环境),避免重复配置,示例如下:

    1
    runtime_env={"env": "shared-training-env"}  # 使用集群中预定义的环境

附录:option 中使用 runtime_env 和 启动参数传入 yaml 文件的区别

  • 在 Ray 中,可以使用 ray job submit 命令提交任务到已经启动的 Ray 集群中
  • ray job submit 命令的 --runtime-env 参数也可以通过传入 yaml 文件(或 JSON 格式的字符串)指定 runtime-env 参数
  • 至此,我们有了两种指定方式:
    • 在代码中通过 option 函数(如 @ray.remote 的 runtime_env 参数)指定运行时环境
    • 在 ray job submit 命令中通过 --runtime-env 参数传入 yaml 文件指定运行时环境
  • 两者的生效级别不同:
    • --runtime-env=./runtime_env.yaml 是 全局级别的配置 ,会为整个 Ray Job 中的所有任务(包括所有 Actor、任务函数)设置默认的运行时环境
      • 适用于需要为整个作业统一配置环境的场景(如统一的工作目录、环境变量等)
    • 代码中 option 函数指定(如 @ray.remote(runtime_env=...))是局部级别的配置 ,仅对当前修饰的 Actor 或任务生效
      • 适用于为特定任务/Actor 单独设置差异化环境的场景(如某个任务需要额外的依赖包,而其他任务不需要)
  • 两者的优先级不同:
    • 局部配置(代码中 option 函数)的优先级高于全局配置(命令行 --runtime-env)
    • 当两者配置不冲突时,会进行合并(例如全局配置了 env_vars,局部配置了 pip,最终环境会同时包含这两者)
    • 当两者配置冲突时(如同一环境变量在两处被设置为不同值),局部配置会覆盖全局配置

Math——因果推断

本文介绍因果推断(Causal Inference)相关概念


参考资料

  • 讲的比较好的入门材料:
    • 参考链接:闲聊因果效应(1):当我们聊因果时,我们在聊什么
    • 参考链接:闲聊因果效应(2): 理解因果效应的计算以及PSM、IPW
  • 阿里发的一篇论文,用神经网络实现的二分类Uplift模型:
    • 参考链接:KDD‘22 阿里|DESCN: Deep Entire Space Cross Networks | 多任务、端到端、IPW的共舞

什么时候需要因果推断?

  • 是否需要因果推断主要取决于是否存在混淆因素/混淆因子(Confounders) ,即 treatment 是否是足够随机的(不受其他因素影响)
    • 如果 treatment 是完全随机分配的(即在每个状态下,treatment 是随机决定的),那么观察到的影响差异可以直接归因于 treatment 的变化,此时相关性即因果性 ,理论上不需要复杂的因果推断方法

有“足够多随机数据”时是否需要因果推断?

  • 若“随机”指完全随机实验 :不需要因果推断,直接建模即可
  • 若“随机”仅指数据量大 :仍需因果推断,因为数据量不能解决混淆偏差问题

出价中是否需要因果推断?

  • 如果出价是随机分配的 ,则可以直接用统计模型直接拟合 收益 = f(状态,出价),无需因果推断,因为随机化已消除混淆偏差
  • 如果出价是策略性选择的(如历史数据中出价高低与状态相关),则存在混淆偏差(confounding),必须用因果推断方法(如双重机器学习、倾向得分匹配)来估计条件平均处理效应(CATE)
    • 例如:高收益场景下系统更倾向出高价,此时出价与收益的关联可能混入了状态的影响

因果推断中的一致性假设

  • 一致性假设指的是:对于某一研究对象,其接受的处理(Treatment)与潜在结果(Potential Outcome)之间存在唯一且明确的对应关系
    • 具体来说,若个体 \(i\) 接受了处理 \(Z_i = z\),那么该个体的观测结果 \(Y_i\) 必然等于其在处理 \(z\) 下的潜在结果 \(Y_i(z)\),即:
      $$Y_i = Y_i(Z_i)$$

一致性假设的作用

  • 在因果推断中,我们通常需要比较同一主体在不同处理下的潜在结果差异(如因果效应 \(Y_i(1) - Y_i(0)\)),但现实中个体只能接受一种处理,无法同时观测到两种结果。一致性假设确保了:
    • 当个体接受处理 \(Z=1\) 时,观测结果 \(Y_i\) 等于其潜在结果 \(Y_i(1)\);
    • 当个体接受处理 \(Z=0\) 时,观测结果 \(Y_i\) 等于其潜在结果 \(Y_i(0)\)
  • 如此一来,我们才能通过分组(如处理组和对照组)的观测结果差异,来推断处理的因果效应(如平均因果效应 \(E[Y(1) - Y(0)]\))

目前因果推断的SOTA模型

  • CFR:Estimating individual treatment effect: generalization bounds and algorithms

Math——拟合优度


整体说明

  • 拟合优度(Goodness of Fit)是指所建立的模型对实际观测值的拟合程度
  • 在回归分析中,它衡量了自变量对因变量的解释程度,拟合优度越大,说明拟合越好
    • 拟合越好,意味着:自变量引起的变异占总变异的百分比越高,观察点在回归直线附近越密集

拟合优度的度量:决定系数 \(R^{2}\)

  • 度量拟合优度的常用统计量是决定系数(coefficient of determination) ,一般记作 \(R^{2}\)
  • \(R^{2}\) 的计算公式为:
    $$R^{2}=\frac{SSR}{SST}=1 - \frac{SSE}{SST}$$
    • \(SSR\) 为回归平方和
    • \(SSE\) 为残差平方和
    • \(SST\) 为总离差平方和
    • 注:\(SST = SSR + SSE\)
  • 若用 \(y_{i}\) 表示真实的观测值, \(\bar{y}\) 表示真实观测值的平均值, \(\hat{y}_{i}\) 表示拟合值,则 \(SSR\) 、 \(SSE\) 、 \(SST\) 的具体计算公式如下:
    • 总平方和 \(SST=\sum_{i = 1}^{n}(y_{i}-\bar{y})^{2}\)
    • 回归平方和 \(SSR=\sum_{i = 1}^{n}(\hat{y}_{i}-\bar{y})^{2}\)
    • 残差平方和 \(SSE=\sum_{i = 1}^{n}(y_{i}-\hat{y}_{i})^{2}\)

Math——最优化问题和KKT条件

凸优化&拉个朗日对偶性的直观理解


凸优化相关书籍

  • 参考链接:优化方法-资料集合

问题定义

  • 一般优化问题的定义:

$$
\begin{align}
\min_{x}\quad &f(x) \\
s.t. \quad &g_{i}(x) \leq 0, i = 1,2,\dots,k \\
&h_{j}(x) = 0, j = 1,2,\dots,l
\end{align}
$$

凸优化问题

  • 如果原始优化问题满足:
    • \(f(x)\) 和 \(g_{i}(x)\) 都是 \(\mathbb{R}^{n}\) 上连续可微的凸函数
    • \(h_{j}(x)\) 为 \(\mathbb{R}^{n}\) 上的仿射函数 (仿射函数是满足 \(h_{j}(x) = a\cdot x + b\) 的函数)
  • 那么,原始优化问题是凸优化问题

凸二次优化问题

  • 若上述凸优化问题还满足:
    • \(f(x)\) 是二次函数
    • \(g_{i}(x)\) 是 \(\mathbb{R}^{n}\) 上的仿射函数
  • 那么,原始优化问题是凸二次优化问题

朗格朗日对偶性

拉格朗日对偶性的推导
  • 原始问题定义为

$$
\begin{align}
\min_{x}\quad &f(x) \\
s.t. \quad &g_{i}(x) \leq 0, i = 1,2,\dots,k \\
&h_{j}(x) = 0, j = 1,2,\dots,l
\end{align}
$$

  • 引进拉格朗日函数有
    $$
    \begin{align}
    L(x,\alpha, \beta) = f(x) + \sum_{i=1}^{k}\alpha_{i}g_{i}(x) + \sum_{j=1}^{l}\beta_{j}h_{j}(x)
    \end{align}
    $$

  • 考虑到
    $$
    \begin{align}
    \max_{\alpha,\beta:\alpha_{i}\geq 0}L(x,\alpha, \beta)
    \end{align}
    $$

    • 当 \(x\) 满足原始问题的解时,上面的式子等价与 \(f(x)\)
    • 否则上面的式子等于无穷大 \(+\infty\)
  • 所以假设原始问题的最优值为 \(p^{\star}\),那么
    $$
    \begin{align}
    p^{\star} = \min_{x}\max_{\alpha,\beta:\alpha_{i}\geq 0}L(x,\alpha, \beta)
    \end{align}
    $$

    • (\(p^{\star}\) 不是最优参数,是最优参数对应的函数值,参数应该用 \(\mathop{\arg\max}_{x}\) 而不是 \(\max_{x}\))
  • 定义对偶问题为:
    $$
    \begin{align}
    &\max_{\alpha,\beta:\alpha_{i}\geq 0}\min_{x}L(x,\alpha, \beta) \\
    &s.t.\quad \alpha_{i} \geq 0,\quad i=1,2,\dots,k
    \end{align}
    $$

  • 假设原始问题的最优解为 \(d^{\star}\),则原始问题与对偶问题的关系为:
    $$
    \begin{align}
    d^{\star} = \max_{\alpha,\beta:\alpha_{i}\geq 0}\min_{x}L(x,\alpha, \beta) = \min_{x}\max_{\alpha,\beta:\alpha_{i}\geq 0}L(x,\alpha, \beta) = p^{\star}
    \end{align}
    $$

KKT条件
  1. 原始可行性 : \(g_{i}(x) \leq 0\), \(h_{j}(x) = 0\)
    • 所有原始约束必须满足
  2. 对偶可行性 : \(\alpha_i \geq 0\)
    • 所有的不等式约束对应的拉格朗日乘子大于等于0
  3. 互补松弛性 : \(\alpha_i g_i(x) = 0\)
    • 对于每个不等式约束 \(g_i(x)\),都有 \(\alpha_i g_i(x) = 0\),这意味着如果一个约束是紧约束(即 \(g_i(x) = 0\) ),那么对应的 \(\alpha_i\) 可以是非零的;如果一个约束是松的(即 \(g_i(x) < 0\) ),那么对应的 \(\alpha_i\) 必须为零
  4. 梯度条件 : \(\nabla_x L(x^, \alpha^, \beta^*) = 0\)
    • 在最优解处,拉格朗日函数关于 \(x\) 的梯度必须为零
  • 其他理解:
    • 对KKT条件其他角度的理解可参考周志华<<机器学习>>P404

Math——相关性指标


PLCC (Pearson Linear Correlation Coefficient)

  • 皮尔逊线性相关系数主要用于衡量预测值与真实值之间的线性相关程度
  • PLCC 反映了预测结果在数值上的准确性
    $$ PLCC = \frac{\sum_{i=1}^{n} (x_i - \bar{x})(y_i - \bar{y})}{\sqrt{\sum_{i=1}^{n} (x_i - \bar{x})^2} \sqrt{\sum_{i=1}^{n} (y_i - \bar{y})^2} } $$
    • \(x_i\) 是第 \(i\) 个样本的预测值
    • \(y_i\) 是第 \(i\) 个样本的真实值(如 MOS 分数)
    • \(\bar{x}\) 和 \(\bar{y}\) 分别是预测值和真实值的平均值
  • PLCC 的特点:
    • 对数值大小敏感
    • 要求数据呈正态分布或接近正态分布效果最好
    • 在计算前,通常需要对预测值进行非线性回归(如 Logistic 映射),以消除模型输出范围与 MOS 分数范围不一致的影响
  • 取值范围:[-1, 1]
    • 1 :完全正线性相关
    • 0 :无线性相关
    • -1 :完全负线性相关
  • 一般在 打分、评估、质量预测、对比两个分数 的场景里:
    • 0.9 ~ 1.0 :极强线性相关
    • 0.7 ~ 0.9 :强线性相关
    • 0.5 ~ 0.7 :中等线性相关
    • 0.3 ~ 0.5 :弱线性相关
    • < 0.3 :几乎无线性相关

SROCC (Spearman Rank-Order Correlation Coefficient)

  • 斯皮尔曼等级相关系数主要用于衡量预测值与真实值之间的单调性相关程度
  • SROCC 只关注数据的相对排序,而不关注具体的数值差异
    $$ SROCC = 1 - \frac{6 \sum_{i=1}^{n} d_i^2}{n(n^2 - 1)} $$
    • \(d_i = rank(x_i) - rank(y_i)\) 是第 \(i\) 个样本的预测值排名与真实值排名之差
    • \(n\) 是样本数量
  • 特点
    • 非参数指标,不要求数据分布
    • 对异常值(Outliers)更具鲁棒性
    • 只要预测值随真实值单调递增,SROCC 就会接近 1,即便它们之间不是线性关系
  • 取值范围:[-1, 1]
    • 1 :完全单调正相关
    • 0 :无单调相关
    • -1 :完全单调负相关
  • 一般分数含义:
    • 0.8 ~ 1.0 :极强单调相关
    • 0.6 ~ 0.8 :强单调相关
    • 0.4 ~ 0.6 :中等单调相关
    • 0.2 ~ 0.4 :弱单调相关
    • < 0.2 :几乎无单调相关

KROCC (Kendall Rank Correlation Coefficient)

  • 肯德尔等级相关系数 主要用于衡量预测值与真实值之间 排序的一致性程度
  • KROCC 基于成对样本的顺序一致性来度量相关性,关注的是变量之间的序数关联而非数值线性关系
    $$
    KROCC = \frac{n_c - n_d}{\sqrt{(n_0 - n_1)(n_0 - n_2)} }
    $$
    • \(n_c\) 为一致对数量:预测值与真实值相对顺序相同的样本对
    • \(n_d\) 为不一致对数量:预测值与真实值相对顺序相反的样本对
    • \(n_0 = \frac{n(n-1)}{2}\) 为总样本对数量
    • \(n_1\)、\(n_2\) 分别为预测值与真实值中存在并列秩的修正项
    • \(n\) 为样本总数
  • 特点:
    • 非参数指标,不依赖数据分布
    • 对异常值不敏感 ,鲁棒性强
    • 更适合小样本、存在并列排名的场景
    • 相比 SROCC,KROCC 对局部排序错误更敏感,解释更直观
  • 取值范围:[-1, 1]
    • 1 :预测值与真实值完全一致排序
    • 0 :随机无序 ,无等级相关
    • -1 :完全相反排序
  • 在质量评估、打分预测、偏好排序等场景中:
    • ≥ 0.60 :极强等级相关
    • 0.40 ~ 0.60 :强等级相关
    • 0.20 ~ 0.40 :中等等级相关
    • 0.10 ~ 0.20 :弱等级相关
    • < 0.10 :几乎无等级相关

附录:SROCC vs PLCC 核心差异对比

  • PLCC 和 SROCC 分别从不同的维度衡量预测值与真实值(Ground Truth)之间的相关性
    • 通常一个优秀的模型应该在两个指标上都接近 1
  • 对比表格:
    特性 PLCC SROCC
    衡量目标 线性相关性 (Linearity) 单调相关性 (Monotonicity)
    计算基础 原始数值 (Raw Values) 排名/等级 (Ranks)
    对异常值敏感度 高(异常值会显著拉低分数) 低(排名变化较小)
    数据分布要求 通常要求正态分布 无要求(非参数统计)
    应用场景 衡量预测精度(数值准不准) 衡量排序能力(好坏顺序对不对)

Math——范数和谱范数


范数的定义

  • 在数学中,范数 (Norm) 是一个函数,它将向量空间中的每个非零向量映射为一个正实数 ,直观上可以理解为向量的“长度”或“大小”
    • 注:常规聊的范数都是针对向量空间的,谱范数(Spectral Norm) 是针对矩阵空间的
  • 对于零向量,范数映射为零
  • 范数需要满足以下三个性质:
    • 1)非负性 (Non-negativity) :对于所有向量 \( x \),有\(|x| \ge 0\),且当且仅当 \(x = 0\) 时,\(|x| = 0\)
    • 2)齐次性 (Homogeneity) :对于所有标量 \( \alpha \) 和向量 \( x \),有 \(|\alpha x| = |\alpha| |x|\)
    • 3)三角不等式 (Triangle Inequality) :对于所有向量 \( x \) 和 \(y\),有 \(|x + y| \le |x| + |y|\)

常见的范数——\(L_p\) 范数

  • \(L_p\) 范数,也称为 Minkowski 范数,定义为:
    $$|x|_p = \left( \sum_{i=1}^n |x_i|^p \right)^{\frac{1}{p} }$$
    • \(x = [x_1, x_2, \dots, x_n]^T\) 是一个 \(n\) 维向量
    • \(p \ge 1\) 是一个实数

\(L_1\) 范数 (Manhattan Norm / Taxicab Norm)

  • 当 \(p=1\) 时,称为 \(L_1\) 范数,表示向量中所有元素的绝对值之和
  • \(L_1\) 范数衡量的是向量元素到原点的曼哈顿距离
    $$|x|_1 = \sum_{i=1}^n |x_i|$$
  • 在机器学习中,常用于稀疏表示和特征选择(如 Lasso 回归),因为它倾向于产生稀疏解

\(L_2\) 范数 (Euclidean Norm)

  • 当 \(p=2\) 时,称为 \(L_2\) 范数,表示向量的欧几里得长度,即从原点到向量的欧几里得距离
    $$|x|_2 = \sqrt{\sum_{i=1}^n |x_i|^2}$$
  • \(L_2\) 范数是最常见的范数,广泛应用于各种领域,如机器学习中的岭回归 (Ridge Regression)、深度学习中的权重衰减 (Weight Decay) 以及距离计算

\(L_\infty\) 范数 (Maximum Norm / Chebyshev Norm)

  • 当 \(p \to \infty\) 时,称为 \(L_\infty\) 范数,表示向量中所有元素的绝对值的最大值
    $$|x|_\infty = \max_{i} |x_i|$$
  • 在一些优化问题中,当需要限制向量中最大分量的大小时会使用到

矩阵范数

  • 矩阵范数是定义在矩阵空间上的范数,除了满足向量范数的三个性质外,对于矩阵乘法还需满足:
    $$
    |AB| \leq |A| |B|
    $$

诱导范数(算子范数)

  • 对于矩阵 \( A \in \mathbb{C}^{m \times n} \),由向量范数 \( |\cdot|_p \) 诱导的矩阵范数定义为:
    $$
    |A|_p = \sup_{x \neq 0} \frac{|Ax|_p}{|x|_p} = \sup_{|x|_p=1} |Ax|_p
    $$
  • 特殊情况下,有以下范数:
    • 1)列和范数(诱导自 \(L_1\) 范数) :
      $$
      |A|_1 = \max_{1 \leq j \leq n} \sum_{i=1}^m |a_{ij}|
      $$
      • 按列求和,再取最大者
    • 2)谱范数(诱导自 \(L_2\) 范数) :
      $$
      |A|_2 = \sqrt{\lambda_{\max}(A^* A)}
      $$
      • 其中 \( \lambda_{\max} \) 表示最大特征值,\( A^* \) 是 \( A \) 的共轭转置
    • 3)行和范数(诱导自 \(L_\infty\) 范数) :
      $$
      |A|_\infty = \max_{1 \leq i \leq m} \sum_{j=1}^n |a_{ij}|
      $$
      • 按行求和,再取最大者

常用的矩阵范数——谱范数

  • 谱范数(Spectral Norm) 是矩阵范数的一种,它通常特指矩阵的 \(L_2\) 范数,即诱导 \(L_2\) 范数
  • 谱范数是矩阵分析中最重要的范数之一,具有许多优良性质

谱范数定义

  • 对于矩阵 \( A \in \mathbb{C}^{m \times n} \),其谱范数定义为:
    $$
    |A|_2 = \sup_{x \neq 0} \frac{|Ax|_2}{|x|_2} = \sigma_{\max}(A)
    $$
    • 其中 \( \sigma_{\max}(A) \) 是 \( A \) 的最大奇异值
  • 谱范数的更容易理解的另一个形式为:
    $$|A|_2 = \max_{x \ne 0} \frac{|Ax|_2}{|x|_2}$$
    • 这个定义表明,谱范数是矩阵 \(A\) 对向量 \(x\) 进行线性变换后 ,最大可能的“放大倍数”
    • 换句话说,它衡量了矩阵 \(A\) 在将单位向量 \(x\) 映射到 \(Ax\) 时,所能达到的最大长度

谱范数计算方法

  • 1) 计算 \( A^* A \)(实矩阵时计算 \( A^T A \) 即可)
    • 注:\( A^* \) 是共轭转置 ,对于实矩阵为普通转置 \( A^T\)
  • 2) 求 \( A^* A \) 的最大特征值 \( \lambda_{\max} \)
  • 3) 谱范数为 \( \sqrt{\lambda_{\max} } \)

谱范数性质

  • 1) 次乘性 :\( |AB|_2 \leq |A|_2 |B|_2 \)
  • 2) 酉不变性 :对于任意酉矩阵 \( U \) 和 \( V \),有 \( |UAV|_2 = |A|_2 \)
    • 注:酉矩阵(Unitary Matrix)的共轭转置(即 Hermitian 转置)等于其逆矩阵:
      $$ U^*U = UU^* = I$$
  • 3) 与Frobenius范数的关系 :\( |A|_2 \leq |A|_F \leq \sqrt{\operatorname{rank}(A)} |A|_2 \)
  • 4) 与特征值的关系 :对于正规矩阵,谱范数等于谱半径 \( \rho(A) = \max |\lambda_i| \)

谱范数的应用

  • 矩阵近似 :在低秩近似中,谱范数度量了近似误差

附录:谱范数与奇异值

  • 谱范数有一个非常重要的性质,它等于矩阵 \(A\) 的最大奇异值
  • 矩阵 \(A\) 的奇异值是其正定半定矩阵 \(A^T A\)(或 \(A A^T\))的特征值的平方根
  • 令 \(\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0\) 为矩阵 \(A\) 的非零奇异值,其中 \(r = \text{rank}(A)\)。那么,谱范数可以表示为:
    $$|A|_2 = \sigma_{\max}(A) = \sqrt{\lambda_{\max}(A^T A)}$$
    • \(\sigma_{\max}(A)\) 表示矩阵 \(A\) 的最大奇异值
    • \(\lambda_{\max}(A^T A)\) 表示矩阵 \(A^T A\) 的最大特征值
  • 推导简述 :
    • 考虑 \(A^T A\) 是一个对称半正定矩阵,它的特征值都是非负的
    • 对于任意非零向量 \(x\),我们有:
      $$\frac{|Ax|_2^2}{|x|_2^2} = \frac{(Ax)^T (Ax)}{x^T x} = \frac{x^T A^T A x}{x^T x}$$
    • 根据瑞利商 (Rayleigh Quotient) 的性质,\(\max_{x \ne 0} \frac{x^T M x}{x^T x} = \lambda_{\max}(M)\),其中 \(M\) 是对称矩阵
    • 因此:
      $$\max_{x \ne 0} \frac{|Ax|_2^2}{|x|_2^2} = \lambda_{\max}(A^T A)$$
    • 取平方根后即可得到 \(|A|_2 = \sqrt{\lambda_{\max}(A^T A)} = \sigma_{\max}(A)\)
  • 谱范数用于正则化 :在机器学习中,谱范数可以用于限制模型的复杂度,例如在深度学习中,限制神经网络层的权重矩阵的谱范数可以帮助防止过拟合

附录:共轭转置

  • 共轭转置(Conjugate Transpose),也称为Hermitian转置 ,是线性代数中对矩阵的一种操作,记作 \( A^* \)、\( A^H \) 或 \( A^\dagger \)
  • 共轭转置 对矩阵 \( A \) 进行以下两步运算:
    • 1) 共轭 :将矩阵 \( A \) 的每个元素取复共轭(即实部不变,虚部取反)
    • 2) 转置 :将矩阵的行列互换(即第 \( i \) 行第 \( j \) 列元素变为第 \( j \) 行第 \( i \) 列)

与普通转置对比

  • 普通转置(\( A^T \)) :仅行列互换,不取共轭
  • 实矩阵的共轭转置 :退化为普通转置(因虚部为零)

附录:Schatten-\( p \) 范数是什么?

  • Schatten-\( p \) 范数(Schatten-\( p \) norm)是矩阵空间中一类重要的范数,常用于描述矩阵的“大小”或“强度”
  • Schatten-\( p \) 范数 基于矩阵的奇异值(singular values)定义,适用于更广泛的矩阵分析场景(如紧算子、核范数等)

Schatten-\( p \) 范数的定义

  • 设矩阵 \( A \in \mathbb{C}^{m \times n} \) 的奇异值为 \( \sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0 \)(其中 \( r = \min(m, n) \)),则其 Schatten-\( p \) 范数定义为:
    $$
    |A|_{S_p} = \left( \sum_{i=1}^r \sigma_i^p \right)^{1/p}, \quad p \in [1, \infty).
    $$

Schatten-\( p \) 范数的特例

  • 1) \( p = 1 \)(核范数,Nuclear norm)
    $$ |A|_{S_1} = \sum_{i=1}^r \sigma_i $$
    • 用于矩阵低秩恢复、压缩感知等
  • 2) \( p = 2 \)(Frobenius 范数,也称 F 范数)
    $$ |A|_{S_2} = \left( \sum_{i=1}^r \sigma_i^2 \right)^{1/2} = \sqrt{\text{tr}(A^* A)} $$
    • 即矩阵元素的平方和开根号
  • 3) \( p = \infty \)(谱范数,Spectral norm)
    $$ |A|_{S_\infty} = \sigma_1 $$
    • 等于矩阵的最大奇异值,也是算子范数的一种

附录:Frobenius 范数的更多说明

  • Frobenius范数(F 范数)是矩阵的一种常用范数,用于衡量矩阵的“大小”
  • 它将矩阵视为一个向量,计算其所有元素的平方和的平方根
  • 对于一个 \( m \times n \) 的矩阵 \( A = (a_{ij}) \),其Frobenius范数定义为:
    $$
    |A|_F = \sqrt{\sum_{i=1}^{m} \sum_{j=1}^{n} |a_{ij}|^2}
    $$
    • 等价于矩阵所有元素的平方和再开平方
    • 在 PyTorch 中的实现为 A.norm()

RL——AlphaGo系列算法


AlphaGo整体说明

  • AlphaGo是强化学习的阶段性集大成者,其核心思想值得细细推敲

AlphaGo棋局介绍

  • AlphaGo 的目标是解决围棋对弈问题 ,即在标准的 19×19 围棋棋盘上(共381维),通过观察棋盘情况选择最优的落子动作,击败对手
  • 输入 :当前棋盘状态(包括棋子分布和历史信息)
  • 输出 :下一步落子的最优位置(或概率分布)
  • 挑战 :
    • 围棋的状态空间复杂度高达 \(3^{361}\)(约\(10^{172}\)量级),无法暴力搜索
    • 围棋的决策步长约100+步,决策需要结合长期策略收益
    • 围棋的评估函数难以设计(难以量化当前局面是否有“局面优势”)

ALphaGo问题建模

  • 状态空间:\(19 \times 19 \times N\),这里的N在不同版本不一样,比如17=16+1时,16是用于记录最近 8 步的状态(相当于记录了窗口),1则表示该哪一方下棋,其他还有一些需要理解围棋规则才能解释
  • 动作空间:离散动作空间,362个动作可选(361位置 + 1 Pass)
  • 奖励函数:对局结束时,胜利方奖励+1,失败方-1,平局为0(围棋通常无平局)

AlphaGo 训练过程(分三个阶段)

第一阶段:行为克隆(监督学习模仿人类专家)

  • 基于 KGS 围棋平台上的 3000 万局人类对弈棋谱,学习人类专家的落子的模式
  • 通过监督学习训练一个策略网络(Policy Network) ,输入棋盘状态,输出人类选手的落子概率分布
    • 网络结构:13 层卷积神经网络(CNN)
    • 准确率:57%(预测人类下一步动作)

第二阶段:强化学习(自我对弈优化,策略梯度优化)

  • 通过策略梯度法,进一步优化策略网络,超越人类水平
    • 自我对弈 :使用初始策略网络生成大量自我对局数据
    • 策略梯度 :通过胜负结果优化策略网络(即强化学习策略网络),使其更倾向于获胜的走法
    • 回报函数 :对局结束时获胜方获得 +1 奖励,失败方获得 -1

第三阶段:价值网络学习(局面评估)

  • 价值网络学习阶段的目标是训练一个价值网络(Value Network) ,预测当前局面的胜率(替代蒙特卡洛rollout的耗时评估)
  • 通过自我对弈生成 3000 万组棋盘状态及最终胜负结果,学习一个标量值(-1 到 +1),表示当前玩家获胜的概率

AlphaGo 决策过程

  • AlphaGo 的实时决策基于蒙特卡洛树搜索(MCTS) ,结合神经网络的输出:
  • 选择(Selection) :从根节点(当前棋盘状态)出发,通过树策略(如UCT算法)选择子节点,平衡探索与利用,使用策略网络优先选择高概率的落子分支
  • 扩展(Expansion) :当遇到未探索的节点时,用策略网络生成可能的落子概率,扩展树结构
  • Evaluation 对价值网络评估胜率,和策略网络模拟rollout到终局得到的奖励两者做加权结合
  • 回溯(Backup) :将叶子节点的评估结果反向传播更新路径上的节点统计量(访问次数、平均胜率)
  • 最终决策(Decision) :搜索结束后,选择访问次数最多的节点对应的落子动作

AlphaGo 相关思考

  • 以模仿学习作为强化学习策略的冷启动是个不错的想法
  • 使用MCTS来决策有助于提升模型决策能力,在MCTS下,随着围棋的进行,搜索空间变小,AlphaGo相对人类的优势会越来越明显

附录:AlphaGo 的迭代版本

版本 发版时间 训练数据 核心算法 计算需求 棋力提升
AlphaGo Fan 2015年10月 人类棋谱(监督学习) SL + MCTS 中等(分布式计算) 首次击败职业棋手(樊麾)
AlphaGo Lee 2016年3月 人类棋谱 + 自我对弈 SL + RL + MCTS + 价值网络 高(1202 CPU + 176 GPU) 超越人类顶尖(李世石)
AlphaGo Master 2017年1月(Master)
2017年5月(正式对战柯洁)
纯自我对弈 纯RL + 深度网络 低(单机) 完胜人类第一柯洁
AlphaGo Zero 2017年10月 从零开始自我对弈 纯RL + ResNet + MCTS 极低(4 TPU) 100:0击败AlphaGo Lee
AlphaZero 2017年12月 多棋类自我对弈 通用RL + 高效搜索 低(单机) 8小时超越AlphaGo Zero

RL——BCQ

  • 参考链接:【笔记】BCQ详解
    • 原作者的PPT
  • 参考链接:BCQ姊妹篇:Discrete BCQ - Metaqiang的文章 - 知乎
  • 参考链接:【代码速读】(RL)1.BCQ - 一条的文章 - 知乎

BCQ 整体介绍

  • BCQ(Batch-Constrained deep Q-learning)分为连续版本(Off-Policy Deep Reinforcement Learning without Exploration,2019年8月)和离散版本(Benchmarking Batch Deep Reinforcement Learning Algorithms,2019年10月)两篇文章,一作是同一个作者
  • 外推误差(Extrapolation Error)的定义:off-policy值学习中,当前策略真实状态动作访问分布和数据集中的状态动作分布不匹配导致的一种误差

    Extrapolation error is an error in off-policy value learning which is introduced by the mismatch between the dataset and true state-action visitation of the current policy

  • 背景:off-policy的策略理论上可以从任意行为策略采样的数据中学习最优策略,但是直接将off-policy策略应用到Offline RL(也称为Batch RL)场景中可能面临,Absent Data(状态动作对缺失),Training Mismatch(训练预测分布不一致),Model Bias(随机MDP的状态转移概率有偏差)等问题
  • BCQ的基本思想:采取保守策略,让学到的策略对应的状态动作访问空间尽量只在出现过的数据集上,或者相近的数据上
    • 基本方法:主要通过限制 \(Q(s’,\pi(s’))\) 中的 \(\pi(s’)\) 不要偏离数据集太多来实现

BCQ 连续版本

关键实验

  • 实验设置:

    • 第一个实验(Final Buffer),使用DDPG算法在线训练一个智能体,将智能体训练过程中与环境交互的所有数据保存下来,利用这些数据训练另一个离线DDPG智能体
    • 第二个实验(Concurrent),使用DDPG算法在线训练一个智能体,训练时每次从经验回放池中采样,并用相同的数据同步训练离线DDPG智能体,甚至保持训练时使用的数据和数据顺序都完全相同
    • 第三个实验(Imitation),使用DDPG算法在线训练一个智能体,将该智能体作为专家,与环境交互采集大量数据,利用这些数据训练另一个离线DDPG智能体
  • 实验结果:

    • 第三个实验中使用的样本最好,但是训练得到的离线智能体效果最差,原因分析主要是外推误差导致
    • 三个实验的离线DDPG智能体都有不同情况的Q值高估问题,其中第三个实验的Q值高估问题最为严重(注意图2中看起来高估问题大于图1中,其实不是,是因为图二的量纲较小导致的)

理论推导

  • 对于给定的真实MDP和数据集 \(\mathcal{B}\),定义外推误差
    $$\epsilon_\text{MDP}(s,a) = Q^\pi(s,a) - Q_{\mathcal{B}}^\pi(s,a)$$
  • 则有外推误差可推导得到如下结论:

训练流程

  • 整体流程概览:

  • 训练流程解释:

    • 训练时,使用4个Q网络(其中两个是Target Q网络),1个策略网络和扰动网络
    • 两个Q网络的用途是在计算Q值目标时做他们最大最小值的凸组合(实际上就是最大最小值的加权平均),类似Twin Q中取两个Q的最小值的方法, \(y\) 值计算方法(流程中 \(\color{red}{\text{公式(13)}}\) )
      $$ y = r + \gamma \max_{a_i}\Big[ \lambda \min_{j=1,2}Q_{\theta_j}(s’,a_i) + (1-\lambda)\max_{j=1,2}Q_{\theta_j}(s’,a_i) \Big] $$

Serving步骤

  • 给定一个状态 \(s\)
  • \(\{ a_i \sim G_w(s) \}_{i=1}^n\):通过conditional VAE网络 \(G_w(s)\) 采样 \(n\) 个动作
  • \(\xi_{\phi}(s,a_i,\Phi)\):将这些状态和动作经过扰动网络,扰动网络输出是在 \([-\Phi,\Phi]\) 内的,得到的扰动值
  • 将扰动添加到原始动作上,再将动作经过Q网络,选取能使Q value最大的动作
  • 最终总结如下:
    $$ \pi(s) = \mathop{\arg\max}_{a_i + \xi_{\phi}(s,a_i,\Phi)} Q_\theta(s, a_i + \xi_{\phi}(s,a_i,\Phi)), \quad with \quad \{ a_i \sim G_w(s) \}_{i=1}^n $$
  • 训练流程解释:
    • 相对普通的DQN,主要改进点在于学习Q的目标值选择时动作受到限制,动作与行为策略(离线数据集)的动作差异不能太大
    • 学习Q值时,使用的是Huber Loss
      $$
      l_{\mathcal{k}}(\delta) =
      \begin{cases}
      \ 0.5\delta^2& \text{if}\ \delta \le \mathcal{k}\\
      \mathcal{k}(|\delta| - 0.5\mathcal{k})& \text{otherwise.}
      \end{cases}
      $$

BCQ 离散版本

训练流程

  • 整体流程概览:

Serving 步骤

  • 按照如下策略决策:
    $$ \pi(s) = \mathop{\arg\max}_{a\vert\frac{G_w(a|s)}{\max_\hat{a} G_w(\hat{a}|s)} \gt \tau} Q_\theta(s,a) $$

RL——CQL

  • 参考链接:
    • 原始论文:NIPS 2020, Conservative q-learning for offline reinforcement learning
    • 【论文分享】Conservative Q-Learning for Offline Reinforcement Learning
    • Conservative Q-Learning for Offline Reinforcement Learning:手打公式
    • 离线强化学习系列3(算法篇): 值函数约束-CQL算法详解与实现:手打公式
    • github.com/aviralkumar2907/CQL:CQL实现源码

CQL 在解决什么问题?

  • 分布偏移(distribution shift) :分布偏移主要是模型训练和预测时的分布存在差异,即训练数据集中的数据分布(训练)与实际决策策略下环境反馈的数据分布(预测)之间的差异。
    • 这种差异可能导致学习到的策略在实际应用中表现不佳,因为该策略是在一个与实际环境不完全相同的数据分布上学习得到的
    • 离线强化学习中这种问题会放大,特别地,会导致OOD问题
  • OOD(Out-of-distribution) :OOD通常指在训练集中没有被观察到过的样本(状态或状态-动作对),实际上,出现频率极低的样本也可以算作一定程度上的OOD样本
    • OOD问题是由于分布偏移导致的,理论上,没有分布偏移问题就不存在OOD问题 ,因为模型不会遇到这些未观察过的样本
  • OOD 问题容易导致值高估(Overestimation of values)问题 :强化学习的迭代公式一般都是找时的动作最大的动作,这本身导致的容易值高估的现象

CQL 相关推导

一些定义

  • 数据集 \(\mathcal{D} \sim d^{\pi_{\beta}}(\mathbf{s})\pi_{\beta}(\mathbf{a} \mid \mathbf{s})\),即数据是行为策略 \(\pi_\beta\) 与环境交互来得到的
  • 对于任意 \((s_0, a_0) \in \mathcal{D}\),有经验行为策略(empirical behavior policy)为:
    $$ \hat{\pi}_\beta(a_0\vert s_0) = \frac{\sum_{(s,a) \in \mathcal{D}}\mathbf{1}(s=s_0,a=a_0)}{\sum_{s\in \mathcal{D}}\mathbf{1}(s=s_0)} $$

回顾贝尔曼算子

  • 一般的贝尔曼算子(Bellman Operator),写作 \(\mathcal{B}^\pi\),重复对 \(Q(s,a)\) 使用 \(\mathcal{B}^\pi\),持续迭代可收敛到策略 \(\pi\) 对应的Q值 \(Q^{\pi}(s,a)\) 值:
    $$
    \mathcal{B}^\pi Q = r(s, a) + \gamma \mathbb{E}_{s^\prime \sim p(s^\prime \vert s, a), a^\prime \sim \pi(a^\prime\vert s^\prime)}[Q (s^\prime, a^\prime)]
    $$
  • Q-Learning的迭代公式,相当于策略是找Q值最优的那个动作,通过对Q重复使用如下贝尔曼最优算子(Bellman Optimality Operator),写作 \(\mathcal{B}^{\pi^*}\) 或者 \(\mathcal{B}^*\):
    $$ \mathcal{B}^{*} Q(\mathbf{s}, \mathbf{a})=r(\mathbf{s}, \mathbf{a})+\gamma \mathbb{E}_{\mathbf{s}^{\prime} \sim P\left(\mathbf{s}^{\prime} \mid \mathbf{s}, \mathbf{a}\right)}\left[\max _{\mathbf{a}^{\prime}} Q\left(\mathbf{s}^{\prime}, \mathbf{a}^{\prime}\right)\right] $$

Offline RL 中的贝尔曼算子

  • 在 Offline RL 中,我们定义新的贝尔曼算子 \(\hat{\mathcal{B}}^\pi\),即更新只在固定数据集上进行,即对于给定的数据集 \(\mathcal{D} = { (s,a,r,s’)} \sim \pi_\beta\), \(\hat{\mathcal{B}}^\pi\) 的更新都发生在数据集上
  • 对于给定数据集 \(\mathcal{D} \sim \pi_\beta\) 上的贝尔曼算子 \(\hat{\mathcal{B}}^\pi\),我们定义 \(\hat{\mathcal{B}}^\pi\) 如下:
    $$
    \hat{\mathcal{B}}^\pi \hat{Q} = r(s, a) + \gamma \mathbb{E}_{s^\prime \sim \mathcal{D}, a^\prime \sim \pi(a^\prime\vert s^\prime)}[\hat{Q} (s^\prime, a^\prime)]
    $$

如果在 Offline RL 中使用常规AC方法会发生什么?

  • Actor-Critic的策略迭代定义为(这种限定数据集的做法是被迫的,因为没法与环境交互):
    $$
    \begin{align}
    \hat{Q}^{k+1} &\leftarrow \mathop{\arg\min}_{Q} \mathbb{E}_{s,a,s^\prime \sim \mathcal{D}}\left[ \left( r(s,a) + \gamma\mathbb{E}_{a^\prime \sim \hat{\pi}^{k}(a^\prime| s^\prime)}[\hat{Q}^k(s^\prime, a^\prime)] - Q(s, a) \right)^2 \right] \ &\text{(policy evaluation)}\\
    \hat{\pi}^{k+1} &\leftarrow \mathop{\arg\max}_{\pi} \mathbb{E}_{s\sim \mathcal{D}, a\sim \pi(a\vert s)}\left[ \hat{Q}^{k+1} (s,a) \right] \ &\text{(policy improvement)}
    \end{align}
    $$
    • 以上公式来自论文,原始论文中使用的是 \(a \sim \pi^k(a|s)\),这里应该改成 \(a \sim \pi(a|s)\) 更合适,因为argmax的目标参数是 \(\pi\),所以我改成了 \(a \sim \pi(a|s)\) 表示找到最优的策略 \(\pi\),使得按照这个策略决策(采样或者选择动作)得到的期望收益Q值是最大的
    • 其实AC方法中,包含了DQN的迭代思路,策略迭代部分, \(a’\) 始终取上一轮Q值最大的动作即可
    • policy evaluation实际上就是在重复对Q使用贝尔曼算子,只是使用最小化均方误差的形式去实现了
  • 问题:Offline RL场景中直接使用上面的策略迭代会面临分布偏移问题 ,从而导致高估:
    • 理解:1) 目标Q值的计算应该使用当前策略 \(\pi^k\),但是数据集中只有从数据集 \(\mathcal{D}\) 中采样到的样本,对应策略 \(\pi_\beta\),极端情况下,策略 \(\pi^k\) 采样到的动作 \(a’ \sim \pi^k\) 可能从未在数据集中出现过,此时模型是无法准确评估 \(Q(s’,a’)\) 的;2)常规的迭代方法中,一般都包含着 \(a’ = \mathop{\arg\max}_a Q(s,a)\) 或者隐式的包含了 \(Q(s, a) = r + \max_{a} Q(s^\prime, a)\) 这样的思想,此时预估值 \(Q(s’,a’)\) 低估不会出现问题,但是 \(Q(s’,a’)\) 一旦高估,该动作就会被选中作为目标值;3)Offline RL场景中没有机会引入新样本来重新修正 \(Q(s’,a’)\) 的高估
    • 在Online RL的场景中,一般不存在该问题,因为一个动作被错误的高估以后,往往会在策略跟环境的交互中选中该动作,从而使得该动作被修正
  • 总结一下:对于策略 \(\pi\),我们的真实Q值是 \(Q^\pi\),在固定的数据集下学到的是 \(\hat{Q}^\pi\),但该值一般往往会高估,我们的目标是让 \(\hat{Q}^\pi\) 尽量接近真实值 \(Q^\pi\),那么面临的往往是高估这个问题,CQL算法的核心思想就是解决这个问题

改进一:打压未知动作的Q值

  • 对于任意的未知策略 \(\mu\),在行为策略 \(\pi_\beta\) 交互收集到的数据集 \(\mathcal{D}\) 中进行训练,其状态动作对访问分布为 \(\mu(s, a)=d^{\pi_\beta}(s) \mu(a \mid s)\),我们的目标通过最小化未知策略采样到的动作对应的Q值,来实现Q值的保守学习:
    $$\hat{Q}^{k+1} \leftarrow \arg \min_{Q} \color{red}{\alpha} \mathbb{E}_{\mathbf{s} \sim \mathcal{D}, \mathbf{a} \sim \mu(\mathbf{a} \mid \mathbf{s})}[Q(\mathbf{s}, \mathbf{a})]+\frac{1}{2} \mathbb{E}_{\mathbf{s}, \mathbf{a}, \mathbf{s’} \sim \mathcal{D}}\left[\left(Q(\mathbf{s}, \mathbf{a})-\hat{\mathcal{B}}^{\pi} \hat{Q}^{k}(\mathbf{s}, \mathbf{a})\right)^{2}\right]$$

  • 使用 \(\mathbf{s}, \mathbf{a}, \mathbf{s’} \sim \mathcal{D}\) 的原因是因为想强调 \(\hat{\mathcal{B}}^{\pi}\) 使用的 \(s’\) 不是按照环境的状态转移概率算的,而是直接使用的数据集中的内容

  • 上面的迭代公式学到的是 \(\hat{Q}^\pi\) (其中 \(\hat{Q}^\pi := \lim_{k\rightarrow \infty}\hat{Q}^k\))

  • 为了方便表达,一些论文或博客会使用 \(\mathcal{L}_{Bellman}(Q) = \frac{1}{2} \mathbb{E}_{\mathbf{s}, \mathbf{a} \sim \mathcal{D}}\left[\left(Q(\mathbf{s}, \mathbf{a})-\hat{\mathcal{B}}^{\pi} \hat{Q}^{k}(\mathbf{s}, \mathbf{a})\right)^{2}\right]\) 来替换等号后面的式子

  • 这里论文中给出了证明(Theorem 3.1):

    • 上式说明:
      • 当 \(supp\ \mu \subset supp\ \pi\) ( \(supp\ \mu\) 表示支持集),且 \(\alpha\) 足够大时, \(\forall \ s\in\mathcal{D},a\in \mathcal{A}\),均有 \(\hat{Q}^\pi(s,a) \le Q^\pi(s,a)\) 成立。即对于任意的分布 \(\mu\),只要我们这里 \(\alpha\) 取得足够大,总能学到一个比真实值 \(Q^\pi(s,a)\) 小的Q值
      • 当 \(supp\ \mu \subset supp\ \pi\),且 \(\hat{B^\pi} = \mathcal{B}^\pi, \ \alpha > 0\) 时,对 \(\forall \ s\in\mathcal{D},a\in \mathcal{A}\),均有 \(\hat{Q}^\pi(s,a) \le Q^\pi(s,a)\) 成立。即如果我们的数据集可以反映真实的数据分布,那么数据偏移就不存在了,我们直接令 \(\alpha=0\),退化到常规的贝尔曼算子对应的损失函数即可(注:此时的数据集 \(\mathcal{D}\) 是从当前策略采样的,故 \(\alpha=0\) 后的式子就是常规贝尔曼算子对应的损失函数)
    • 在概率论和机器学习中,当我们说两个离散概率分布 \(\mu(a|s)\) 和 \(\pi(a|s)\) 满足 \(supp\ \mu \subset supp\ \pi\),这意味着 \(\mu(a|s)\) 的支持集(即 \(\mu(a|s)\) 分配了正概率的所有动作 \(a\) 的集合)是 \(\pi(a|s)\) 支持集的子集。换句话说,对于所有 \(\mu(a|s)\) 给予正概率的动作 \(a\), \(\pi(a|s)\) 也必须给予正概率。简而言之,如果某个动作在 \(\mu(a|s)\) 下是可能发生的(即它有非零的概率),那么在 \(\pi(a|s)\) 下这个动作也是可能发生的。但是, \(\pi(a|s)\) 可能包括一些 \(\mu(a|s)\) 不考虑的动作,这些动作在 \(\pi(a|s)\) 中有正概率但在 \(\mu(a|s)\) 中没有或者为零概率

改进二:打压补偿

  • 改进一学到了 \(Q^\pi(s,a)\) 的逐点下界 \(\forall \ s\in\mathcal{D},a\in \mathcal{A}\),均有 \(\hat{Q}^\pi(s,a) \le Q^\pi(s,a)\),但直观上看,打压过于严格了,甚至行为策略采样到的状态动作对都会打压(其实这些地方我们能估准的),为了缓解这个问题,我们对改进一的打压做一些补偿:
    $$\hat{Q}^{k+1} = \mathop{\arg\min}_Q \color{red}{\alpha} \left(\mathbb{E}_{s\sim \mathcal{D}, a\sim \mu(a\vert s)}[Q(s, a)] - \color{red} { \mathbb{E}_{s\sim \mathcal{D}, a\sim\hat{\pi}_\beta(a\vert s)}[Q(s, a)] } \right) + \frac{1}{2} \mathbb{E}_{\mathbf{s}, \mathbf{a}, \mathbf{s’} \sim \mathcal{D}}\left[\left(Q(\mathbf{s}, \mathbf{a})-\hat{\mathcal{B}}^{\pi} \hat{Q}^{k}(\mathbf{s}, \mathbf{a})\right)^{2}\right]$$

  • 这里论文中给出了证明(Theorem 3.2):

    • 上式说明:
      • 当 \(\mu=\pi\) (注意,改进一种不需要这个约束),且 \(\alpha\) 较大时,有 \(\forall \ s\in\mathcal{D}\),均有 \(\hat{V}^\pi(s) \le V^\pi(s)\)
      • 当 \(\mu=\pi\),且 \(\hat{B^\pi} = \mathcal{B}^\pi, \ \alpha > 0\) 时,有 \(\forall \ s\in\mathcal{D}\),均有 \(\hat{V}^\pi(s) \le V^\pi(s)\)
    • 此时虽然不能再保证学到了 \(Q^\pi(s,a)\) 的逐点下界: \(\forall \ s\in\mathcal{D},a\in \mathcal{A}\),均有 \(\hat{Q}^\pi(s,a) \le Q^\pi(s,a)\)
    • 但可以保证学到了 \(Q^\pi(s,a)\) 的期望下界: \(\mathbb{E}_{\pi(a|s)}[\hat{Q}^\pi(s,a)] \le V^\pi(s) = \mathbb{E}_{\pi(a|s)}[Q^\pi(s,a)]\)

改进三:CQL(\(\mathcal{R}\))

  • 一个遗留问题:论文中提到改进二需要进一步改进,但为什么不能直接用策略二,令 \(\mu=\pi\),然后直接使用改进二的公式更新?原始论文关于改进二的缺点描述(原始论文中对这里的描述不够具体,缺乏说服力)
    • 改进二已经说明了在 \(\mu=\pi\) 时,可以学到一个合适的下界,但是由于改进二中需要对策略 \(\mu\) ( \(\mu=\pi\) )进行采样,即每次迭代Q值时都需要上一轮的策略 \(\pi\) 来采样,这样的话,智能交替进行策略评估和策略提升,且策略评估需要迭代足够长的步骤才能收敛,所以非常耗时(问题,常规的AC不都是这么实现的吗?其实也没有问题吧)
    • 补充:CQL原始论文的描述截图
  • 接下来,我们先假定论文中提到的改进二中的公式确实存在缺点,需要改进,那么可以做如下改进
  • 我们可以进一步地优化,考虑到 \(\pi\) 是使得Q值最大的策略,所以我们使用使得Q值最大的 \(\mu\) 去拟合,改进二的公式可以优化为下面这样:
    $$\hat{Q}^{k+1} = \min_Q \max_\mu \color{red}{\alpha} (\mathbb{E}_{s\sim \mathcal{D}, a\sim \color{red}{\mu(a\vert s)} }[Q(s, a)] - \mathbb{E}_{s\sim \mathcal{D}, a\sim\hat{\pi}_\beta(a\vert s)}[Q(s, a)]) + \frac{1}{2} \mathbb{E}_{\mathbf{s}, \mathbf{a}, \mathbf{s’} \sim \mathcal{D}}\left[\left(Q(\mathbf{s}, \mathbf{a})-\hat{\mathcal{B}}^{\pi} \hat{Q}^{k}(\mathbf{s}, \mathbf{a})\right)^{2}\right] + \color{red}{\mathcal{R}(\mu)} $$
    • 为了防止寻找Q值最大化的 \(\mu\) 时出现过拟合,我们增加正则项 \(\mathcal{R}(\mu)\),一般取 \(\mathcal{R}(\mu) = - D_{KL} (\mu| \rho)\),其中 \(\rho\) 是一个已知分布

改进四:CQL(\(\mathcal{\rho}\))

  • 在CQL(\(\mathcal{R}\))中,求解 \(\mu\) 相当于要求解下面的优化问题
    $$
    \begin{align}
    \max_{\mu} \mathbb{E}_{a \sim \mu(a|s)}[Q(s,a)]&\color{red}{-}D_{\mathrm{KL}}(\mu | \rho) \\
    \text { s.t. } \quad \sum_{a} \mu(a|s)&=1 \\
    \mu(a|s) &\geq 0, \ \forall \mathbf{a} .
    \end{align}
    $$
    • 注意:论文附录中错误地将 \(-D_{\mathrm{KL}}(\mu | \rho)\) 写成了 \(+D_{\mathrm{KL}}(\mu | \rho)\) (因为上述公式的本意是最小化KL散度),需要修正过来
  • 上述优化问题的最优解是:
    $$
    \mu^{*}(a|s)=\frac{1}{Z} \rho(a|s) \exp (Q(s,a))
    $$
    • 其中 \(Z=\sum_a \rho(a\vert s)\cdot \exp(Q(s, a))\), \(Z\) 也被称为归一化因子(normalizing factor)
    • 以上优化问题求解的详细证明与AWR论文相似。更一般地,将以上变量 \(a\) 替换成 \(x\),即 \(Q(s,a)\) 替换成 \(f(x)\) 均可成立
  • 最终我们有CQL(\(\mathcal{\rho}\))的表达形式:
    $$
    \hat{Q}^{k+1} = \min_Q \color{red}{\alpha} \mathbb{E}_{s\sim d^{\pi_\beta}(s)} \left[ \mathbb{E}_{a\sim \rho(a\vert s)} \left[ Q(s, a) \cfrac{\exp(Q(s, a))}{Z} \right ] - \mathbb{E}_{a \sim \hat{\pi}_\beta(a\vert s)}[Q(s, a)] \right] + \frac{1}{2} \mathbb{E}_{\mathbf{s}, \mathbf{a}, \mathbf{s’} \sim \mathcal{D}}\left[\left(Q(\mathbf{s}, \mathbf{a})-\hat{\mathcal{B}}^{\pi} \hat{Q}^{k}(\mathbf{s}, \mathbf{a})\right)^{2}\right]
    $$
    • 原始论文中使用 \(s\sim d^{\pi_\beta}(s)\),实际上与 \(s \sim \mathcal{D}\) 等价,其他形式都是使用 \(s \sim \mathcal{D}\)
    • 论文中,实验时取 \(\rho(a \vert s) = \hat{\pi}^{k-1}(a \vert s)\),实验表格中的CQL(\(\mathcal{\rho}\))就是这个含义

改进五:CQL(\(\mathcal{H}\))

  • 当CQL(\(\mathcal{\rho}\))中的 \(\rho\) 是均匀分布时,有最优解:
    $$
    \begin{align}
    \mu^*(a\vert s) &= \cfrac{\rho(a\vert s)\cdot \exp(Q(s, a))}{\sum_a \rho(a\vert s)\cdot \exp(Q(s, a))} \\
    &= \cfrac{\rho(a\vert s)\cdot \exp(Q(s, a))}{\rho(a\vert s) \sum_a \exp(Q(s, a))} \\
    &= \cfrac{\exp(Q(s, a))}{\sum_a \exp(Q(s, a))}
    \end{align}
    $$
  • 将 \(\mu^*(a\vert s) = \cfrac{\exp(Q(s, a))}{\sum_a \exp(Q(s, a))} \) 带入CQL(\(\mathcal{R}\)),可得CQL(\(\mathcal{H}\)):
    $$
    \hat{Q}^{k+1} = \min_Q \color{red}{\alpha} \mathbb{E}_{s\sim\mathcal{D}} \left[ \log \sum_a \exp(Q(s, a)) - \mathbb{E}_{a \sim \hat{\pi}_\beta(a\vert s)}[Q(s, a)] \right] + \frac{1}{2} \mathbb{E}_{\mathbf{s}, \mathbf{a}, \mathbf{s’} \sim \mathcal{D}}\left[\left(Q(\mathbf{s}, \mathbf{a})-\hat{\mathcal{B}}^{\pi} \hat{Q}^{k}(\mathbf{s}, \mathbf{a})\right)^{2}\right]
    $$
    • 论文中,取 \(\rho(a \vert s)\) 是均匀分布(即 \(\rho(a|s)=\text{Unif}(a)\))时,相当于最大化策略熵,故称此时的更新方式为CQL(\(\mathcal{H}\))

CQL 伪代码

  • 伪代码流程如下,其中CQL(\(\mathcal{R}\))可以是CQL(\(\mathcal{H}\)),也可以是CQL(\(\mathcal{\rho}\)):

  • 如果是Q-learning模式:仅更新Q值即可,最后定义 \(\mu(s) = \mathop{\arg\max}_a Q(s,a)\) 作为最终的策略

  • 如果是Actor-Critic模式:需要使用SAC的训练方式额外训练actor

实践说明

  • \(\alpha\) 的选择:
  • \(\alpha\) 可以变成可学习的值?
  • \(\log\sum_a \exp(Q(s,a))\) 的计算:
  • CQL(\(\mathcal{H}\))和CQL(\(\mathcal{\rho}\))谁更好?
    • 一般来说 CQL(\(\mathcal{H}\))优于CQL(\(\mathcal{\rho}\)),当动作空间特别大时logsumexp预测方差变得很大,此时使用CQL(\(\mathcal{\rho}\))效果更好
  • 一些超参数的设置:

一些说明和思考

  • CQL原始论文中符号使用有点混乱比如CQL(\(\mathcal{R}\)),CQL(\(\mathcal{H}\))和CQL(\(\mathcal{\rho}\))三者的定义不清晰,特别是CQL(\(\mathcal{\rho}\))在正文中没有得到明确的定义,附录里面才有定义,而伪代码中强调的公式4:CQL(\(\mathcal{R}\)),实际上公式4是CQL(\(\mathcal{H}\)),这里我们特别对三个方法的定义进行辨析:

    • CQL(\(\mathcal{R}\)):CQL原始形式
    • CQL(\(\mathcal{\rho}\)):CQL变体,对任意 \(\rho\) 均可使用这个表述,包含了后面的CQL(\(\mathcal{H}\)),论文中实验时使用的是 \(\rho(a \vert s) = \hat{\pi}^{k-1}(a \vert s)\)
    • CQL(\(\mathcal{H}\)):CQL变体,当CQL(\(\mathcal{\rho}\))中 \(\rho\) 取均匀分布时的更新形式
  • 原始论文中 \(s\sim d^{\pi_\beta}(s)\) 和 \(s \sim \mathcal{D}\) 混用,比较公式时容易对不齐,实际上两者是等价的

  • 从推导可以看出,数据越充足,需要的 \(\alpha\) 就越小

  • 问题:为什么直接更新改进二中的更新公式不可以?为什么训练耗时长?普通的AC不都是这么实现的吗?

    • 普通AC确实是这样实现的,但是在Offline RL场景,不希望迭代效率过慢?
  • 问题:为什么使用均匀分布以后,可以推导出CQL(\(\mathcal{H}\))的形式?

    • 详请见附录推导
  • CQL算法得到的策略一定很优秀吗?答案是不会比行为策略差太多

    • 具体来说(Theorem 3.6):CQL算法得到的策略 \(\pi^*(a|s)\) 是一个策略 \(\hat{\pi}_\beta\) 的 \(\zeta\) -safe policy improvement,即有 \(1-\zeta\) 的概率可以保证 \(J(\pi^*, M) \ge J(\hat{\pi}_\beta, M) - \zeta\)

附录:证明约束优化问题

  • 目标是求解下面的约束问题
    $$
    \begin{align}
    \max {\mu} \mathbb{E}_{\mathbf{x} \sim \mu(\mathbf{x})}[f(\mathbf{x})]&-D_{\mathrm{KL}}(\mu | \rho) \\
    \text { s.t. } \quad \sum_{\mathbf{x}} \mu(\mathbf{x})&=1\\
    \mu(\mathbf{x}) &\geq 0, \ \forall \mathbf{x}.
    \end{align}
    $$
  • 需要证明上述式子的最优解为:
    $$\mu^{*}(\mathbf{x})=\frac{1}{Z} \rho(\mathbf{x}) \exp (f(\mathbf{x}))$$
    • 其中 \(Z = \sum_{\mathbf{x}} \rho(\mathbf{x}) \exp (f(\mathbf{x}))\)
  • 证明前,我们先将上述问题修改成更一般的形式(更一般的形式更常用一些),在更一般的形式下, \(D_{\mathrm{KL}}(\mu | \rho)\) 经常会加上温度系数 \(\alpha\) 或出现在约束中:
    $$
    \begin{align}
    \max_{\mu} \mathbb{E}_{\mathbf{x} \sim \mu(\mathbf{x})}[&f(\mathbf{x})] \\
    \text { s.t. } \quad D_{\mathrm{KL}}(\mu | \rho) &\le \epsilon \\
    \quad \sum_{\mathbf{x}} \mu(\mathbf{x})&=1\\
    \mu(\mathbf{x}) &\geq 0, \ \forall \mathbf{x}.
    \end{align}
    $$
  • 求解上面的问题可以先转换成构造拉格朗日函数
    • 原始问题变形
      $$
      \begin{align}
      \min_{\mu} - \mathbb{E}_{\mathbf{x} \sim \mu(\mathbf{x})}[&f(\mathbf{x})] \\
      \text { s.t. } \quad D_{\mathrm{KL}}(\mu | \rho) - \epsilon &\le 0 \\
      \quad \sum_{\mathbf{x}} \mu(\mathbf{x}) - 1 &= 0 \\
      \mu(\mathbf{x}) &\geq 0, \ \forall \mathbf{x}.
      \end{align}
      $$
    • 拉格朗日函数如下
      $$
      \begin{align}
      L(\mu,\alpha,\beta) &= -\mathbb{E}_{\mathbf{x} \sim \mu(\mathbf{x})}[f(\mathbf{x})] + \alpha(D_{\mathrm{KL}}(\mu | \rho)-\epsilon) + \beta(\sum_{\mathbf{x}} \mu(\mathbf{x})-1) \\
      L(\mu,\alpha,\beta) &= -\sum_x \mu(\mathbf{x})f(\mathbf{x}) + \alpha( \sum_x \mu(\mathbf{x}) \log\frac{\mu(\mathbf{x})}{\rho(\mathbf{x})} -\epsilon) + \beta(\sum_{\mathbf{x}} \mu(\mathbf{x})-1) \\
      L(\mu,\alpha,\beta) &= -\sum_x \mu(\mathbf{x})f(\mathbf{x}) + \alpha( \sum_x \mu(\mathbf{x}) \log \mu(\mathbf{x}) - \sum_x \mu(\mathbf{x}) \log \rho(\mathbf{x}) -\epsilon) + \beta(\sum_{\mathbf{x}} \mu(\mathbf{x})-1) \\
      \end{align}
      $$
  • 对上式微分并令微分结果等于0有:
    $$
    \begin{align}
    \frac{\partial L(\mu,\alpha,\beta)}{\partial \mu(x)} &= -\sum_x f(\mathbf{x}) + \alpha \sum_x ( \log \mu(\mathbf{x}) + 1) - \alpha \sum_x \log \rho(\mathbf{x}) + \sum_x \beta \\
    &= \sum_x (- f(\mathbf{x}) + \alpha \log \mu(\mathbf{x}) + 1 - \alpha \log \rho(\mathbf{x}) + \beta) \\
    &= 0
    \end{align}
    $$
    • 上式中求导使用到了 \(\frac{\partial \log \mu(x)}{\partial \mu(x)} = \frac{1}{\mu(x)}\)
  • 进一步可以得到
    $$
    - f(\mathbf{x}) + \alpha \log \mu(\mathbf{x}) + 1 - \alpha \log \rho(\mathbf{x}) + \beta = 0
    $$
  • 即
    $$
    \begin{align}
    \alpha \log \mu(\mathbf{x}) &= f(\mathbf{x}) + \alpha \log \rho(\mathbf{x}) - (\beta + 1) \\
    \log \mu(\mathbf{x}) &= \frac{1}{\alpha}f(\mathbf{x}) + \log \rho(\mathbf{x}) + \frac{- (\beta + 1)}{\alpha} \\
    \mu(\mathbf{x}) &= exp(\frac{1}{\alpha}f(\mathbf{x}) + \log \rho(\mathbf{x}) + \frac{- (\beta + 1)}{\alpha}) \\
    \mu(\mathbf{x}) &= exp(\frac{1}{\alpha}f(\mathbf{x})) \cdot exp(\log \rho(\mathbf{x})) \cdot exp(\frac{- (\beta + 1)}{\alpha}) \\
    \mu(\mathbf{x}) &= \rho(\mathbf{x})exp(\frac{1}{\alpha}f(\mathbf{x})) \cdot exp(\frac{- (\beta + 1)}{\alpha}) \\
    \end{align}
    $$
  • 由于 \(exp(\frac{- (\beta + 1)}{\alpha})\) 包含拉格朗日乘子,是未知的,所以我们进一步化简,尝试将这部分替换为已知式子,对上述结果最后一步两边同时积分有
    $$
    \begin{align}
    \sum_x \mu(\mathbf{x}) &= \sum_x (\rho(\mathbf{x})exp(\frac{1}{\alpha}f(\mathbf{x})) \cdot exp(\frac{- (\beta + 1)}{\alpha})) \\
    1 &= exp(\frac{- (\beta + 1)}{\alpha}) \sum_x (\rho(\mathbf{x})exp(\frac{1}{\alpha}f(\mathbf{x}))) \\
    exp(\frac{- (\beta + 1)}{\alpha}) &= \frac{1}{\sum_x (\rho(\mathbf{x})exp(\frac{1}{\alpha}f(\mathbf{x})))} \\
    \end{align}
    $$
  • 将 \(exp(\frac{- (\beta + 1)}{\alpha}) = \frac{1}{\sum_x (\rho(\mathbf{x})exp(\frac{1}{\alpha}f(\mathbf{x})))}\) 的结果带入 \(\mu(\mathbf{x}) = \rho(\mathbf{x})exp(\frac{1}{\alpha}f(\mathbf{x})) \cdot exp(\frac{- (\beta + 1)}{\alpha})\) 可以解的最终解:
    $$\mu^{*}(\mathbf{x})=\frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x}))$$
    • 其中 \(Z = \sum_{\mathbf{x}} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x}))\)
  • 回到最初的问题:我们令 \(\alpha=1\) 即可退回到原始问题

附录:最优策略形式的使用方式

  • 从上面的证明,我们已经得到了最优策略的一般形式 \(\mu^{*}(\mathbf{x})=\frac{\rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x}))}{\sum_{\mathbf{x}} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x}))} \),但这个形式难以直接使用
    • 难以直接使用的原因(个人理解):
      • 离线强化场景中 \(\rho\) 未知,无法直接使用;
      • 在线强化学习场景中,难以用于状态维度高或动作空间大(包括连续状态或动作)的场景。状态和动作空间有限时, \(\rho\) 是上一布步的策略或者历史混合策略 \(f(\mathbf{x})\) 一般是 \(A^\rho(s,a)\),理论上如果按照on-policy更新或者记录policy和样本以后按照off-policy更新均可,但是实际更新时,这种非参数化的策略,不同状态的策略是隔离的(没有状态泛化能力),针对每个状态都要更行才能做到该状态上的策略迭代 \(\mu^{*}(\mathbf{a|s})=\frac{\rho(\mathbf{a|s}) \exp (\frac{1}{\alpha}f(\mathbf{a|s}))}{\sum_{\mathbf{a}} \rho(\mathbf{a|s}) \exp (\frac{1}{\alpha}f(\mathbf{a|s}))} \),相当于每次迭代需要收集大量的样本才能足够更新各个状态上的效果,否则在下一轮中遇到其他状态时,这里相当于没有被更新
  • 一般来说,可以用神经网络去表示策略,实际上还可以进一步推导,不同的算法,目标函数不同,推导得到的结果也不同
  • 对于CQL来说,由于目标是两步min max,需要进一步将最优解带入原始目标得到最终的目标
  • 对于AWR,AWAC和IQL(复用了AWR方法)等论文,这里会直接使用一个神经网络去拟合策略,并尝试求这个策略的参数更新公式
    $$
    \begin{align}
    \theta^* &= \mathop{\arg\min}_{\theta} D_{\mathrm{KL}}(\mu^*(\mathbf{x}) | \pi_\theta(\mathbf{x})) \\
    &= \mathop{\arg\min}_{\theta} D_{\mathrm{KL}}\Big( \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) | \pi_\theta(\mathbf{x})\Big) \\
    &= \mathop{\arg\min}_{\theta} \sum_{\mathbf{x}} \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) \log \frac{ \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x}))} {\pi_\theta(\mathbf{x})} \\
    &= \mathop{\arg\min}_{\theta} \sum_{\mathbf{x}} \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) \log \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) - \sum_{\mathbf{x}} \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) \log \pi_\theta(\mathbf{x}) \\
    &= \mathop{\arg\min}_{\theta} - \sum_{\mathbf{x}} \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) \log \pi_\theta(\mathbf{x}) \\
    &= \mathop{\arg\max}_{\theta} \sum_{\mathbf{x}} \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) \log \pi_\theta(\mathbf{x}) \\
    &= \mathop{\arg\max}_{\theta} \sum_{\mathbf{x}} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) \log \pi_\theta(\mathbf{x}) \quad \quad \text{Z与策略参数\theta无关,可以消掉} \\
    &= \mathop{\arg\max}_{\theta} \mathbb{E}_{\mathbf{x} \sim \rho(\mathbf{x})} \Big[\exp (\frac{1}{\alpha}f(\mathbf{x})) \log \pi_\theta(\mathbf{x}) \Big] \\
    \end{align}
    $$
  • 此时,最优解求解目标变成了从已知策略 \(\rho(\mathbf{x} )\) 中采样,并最大化 \(\exp (\frac{1}{\alpha}f(\mathbf{x})) \log \pi_\theta(\mathbf{x})\) 即可,此时的目标是可以直接对策略求梯度的,非常容易迭代

附录:证明 logsumexp 公式

  • 参考:CQL算法logsumexp公式推导
  • 当CQL(\(\mathcal{\rho}\))中的 \(\rho\) 是均匀分布时,有最优解:
    $$
    \begin{align}
    \mu^*(a\vert s) &= \cfrac{\rho(a\vert s)\cdot \exp(Q(s, a))}{\sum_a \rho(a\vert s)\cdot \exp(Q(s, a))} \\
    &= \cfrac{\rho(a\vert s)\cdot \exp(Q(s, a))}{\rho(a\vert s) \sum_a \exp(Q(s, a))} \\
    &= \cfrac{\exp(Q(s, a))}{\sum_a \exp(Q(s, a))}
    \end{align}
    $$
  • 带入CQL(\(\mathcal{R}\))形式有
    $$
    \begin{align}
    \mathbb{E}_{a \sim \mu^*} [Q(s, a)] - D_{\mathrm{KL}}(\mu^* | \rho) &= \mathbb{E}_{a \sim \mu^*} \left[ \exp(Q(s, a)) - \log(\mu^*) + \log(\rho)\right]\\
    &= \mathbb{E}_{a \sim \mu^*} \left[Q(s, a) - \log(\cfrac{\exp(Q(s, a))}{\sum_a \exp(Q(s, a))} ) +\log(\rho)\right]\\
    &= \mathbb{E}_{a \sim \mu^*} \left[Q(s, a) - \log(\exp(Q(s, a))) + \log(\sum_a \exp(Q(s, a))) +\log(\rho)\right]\\
    &= \mathbb{E}_{a \sim \mu^*} \left[\log(\sum_a \exp(Q(s, a))) + \log(\rho)\right]\\
    \end{align}
    $$
  • 显然 \(\log(\sum_a \exp(Q(s, a))) + \log(\rho)\) 此时与策略 \(\mu^*\) 无关,期望可以消掉,同时 \(\rho\) 是均匀分布时,有 \(\rho(a|s) = \frac{1}{|A|}\), \(\log(\rho) = -\log(|A|)\),于是有:
    $$
    \begin{align}
    \mathbb{E}_{a \sim \mu^*} [Q(s, a)] - D_{\mathrm{KL}}(\mu^* | \rho) &= \log \sum_a \exp(Q(s, a)) -\log(|A|)
    \end{align}
    $$
    • 注意,这里需要的是一个 \(\max_Q f(Q)\) 的形式,而 \(-\log(|A|)\) 这个值是个常数,与优化目标Q无关,可以消去
  • 补充问题:为什么 CQL(\(\mathcal{\rho}\)) 中可以直接消掉 \(\mathcal{R}(\mu)\),但是 CQL(\(\mathcal{H}\)) 中不行?
    • 理论上,CQL(\(\mathcal{\rho}\))中不能直接消掉 \(\mathcal{R}(\mu)\),CQL(\(\mathcal{H}\))中推导才是对的,论文中没有提这一点,实际上,把 \(\mathcal{R}(\mu)\) 从目标挪到约束上 \(\mathcal{R}(\mu) \le \epsilon\),最终推导的结果可以没有 \(\mathcal{R}(\mu)\),指数权重上会有个温度系数(因为新增约束引入的拉格朗日乘子)

RL——IMPALA

注:本文包含 AI 辅助创作

  • 参考链接
    • 原始论文:IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures
    • 补充材料(附录):IMPALA Supplemental Material
    • 其他参考博客:【强化学习 44】IMPALA/V-trace - 张海抱的文章 - 知乎

Paper Summary

  • 论文的目标是使用一个具有单一参数集的单一强化学习智能体来解决大量任务
    • 一个关键挑战是处理增加的数据量和延长的训练时间
  • 论文开发了一种新的分布式智能体 IMPALA(重要性加权 Actor-Learner 架构,Importance Weighted Actor-Learner Architecture),
    • IMPALA 不仅能在单机训练中更有效地使用资源,而且可以扩展到数千台机器,同时不牺牲数据效率或资源利用率
  • 论文通过将解耦的执行与学习相结合,并采用一种称为 V-trace 的新型 Off-policy 校正方法,实现了高吞吐量下的稳定学习
  • 论文在 DMLab-30(来自 DeepMind Lab 环境 (2016) 的 30 个任务集)和 Atari-57(Arcade Learning Environment (2013b) 中所有可用的 Atari 游戏)上展示了 IMPALA 在多任务强化学习中的有效性
  • 论文的结果表明,IMPALA 能够用更少的数据实现比先前智能体更好的性能,并且由于其多任务方法,关键地展示了任务间的正向迁移

Introduction and Discussion

  • 深度强化学习方法通过试错学习掌握了多种领域 (2015; 2016; 2017; 2013a; 2014)
    • 虽然在围棋 (2016) 和 Atari 游戏 (2015) 等任务上的改进是显著的,但进展主要是在单任务性能上,即每个任务分别训练一个智能体
  • 论文感兴趣的是开发能够同时掌握多种多样任务的新方法,以及适合评估此类方法的环境
  • 在多个任务上同时训练单个智能体的一个主要挑战是可扩展性
    • 由于当前 SOTA 方法如 A3C (2016) 或 UNREAL (2017) 可能需要多达十亿帧数据和数天时间来掌握一个单一领域,同时在数十个领域上训练它们就太慢而不实用
  • 论文提出了如图 1 所示的重要性加权 Actor-Learner 架构(Importance Weighted Actor-Learner Architecture, IMPALA)
  • IMPALA 能够扩展到数千台机器,同时不牺牲训练稳定性或数据效率
    • 与流行的基于 A3C 的智能体(其工作进程向中央参数服务器通信关于策略参数的梯度)不同,IMPALA 的执行者(actor)将经验轨迹(状态、动作和奖励的序列)通信给一个集中化的 Learner
      • 由于 IMPALA 中的 Learner 可以访问完整的经验轨迹,论文使用 GPU 对轨迹的小批量进行更新,同时积极并行化所有时间无关的操作
    • 这种解耦架构可以实现非常高的吞吐量
  • 然而,因为在梯度计算时,用于生成轨迹的策略可能落后于 Learner 上的策略若干次更新,学习就变成了 Off-policy 的
    • 因此,论文引入了 V-trace Off-policy Actor-Critic 算法来校正这种有害的差异
  • 结合可扩展架构和 V-trace,IMPALA 实现了每秒 250,000 帧的极高数据吞吐率,使其比单机 A3C 快 30 多倍
  • 关键的是,IMPALA 也比基于 A3C 的智能体更具数据效率,并且对超参数值和网络架构更具鲁棒性,使其能够更好地利用更深的神经网络
  • 论文通过在 DMLab-30(一个新的挑战集,包含在 3D DeepMind Lab (2016) 环境中的 30 个多样化认知任务)上训练单个智能体来解决多任务问题,以及在 Atari-57 任务集中的所有游戏上训练单个智能体,来展示 IMPALA 的有效性

Related Work

  • 最早扩展深度强化学习的尝试依赖于具有多个工作进程的分布式异步随机梯度下降(SGD)(2012)
    • 比如分布式 A3C (2016) 和 Gorila (2015)(深度 Q 网络 (2015) 的分布式版本)
  • 最近用于强化学习的异步 SGD 的替代方案
    • 包括使用进化过程 (2017)、分布式 BA3C (2018) 和 Ape-X (2018)(其具有分布式回放但同步 Learner )
  • 也有多项工作通过利用 GPU 来扩展强化学习
    • 其中最简单的方法之一是批处理 A2C (2017)
      • 在每一步,批处理 A2C 产生一批动作并将其应用于一批环境
      • 每批中最慢的环境决定了执行整批步骤所需的时间(见图 1(a) 和 1(b))
      • 换句话说,环境速度的高方差会严重限制性能
    • 批处理 A2C 在 Atari 环境中特别有效,因为与强化学习智能体执行的昂贵张量操作相比,渲染和游戏逻辑在计算上非常便宜
      • 但视觉或物理上更复杂的环境可能模拟速度较慢,并且每一步所需的时间可能具有高方差
      • 环境也可能具有可变长度的(子)片段,导致初始化片段时速度减慢
  • 与 IMPALA 最相似的架构是 GA3C (2016),它也使用异步数据收集来更有效地利用 GPU
    • GA3C 通过使用动态批处理将执行/前向传递与梯度计算/后向传递解耦
    • GA3C 中的 Actor/Learner 异步性导致学习期间的不稳定性,(2016) 仅通过在策略梯度估计期间向动作概率添加一个小常数来部分缓解
    • 相比之下,IMPALA 使用了更原则性的 V-trace 算法
  • 先前关于 Off-policy 强化学习的相关工作包括 (2000, 2001); (2009); (2014); (2017) 和 (2016)
    • 与论文工作最接近的是 Retrace 算法 (2016),它引入了多步强化学习的 Off-policy 校正,并已在多种智能体架构中使用 (2017); (2018)
    • Retrace 需要学习状态-动作值(state-action-value)函数 \(Q\) 以进行 Off-policy 校正
    • 然而,许多 Actor-Critic 方法(如 A3C)学习状态值(state-value)函数 \(V\) 而不是状态-动作值函数 \(Q\)
    • V-trace 基于状态值函数

IMPALA

  • IMPALA (图 1) 使用 Actor-Critic 设置来学习一个策略 \(\pi\) 和一个基线函数 \(V^{\pi}\)
  • 生成经验的过程与学习 \(\pi\) 和 \(V^{\pi}\) 的参数是解耦的
  • 该架构由一组 Actor 和 一个或多个 Learner 组成, Actor 反复生成经验轨迹, Learner 使用 Actor 发送的经验来 Off-policy 地 (off-policy) 学习 \(\pi\)
    • 在每个轨迹开始时,一个 Actor 会将其自身的本地策略 \(\mu\) 更新为最新的 Learner 策略 \(\pi\) (\(\mu \leftarrow \pi\)),并在其环境中运行 \(n\) 步
    • 在 \(n\) 步之后, Actor 将状态、动作和奖励的轨迹 \(x_{1},a_{1},r_{1},\ldots,x_{n},a_{n},r_{n}\) 连同相应的策略分布 \(\mu(a_{t}|x_{t})\) 和初始 LSTM 状态通过一个队列发送给 Learner
    • Learner 持续地在来自许多 Actor 的轨迹批次上更新其策略 \(\pi\)
  • 这种简单的架构使得 Learner 能够使用 GPU 进行加速,并且 Actor 可以轻松地分布在多台机器上
    • 但在更新时, Learner 策略 \(\pi\) 可能比 Actor 的策略 \(\mu\) 领先若干次更新,因此在 Actor 和 Learner 之间存在 策略滞后 (policy-lag)
  • V-trace 算法校正了这种滞后,从而在保持数据效率的同时实现了极高的数据吞吐量
    • 使用 Actor-Learner 架构,提供了像分布式 A3C 那样的容错能力,但通常具有更低的通信开销,因为 Actor 发送的是观测值而不是参数/梯度
  • 随着模型架构越来越深,单个 GPU 的速度常常成为训练期间的 limiting factor (限制因素)
  • 如图 1 所示,IMPALA 可以与分布式的 Learner 集合一起使用,以高效地训练大型神经网络
  • 参数分布在各个 Learner 之间, Actor 并行地从所有 Learner 检索参数,同时只将观测值发送给单个 Learner
  • IMPALA 使用同步参数更新,这在扩展到多台机器时对于保持数据效率至关重要 (2016)

Efficiency Optimisations

  • GPU 和 many-core CPU 通过运行少量大型、可并行化的操作而不是许多小操作而受益匪浅
  • 由于 IMPALA 中的 Learner 在整个轨迹批次上执行更新,因此它能够比像 A3C 这样的在线智能体并行化更多的计算
    • 例如,一个典型的深度 RL 智能体包含一个卷积网络,后接一个 长短期记忆网络 (Long Short-Term Memory, LSTM) (1997) 和一个在 LSTM 之后的全连接输出层
    • IMPALA Learner 通过将时间维度折叠到批次维度中,将卷积网络并行地应用于所有输入
  • 类似地,一旦所有 LSTM 状态计算完毕,它也将输出层并行地应用于所有时间步
    • 这种优化将有效批次大小增加到数千
    • 基于 LSTM 的智能体还通过利用网络结构依赖性和操作融合 (2016) 在 Learner 上获得了显著的加速
  • 最后,论文还利用了 TensorFlow (2017) 中提供的几种现成的优化,例如在执行计算的同时为 Learner 准备下一批数据、使用 XLA(一个 TensorFlow 即时编译器)编译部分计算图,以及优化数据格式以从 cuDNN 框架 (2014) 获得最大性能

V-trace

  • 在解耦的分布式 Actor-Learner 架构中, Off-policy 学习非常重要,因为 Actor 生成动作与 Learner 估计梯度之间存在滞后
  • 为此,论文为 Learner 引入了一种新颖的 Off-policy Actor-Critic 算法,称为 V-trace
  • 论文考虑 马尔可夫决策过程 (Markov Decision Processes, MDP) (1994; 1998) 中的 discounted infinite-horizon 强化学习问题,目标是找到一个策略 \(\pi\),以最大化未来折扣奖励的期望和:
    $$ V^{\pi}(x)\stackrel{ {\mathrm{def} } }{ {=} }\mathbb{E}_{\pi}\big{[} \sum_{t\geq 0}\gamma^{t}r_{t}\big{]} $$
    • 其中 \(\gamma\in[0,1)\) 是折扣因子,\(r_{t}=r(x_{t},a_{t})\) 是时间 \(t\) 的奖励,\(x_{t}\) 是时间 \(t\) 的状态(初始化为 \(x_{0}=x\)),\(a_{t}\sim\pi(\cdot|x_{t})\) 是通过遵循某个策略 \(\pi\) 生成的动作
  • Off-policy RL 算法的目标是使用由某个策略 \(\mu\)(称为 行为策略 (behaviour policy))生成的轨迹,来学习另一个策略 \(\pi\)(可能与 \(\mu\) 不同,称为 目标策略 (target policy))的价值函数 \(V^{\pi}\)

V-trace 目标 (V-trace target)

  • 考虑一个由 Actor 遵循某个策略 \(\mu\) 生成的轨迹 \((x_{t},a_{t},r_{t})_{t=s}^{t=s+n}\)
    • 论文为 \(V(x_{s})\)(论文在状态 \(x_{s}\) 的价值近似值)定义 \(n\)-step V-trace 目标为:
      $$v_{s}\stackrel{ {\mathrm{def} } }{ {=} } V(x_{s})+\sum_{t=s}^{s+n-1}\gamma^{t-s}\Big{(}\prod_{i=s}^{t-1 }c_{i}\Big{)}\delta_{t}V \tag{1}$$
      • 理解:这里是贝尔曼目标而不是 Advantage,类似 \(r_t + V(s_t)\) 的角色
      • 其中 \(\delta_{t}V\) 是 \(V\) 的时序差分:
        $$ \delta_{t}V\stackrel{ {\mathrm{def} } }{ {=} }\rho_{t}\big{(}r_{t}+ \gamma V(x_{t+1})-V(x_{t})\big{)} $$
      • \(\rho_{t}\) 和 \(c_{i}\) 是截断的重要性采样 (Importance Sampling, IS) 权重(论文使用符号约定 \(\prod_{i=s}^{t-1}c_{i}=1\) 当 \(s=t\))
        $$
        \rho_{t}\stackrel{ {\mathrm{def} } }{ {=} }\min\big{(}\bar{\rho},\frac {\pi(a_{t}|x_{t})}{\mu(a_{t}|x_{t})}\big{)} \\
        c_{i}\stackrel{ {\mathrm{def} } }{ {=} }\min\big{(}\bar{c},\frac{\pi(a_{ t}|x_{t})}{\mu(a_{t}|x_{t})}\big{)}
        $$
      • 此外,论文假设截断水平满足 \(\bar{\rho}\geq\bar{c}\)
  • 在 On-policy 的情况下(当 \(\pi=\mu\)),并假设 \(\bar{c}\geq 1\),那么所有的 \(c_{i}=1\) 且 \(\rho_{t}=1\),因此 (1) 式重写为
    $$
    \begin{align}
    v_{s} &=V(x_{s})+\sum_{t=s}^{s+n-1}\gamma^{t-s}\big{(}r_{t}+\gamma V(x_{t +1})-V(x_{t})\big{)}\\
    &=\sum_{t=s}^{s+n-1}\gamma^{t-s}r_{t}+\gamma^{n}V(x_{s+n})
    \end{align} \tag{2}
    $$
    • 这是 On-policy \(n\)-step Bellman 目标
    • 因此,在 On-policy 情况下,V-trace 简化为 On-policy \(n\)-step Bellman 更新
      • 这个属性(是 Retrace (2016) 所不具备的)允许人们对离线和 On-policy 数据使用相同的算法
  • (截断的)IS 权重 \(c_{i}\) 和 \(\rho_{t}\) 扮演不同的角色
  • 权重 \(\rho_{t}\) 出现在时序差分 \(\delta_{t}V\) 的定义中,并定义了此更新规则的固定点
    • 在表格情况下,即函数可以被完美表示时,此更新的固定点(即,当对所有状态都有 \(V(x_{s})=v_{s}\) 时),其特征是在期望下(在 \(\mu\) 下)\(\delta_{t}V\) 等于零,它是某个策略 \(\pi_{\bar{\rho} }\) 的价值函数 \(V^{\pi_{\bar{\rho} } }\),该策略由下式定义:
      $$\pi_{\bar{\rho} }(a|x)\stackrel{ {\mathrm{def} } }{ {=} }\frac{\min\big{(}\bar{\rho}\mu(a|x),\pi(a|x)\big{)} }{\sum_{b\in A}\min\big{(}\bar{\rho}\mu(b|x ),\pi(b|x)\big{)} } \tag{3}$$
    • (参见附录 A 中的分析)
    • 所以当 \(\bar{\rho}\) 是无限的(即没有对 \(\rho_{t}\) 进行截断)时,这就是目标策略 \(\pi\) 的价值函数 \(V^{\pi}\)
    • 然而,如果论文选择一个截断水平 \(\bar{\rho}<\infty\),论文的固定点就是策略 \(\pi_{\bar{\rho} }\) 的价值函数 \(V^{\pi_{\bar{\rho} } }\),该策略介于 \(\mu\) 和 \(\pi\) 之间
    • 在 \(\bar{\rho}\) 接近零的极限情况下,论文得到行为策略 \(\mu\) 的价值函数 \(V^{\mu}\)
    • 在附录 A 中,论文证明了相关 V-trace 算子的收缩性以及相应在线 V-trace 算法的收敛性
  • 权重 \(c_{i}\) 类似于 Retrace 中的“迹切割”系数
    • 它们的乘积 \(c_{s}\dots c_{t-1}\) 衡量了在时间 \(t\) 观察到的时序差分 \(\delta_{t}V\) 对先前时间 \(s\) 的价值函数更新的影响程度
    • \(\pi\) 和 \(\mu\) 越不相似(论文越是 Off-policy ),该乘积的方差就越大
    • 论文使用截断水平 \(\bar{c}\) 作为一种方差缩减技术
    • 但请注意,这种截断不会影响论文收敛到的解(该解仅由 \(\bar{\rho}\) 表征)
  • 因此,论文看到截断水平 \(\bar{c}\) 和 \(\bar{\rho}\) 代表了算法的不同特征:
    • \(\bar{\rho}\) 影响 IMPALA 收敛到的价值函数的性质
    • \(\bar{c}\) 影响 IMPALA 收敛到该函数的速度
  • Remark 1 :V-trace 目标可以递归地计算:
    $$v_{s}=V(x_{s})+\delta_{s}V+\gamma c_{s}\big{(}v_{s+1}-V(x_{s+1})\big{)}.$$
  • Remark 2 :
    • 与 Retrace\((\lambda)\) 类似,也可以在 V-trace 的定义中考虑一个额外的折扣参数 \(\lambda\in[0,1]\),通过设置 \(c_{i}=\lambda\min\big{(}\bar{c},\frac{\pi(a_{i}|x_{i})}{\mu(a_{i}|x_{i})}\big{)}\) 来实现
    • 在 On-policy 情况下,当 \(n=\infty\) 时,V-trace 则简化为 TD\((\lambda)\)

Actor-Critic algorithm

策略梯度 (Policy gradient)
  • 在 On-policy 情况下,价值函数 \(V^{\mu}(x_{0})\) 关于策略 \(\mu\) 的某个参数的梯度是
    $$\nabla V^{\mu}(x_{0})=\mathbb{E}_{\mu}\Big{[}\sum_{s\geq 0}\gamma^{s}\nabla\log \mu(a_{s}|x_{s})Q^{\mu}(x_{s},a_{s})\Big{]},$$
    • 其中 \(Q^{\mu}(x_{s},a_{s})\stackrel{ {\textrm{def} } }{ {=} }\mathbb{E}_{\mu} \big{[}\sum_{t\geq s}\gamma^{t-s}r_{t}|x_{s},a_{s}\big{]}\) 是策略 \(\mu\) 在 \((x_{s},a_{s})\) 的状态-动作价值
    • 这通常通过随机梯度上升来实现,该上升沿 \(\mathbb{E}_{a_{s}\sim\mu(\cdot|x_{s})}\Big{[}\nabla\log\mu(a_{s}|x_{s})q_{s}|x_ {s}\Big{]}\) 的方向更新策略参数,其中 \(q_{s}\) 是 \(Q^{\mu}(x_{s},a_{s})\) 的一个估计值,并在某个行为策略 \(\mu\) 下访问到的一组状态 \(x_{s}\) 上取平均
  • 现在,在论文考虑的 Off-policy 设置中,我们可以使用被评估的策略 \(\pi_{\bar{\rho} }\) 和行为策略 \(\mu\) 之间的 IS 权重,沿以下方向更新论文的策略参数
    $$\mathbb{E}_{a_{s}\sim\mu(\cdot|x_{s})}\Big{[}\frac{\pi_{\bar{\rho} }(a_{s}|x_{s })}{\mu(a_{s}|x_{s})}\nabla\log\pi_{\bar{\rho} }(a_{s}|x_{s})q_{s}\big{|}x_{s} \Big{]} \tag{4}$$
    • 其中 \(q_{s}\stackrel{ {\textrm{def} } }{ {=} }r_{s}+\gamma v_{s+1}\) 是从下一个状态 \(x_{s+1}\) 的 V-trace 估计 \(v_{s+1}\) 构建的 \(Q^{\pi_{\bar{\rho} } }(x_{s},a_{s})\) 的估计值
    • 论文使用 \(q_{s}\) 而不是 \(v_{s}\) 作为论文的 Q 值 \(Q^{\pi_{\bar{\rho} } }(x_{s},a_{s})\) 的目标的原因是:
      • 假设论文的价值估计在所有状态下都是正确的,即 \(V=V^{\pi_{\bar{\rho} } }\),那么论文有 \(\mathbb{E}[q_{s}|x_{s},a_{s}]=Q^{\pi_{\bar{\rho} } }(x_{s},a_{s})\)(而如果论文选择 \(q_{t}=v_{t}\) 则不具备此性质)。有关分析请参见附录 A,关于估计 \(q_{s}\) 的不同方法的比较请参见附录 E.3
  • 为了降低策略梯度估计 (4) 的方差,论文通常从 \(q_{s}\) 中减去一个依赖于状态的基线,例如当前的价值近似值 \(V(x_{s})\)
  • 最后请注意,(4) 式估计的是 \(\pi_{\bar{\rho} }\) 的策略梯度,这是在使用截断水平 \(\bar{\rho}\) 时 V-trace 算法所评估的策略
    • 然而,假设偏差 \(V^{\pi_{\bar{\rho} } }-V^{\pi}\) 很小(例如,如果 \(\bar{\rho}\) 足够大),那么我们可以期望 \(q_{s}\) 为论文提供 \(Q^{\pi}(x_{s},a_{s})\) 的良好估计
    • 考虑到这些 Remarks,论文推导出以下规范的 V-trace Actor-Critic 算法
V-trace actor-critic algorithm
  • 考虑价值函数 \(V_{\theta}\) 和当前策略 \(\pi_{\omega}\) 的参数化表示
  • 轨迹是由 Actor 遵循某个行为策略 \(\mu\) 生成的
  • V-trace 目标 \(v_{s}\) 由 (1) 定义
  • 在训练时间 \(s\),价值参数 \(\theta\) 通过梯度下降法在 \(l2\) 损失上朝着目标 \(v_{s}\) 更新,即,沿着下面的方向更新
    $$\big{(}v_{s}-V_{\theta}(x_{s})\big{)}\nabla_{\theta}V_{\theta}(x_{s})$$
  • 而策略参数 \(\omega\) 则沿着策略梯度的方向更新:
    $$\rho_{s}\nabla_{\omega}\log\pi_{\omega}(a_{s}|x_{s})\big{(}r_{s}+\gamma v_{s+1}- V_{\theta}(x_{s})\big{)}$$
  • 为了防止过早收敛,我们可以像在 A3C 中那样,沿着以下方向添加一个 熵奖励 (entropy bonus)
    $$-\nabla_{\omega}\sum_{a}\pi_{\omega}(a|x_{s})\log\pi_{\omega}(a|x_{s})$$
  • 总的更新是通过将这三个梯度按适当的系数重新缩放后相加得到的,这些系数是算法的超参数

Experiments

  • 论文研究了 IMPALA 在多种设置下的性能
  • 为了评估数据效率、计算性能和 Off-policy 校正的有效性,论文观察了在单个任务上训练的 IMPALA 智能体的学习行为
  • 对于多任务学习,论文在一个新引入的包含 30 个 DeepMind Lab 任务的集合以及 Atari 学习环境 (2013a) 的所有 57 个游戏上训练智能体,每个智能体对所有任务使用同一组权重
  • 在所有实验中,论文使用了两种不同的模型架构:
    • 一个类似于 (2016) 的浅层模型,在策略和价值函数之前有一个 LSTM(如图 3(左)所示);
    • 一个更深的残差模型 (2016)(如图 3(右)所示)
  • 对于有语言通道的任务,论文使用了一个以文本嵌入作为输入的 LSTM

计算性能 (Computational Performance)

  • 高吞吐量、计算效率和可扩展性是 IMPALA 的主要设计目标
  • 为了证明 IMPALA 在这些指标上优于当前算法,论文比较了 A3C (2016)、批处理 A2C 变体以及具有各种优化的 IMPALA 变体
    • 对于使用 GPU 的单机实验,论文在前向传播中使用动态批处理来避免多次批大小为 1 的前向传播
    • 论文的动态批处理模块由专门的 TensorFlow 操作实现,但在概念上类似于 GA3C 中使用的队列
  • 表 1 详细列出了使用图 3 中浅层模型的单机和多机版本的结果
    • 在单机情况下,IMPALA 在两个任务上都实现了最高性能,领先于所有批处理 A2C 变体以及 A3C
    • 且分布式多机设置才是 IMPALA 真正展示其可扩展性的地方
    • 通过第 3.1 节中的优化来加速基于 GPU 的学习器,IMPALA 智能体实现了 250,000 帧/秒或 210 亿帧/天的吞吐率
    • 为了减少每个学习器所需的执行器数量,可以使用辅助损失、来自经验回放的数据或其他仅在学习器上进行的昂贵计算

单任务训练 (Single-Task Training)

  • 为了研究 IMPALA 的学习动态,论文采用了单任务场景,在 5 个不同的 DeepMind Lab 任务上分别训练智能体
    • 该任务集包括一个规划任务、两个迷宫导航任务、一个带有脚本机器人的激光标签任务和一个简单的水果收集任务
  • 论文对熵正则化的权重、学习率和RMSProp epsilon进行了超参数扫描
    • 对于每个实验,论文使用一组相同的 24 个从附录 D.1 范围内预采样的超参数组合
    • 其他超参数固定为附录 D.3 中指定的值
收敛性与稳定性 (Convergence and Stability)
  • 图 4 显示了 IMPALA、A3C 和使用图 3 中浅层模型的批处理 A2C 之间的比较
  • 在所有 5 个任务中,要么是批处理 A2C 要么是 IMPALA 达到了最佳最终平均回报
    • 并且在除 seekavoid_arena_01 之外的所有任务中,它们在整个训练过程中都领先于 A3C
    • 理解:
      • A2C 是严格 On-policy 的,且参数是同步更新,所以是理论上的性能最优;
      • 对比来看,虽然 A3C 是 On-policy 的,但是存在参数的异步更新(有一定的滞后性),会导致一定的导致不稳定性
  • IMPALA 在 5 个任务中的 2 个上优于同步批处理 A2C,同时实现了更高的吞吐量(见表 1)
    • 论文推测这种行为可能源于
      • 1)V-trace Off-policy 校正的作用类似于广义优势估计 (2016)
      • 2)异步数据收集产生了更多样化的经验批次
  • 除了达到更好的最终性能外,IMPALA 对超参数选择的鲁棒性也比 A3C 更强
  • 图 4 比较了上述方法在不同超参数组合下的最终性能,这些组合按平均最终回报从高到低排序
    • IMPALA 在更多的组合上取得了更高的分数
V-trace 分析 (V-trace Analysis)
  • 为了分析 V-trace,论文研究了四种不同的算法:
    • 1. 无校正 (No-correction) : 无 Off-policy 校正
    • 2. \(\varepsilon\)-校正 (\(\varepsilon\)-correction) :在梯度计算期间添加一个小的常数值(\(\varepsilon=1e-6\)),以防止 \(\log\pi(a)\) 变得非常小并导致数值不稳定,类似于 (2016)
    • 3. 1-step 重要性采样 (1-step importance sampling) :优化 \(V(x)\) 时不进行 Off-policy 校正
      • 对于策略梯度,将每个时间步的优势(advantage)乘以相应的重要性采样权重
      • 此变体类似于没有“迹(traces)”的 V-trace,包含它是为了研究“迹”在 V-trace 中的重要性
    • 4. V-trace :如第 4 节所述
  • 对于 V-trace 和 1-step 重要性采样,论文将每个重要性权重 \(\rho_{t}\) 和 \(c_{t}\) 裁剪为 \(1\)(即 \(\bar{c}=\bar{\rho}=1\))
    • 这降低了梯度估计的方差但引入了偏差
    • 在 \(\bar{\rho}\in[1,10,100]\) 中,论文发现 \(\bar{\rho}=1\) 效果最好
  • 论文在上一节的 5 个 DeepMind Lab 任务集上评估了所有算法
    • 论文还在学习器上添加了一个经验回放缓冲区,以增加 \(\pi\) 和 \(\mu\) 之间的 Off-policy 差距
    • 在经验回放实验中,论文从回放缓冲区中均匀随机抽取每批中 50% 的项目
  • 表 2 分别显示了每种算法在有回放和无回放情况下的最终性能
  • 在无回放设置中,V-trace 在 5 个任务中的 3 个上表现最佳,其次是 1-step 重要性采样、\(\varepsilon\)-校正和无校正
    • 尽管 1-step 重要性采样在无回放设置中表现与 V-trace 相似,但在使用经验回放时,在 5 个任务中的 4 个上差距扩大了
      • 这表明,当目标策略和行为策略偏离更严重时,粗糙的 1-step 重要性采样近似变得不足
    • 还要注意,V-trace 是唯一一个始终受益于添加经验回放的变体
    • \(\varepsilon\)-校正 在两个任务上比无校正有显著改进,但远远落后于基于重要性采样的方法,特别是在使用经验回放的更 Off-policy 的设置中
    • 图 E.1 显示了更详细分析的结果
    • 图 E.2 显示基于重要性采样的方法在所有超参数下也表现更好,并且通常更鲁棒

多任务训练 (Multi-Task Training)

  • IMPALA 的高数据吞吐量和数据效率使论文不仅可以在一个任务上训练,还可以在多个任务上并行训练,只需对训练设置进行最小更改
  • 论文没有在所有执行器上运行相同的任务,而是将固定数量的执行器分配给多任务套件中的每个任务
  • 注意,模型不知道它正在被训练或评估的是哪个任务
DMLab-30
  • 为了测试 IMPALA 在多任务设置中的性能,论文使用 DMLab-30,这是一个基于 DeepMind Lab 构建的包含 30 个多样化任务的集合
  • 该套件中的众多任务类型包括具有自然外观地形的视觉复杂环境、基于指令的接地语言任务 (2017)、导航任务、认知任务 (2018) 以及以脚本机器人作为对手的第一人称标签任务
  • DMLab-30 和任务的详细描述可在 github.com/deepmind/lab 和 deepmind.com/dm-lab-30 获取
  • 论文比较了多种 IMPALA 变体与分布式 A3C 实现
    • 除了使用基于群体的训练 (Population-Based Training, PBT) (2017a) 的智能体外,所有智能体都在附录 D.1 给出的相同范围内进行了超参数扫描
    • 论文报告了平均上限人类标准化分数(mean capped human normalised score),其中每个任务的分数上限为 100%(见附录 B)
    • 使用平均上限人类标准化分数强调了解决多个任务的需要,而不是专注于在单个任务上变得超人类
    • 对于 PBT,论文使用平均上限人类标准化分数作为适应度函数,并调整熵成本、学习率和 RMSProp \(\varepsilon\)
    • PBT 设置的具体细节见附录 F
  • 具体来说,论文比较了以下智能体变体
    • A3C,deep ,一个具有 210 个工作者(每个任务 7 个)的分布式实现,采用深度残差网络架构(图 3(右))
    • IMPALA,shallow 具有 210 个执行器
    • IMPALA,deep 具有 150 个执行器,两者都使用单个学习器
    • IMPALA,deep,PBT ,与 IMPALA,deep 相同,但额外使用 PBT (2017a) 进行超参数优化
    • IMPALA,deep,PBT,8 learners ,它利用 8 个学习器 GPU 来最大化学习速度
  • 论文还在专家设置中训练了 IMPALA 智能体,IMPALA-Experts,deep ,其中每个任务训练一个单独的智能体
    • 在这种情况下,论文没有为每个任务单独优化超参数,而是在训练 30 个专家智能体的所有任务上进行了优化
  • 表 3 和图 5 显示所有 IMPALA 变体的性能都远优于深度分布式 A3C
    • 此外,深度 IMPALA 变体不仅在最终性能上优于浅层网络版本,而且在整个训练过程中都表现更好
    • 注意在表 3 中, IMPALA,deep,PBT,8 learners 虽然提供了更高的吞吐量,但在相同步数下达到了与 1 GPU 的 IMPALA,deep,PBT 相同的最终性能
  • 特别地,在每个任务上单独训练的IMPALA-Experts 与同时在所有任务上训练的 IMPALA,deep,PBT 之间的差距
    • 如图 5 所示,多任务版本在整个训练过程中都优于IMPALA-Experts ,附录 B 中的个体分数细分显示在语言任务和激光标签任务等任务上存在正向迁移(positive transfer)
  • 将 A3C 与 IMPALA 在挂钟时间(wall clock time)上进行比较(图 6)进一步凸显了两种方法之间的可扩展性差距
    • 使用 1 个学习器的 IMPALA 仅需约 10 小时即可达到 A3C 在 7.5 天后才接近的性能
    • 使用 8 个学习器 GPU 而不是 1 个,将深度模型的训练速度进一步提高了 7 倍,达到 210K 帧/秒,高于原来的 30K 帧/秒
Atari
  • Atari 学习环境 (ALE) (2013a) 是大多数近期深度强化学习智能体的测试平台
    • Atari 中的 57 个任务提出了具有挑战性的强化学习问题,包括探索、规划、反应性游戏和复杂的视觉输入
    • 大多数游戏具有非常不同的视觉效果和游戏机制,这使得该领域对多任务学习尤其具有挑战性
  • 论文在每个游戏上单独训练 IMPALA 和 A3C 智能体,并使用第 5 节介绍的深度网络(不含 LSTM)比较它们的性能
  • 论文还提供了使用浅层网络的结果,该网络等效于 (2016) 中使用的前馈网络,包含三个卷积层
    • 该网络通过在每个步骤堆叠最近的 4 个观察值来提供短期历史信息
    • 有关预处理和超参数设置的详细信息,请参阅附录 G
  • 除了使用固定超参数集训练 2 亿帧的个体每游戏专家外,论文还训练了一个 IMPALA Atari-57 智能体(一个智能体,一组权重),同时在所有 57 个 Atari 游戏上训练,每个游戏 2 亿帧,总计 114 亿帧
  • 对于 Atari-57 智能体,论文使用群体大小为 24 的基于群体的训练,在整个训练过程中调整熵正则化、学习率、RMSProp \(\varepsilon\) 和全局梯度范数裁剪阈值
  • 论文比较了所有算法在 57 个 Atari 游戏上的中位数人类标准化分数
    • 评估遵循标准协议,每个游戏分数是 200 个评估回合的平均值,每个回合开始时执行随机数量的无操作动作(从 [1, 30] 中均匀选择)以对抗 ALE 环境的确定性
  • 如表 4 所示,IMPALA 专家在深度和浅层配置下都提供了比其 A3C 对应物更好的最终性能和数据效率
    • 正如在论文的 DeepMind Lab 实验中一样,深度残差网络比浅层网络导致更高的分数,与使用的强化学习算法无关
    • 浅层 IMPALA 实验在不到一小时内完成了超过 2 亿帧的训练
  • 作者特别强调,IMPALA, deep, multi-task ,一个同时在所有 57 个 ALE 游戏上训练的单一智能体,达到了 59.7% 的中位数人类标准化分数
    • 尽管 ALE 套件内的视觉外观和游戏机制具有高度多样性,IMPALA 多任务版本仍然设法与相关工作中常用作基线的 A3C, shallow, experts 保持竞争力
    • ALE 通常被认为是一个困难的多任务环境,常常伴随着任务间的负迁移(negative transfer)(2016)
    • 据论文所知,IMPALA 是第一个在 ALE 所有 57 个游戏的多任务设置下进行训练、并能与标准专家基线竞争的智能体

Conclusion

  • 论文引入了一种新的高度可扩展的分布式智能体 IMPALA 以及一种新的 Off-policy 学习算法 V-trace
    • 凭借其简单但可扩展的分布式架构,IMPALA 能够高效地利用小规模和大规模场景下的可用计算资源
    • 这直接转化为研究新想法时非常快的周转时间,并开启了未被探索的机会
  • V-trace 是一种通用的 Off-policy 学习算法,与其他用于 Actor-Critic 智能体的 Off-policy 校正方法相比,它更加稳定和鲁棒
  • 论文已经证明,在数据效率、稳定性和最终性能方面,IMPALA 实现了比 A3C 变体更好的性能
  • 论文进一步在新的 DMLab-30 任务集和 Atari-57 任务集上评估了 IMPALA
  • 据论文所知,IMPALA 是第一个在此类大规模多任务设置中成功测试的深度强化学习(Deep-RL)智能体,并且与基于 A3C 的智能体相比,它显示出卓越的性能(在 DMLab-30 上,标准化人类分数为 49.4% 对比 23.8%)
  • 最重要的是,论文在 DMLab-30 上的实验表明,在多任务设置中,个体任务之间的正向迁移(positive transfer)使得 IMPALA 实现了比专家训练设置更好的性能
  • 作者相信,IMPALA 为构建更好的深度强化学习智能体提供了一个简单、可扩展且鲁棒的框架,并具有激发新挑战研究的潜力

附录:【待补充】

  • 补充材料(附录):IMPALA Supplemental Material
1…252627…66
Joe Zhou

Joe Zhou

Stay Hungry. Stay Foolish.

659 posts
53 tags
GitHub E-Mail
© 2026 Joe Zhou
Powered by Hexo
|
Theme — NexT.Gemini v5.1.4