RL——CMDP拉格朗日乘子更新思考

注：这是一个简单的思考随记，不严谨，以后有时间还需完善

整体背景说明

对下面约束优化问题：
$$
\begin{align}
\max_{a_t}\sum_{i=1}^M \sum_{a_t=1}^{N_t} x_{i,a_t} {Value}_{i,a_t} \\
s.t. \sum_{i=1}^M \sum_{a_t=1}^{N_t} x_{i,a_t} {Cost}_{i,a_t} \leq C_t \\
\sum_{a_t=1}^{N_t}x_{i,a_t} \leq 1, \ \ \forall i \\
x_{i,a_t} \in {0, 1}, \ \ \forall i,a_t
\end{align}
$$
可以求得其最优动作为（真实场景不一定是下面的形式，可以是任意形式的最优解，不影响 $\lambda$ 的更新）：
$$x^* = \mathop{\arg\max}_x f(x) - \lambda x$$
- 注：为了简化，这里将价值改为与算力有关的函数，其中 $f(\cdot)$ 是非减函数（单调不减函数），对应原始式子中的价值 $Value$
- 这里的 $x$ 是一个示意，可看做是算力
证明：仅需满足 $f(\cdot)$ 是非减函数（即价值随算力是单调不减的，不需要满足 RL-MPCA 论文中所说的价值边际收益递减假设），则拉格朗日乘子 $\lambda$ 的更新公式就可以定义为：
$$\lambda^{k+1} = \lambda^{k} + \eta(\hat{C} - C)$$
为简化，本文不再赘述论文内容描述，更多相关概念和原始问题定义需要结合论文查看

关于 adaptive-$\lambda$ 更新方式的另一种证明

说明：自适应 $\lambda$, 即 adaptive-$\lambda$，是 RL-MPCA 论文提出的方法，和 RCPO 方法的更新方式本质相同，证明形式不完全一致
论文证明目标 ：当 $f(\cdot)$ 是非减函数时，可使用 $\lambda^{k+1} = \lambda^{k} + \eta(\hat{C} - C)$ 来更新 $\lambda$
最优动作解读：$x^* = \mathop{\arg\max}_x f(x) - \lambda x$（其中 $x$ 是算力， $f(x)$ 是价值）的场景
仅需证明 ：当 $\lambda$ 提升时，最优解对应的价值和成本都会降低即可
形式化证明目标 ：$\forall \ \lambda_2 \gt \lambda_1$，有 $x^*(\lambda_2) \le x^*(\lambda_1)$ 且 $f(x^*(\lambda_2)) \le f(x^*(\lambda_1))$（其中 $x^*(\lambda_0)$ 和 $f(x^*(\lambda_0))$ 分别表示 $\lambda = \lambda_0$ 时的最优算力 $x^*$ 和价值 $f(x^*)$）
- 证明步骤1 ：$\lambda_2 \gt \lambda_1$ 时， $x^*(\lambda_2) \le x^*(\lambda_1)$ 成立
  - 设 $x^*(\lambda_1) = x_1$，则，按照最优性，有任取 $x_2 \ge x_1$，都满足 $f(x_1) - \lambda_1 x_1 \ge f(x_2) - \lambda_1 x_2$ 成立
  - 在 $x_2 \ge x_1$ 下，继续取 $\lambda_2 \gt \lambda_1$ 时，有 $f(x_1) - \lambda_2 x_1 \ge f(x_2) - \lambda_2 x_2$ 也成立，证明如下：
    - 由 $x_2 \ge x_1$ 且 $\lambda_2 \gt \lambda_1$ 可得 $- (\lambda_2 - \lambda_1)x_1 \ge - (\lambda_2 - \lambda_1) x_2$，所以所有 $f(x_1) - (\lambda_2 - \lambda_1) x_1 - \lambda_1 x_1 \ge f(x_2) - (\lambda_2 - \lambda_1) x_2 - \lambda_1 x_2$
  - $f(x_1) - \lambda_2 x_1 \ge f(x_2) - \lambda_2 x_2$ 等价于说： $\lambda_2$ 对应的最优算力不可能比 $x_1$ 更大 ，于是推出：
    - $\forall \ \lambda_2 \gt \lambda_1$， $\lambda_2$ 下的最优解 $x^*(\lambda_2)$ 不可能大于 $x^*(\lambda_1)$
- 证明步骤2 ：由于 $\lambda_2 \gt \lambda_1$ 时， $x^*(\lambda_2) \le x^*(\lambda_1)$ 成立，所以，当 $\lambda$ 减少时（从 $\lambda_2$ 变成 $\lambda_1$ ）时，有：
  - $x^*(\lambda_1) \ge x^*(\lambda_2)$，即成本 $x$ 增加了
  - 此时除非收益也增加，即 $f(x^*(\lambda_1)) \gt f(x^*(\lambda_2))$，否则最优点不会动（不动时有 $f(x^*(\lambda_2)) = f(x^*(\lambda_1))$ ），也就是说， $f(x^*(\lambda_2)) \le f(x^*(\lambda_1))$ 一定成立
根据证明有如下推论：
- 由于最优算力 $x^*(\lambda)$ 和和最优收益 $f(x^*(\lambda))$ 和 $\lambda$ 均呈现负相关关系（不是严格单调）
  - 当 $\hat{C} > C$ 时，约束被违反了，需要增大 $\lambda$ 以增强算力约束，减少算力消耗
  - 当 $\hat{C} < C$ 时，约束指标还有一定提升空间，需要缩小 $\lambda$ 以提升收益，直到 $\lambda=0$ 为止，此时无法继续缩小 $\lambda$，最优解对应的算力可能仍然是 $\hat{C} < C$ 的（ $\lambda=0$ 时，原始约束是松约束，相当于没有这个约束）
故而可得 ：仅需满足 $f(\cdot)$ 是非减函数（即价值随算力是单调不减的，不需要满足 RL-MPCA 论文中所说的价值边际收益递减假设）即可使用 $\lambda^{k+1} = \lambda^{k} + \eta(\hat{C} - C)$ 来更新 $\lambda$ 以获取最优解
- 当 算力未用完时 ，减少 $\lambda$ ，可保证 最优收益增加（单调不减） ，是更优的；
- 当 算力用超时 ，增加 $\lambda$ ，可保证 最优点对应的成本降低 ，逐渐降低到满足成本约束，收益会降低，但这是满足算力约束而必要的
- 注：算力约束是松约束时，$\lambda = 0$，需要添加 clip 操作防止降低到负数

RL-MPCA 中的一些讨论

论文中对智能算力场景给定两个假设（价值随算力单调递增；边际收益递减）是参考了 DCAF 论文的假设，简化了证明过程。在这两个条件满足时，可以证明最优解一定且仅在 $\hat{C} = C$ 处，此时可以使用二分查找求解 $\lambda$ 或Batch Loss来找到最优模型参数（只有这种情况下可以使用这两种方法）
实际上，论文中可以不给定假设，也可以推导得到 $\lambda^{k+1} = \lambda^{k} + \eta(\hat{C} - C)$ 这样的更新公式，这样定义是方便在 4.1.2 𝜆 Correction in Offline Model Evaluation 中证明可以使用二分查找，有这个假设的情况下，正好使得 $\lambda^{k+1} = \lambda^{k} + \eta(\hat{C} - C)$ 更容易推导了（论文中使用的是容易推导的形式）
- 待讨论问题：按照上文的证明，证明二分查找似乎也不需要边际收益递减的假设了吧？

整体背景说明

关于 adaptive-\(\lambda\) 更新方式的另一种证明

RL-MPCA 中的一些讨论