基于嵌套优化的稀疏proximal强化学习算法
168 浏览量
更新于2024-08-27
收藏 1.4MB PDF 举报
本文主要探讨了在强化学习问题中，利用线性价值函数近似进行特征选择和政策评估时面临的挑战。高维特征向量和有限的样本数据可能导致过拟合和计算成本高昂的问题。为了解决这些问题，传统的思路是采用正则化方法，特别是L1正则化（也称为Lasso回归），它能够促使模型得到稀疏解，从而提升泛化性能。
作者们提出了一个高效且具有O(n^2)复杂度的在线算法，名为L1-RC（L1-Regularized Recursive Least Squares），它是在递归最小二乘（RLS）的基础上扩展的。L1-RC通过嵌套优化分解策略来处理问题，避免了直接最小化带有L1正则化的均方投影贝尔曼误差，这种方法在保持计算效率的同时，实现了特征选择与模型更新的有效结合。
在L1-RC算法的核心部分，作者引入了迭代细化（iterative refinement）技术，这是一种迭代优化过程，旨在逐步逼近优化目标。通过这种策略，L1-RC能够在每个时间步都找到更优的解决方案，确保了学习过程中的稳定性和准确性。此外，L1-正则项在算法中起到了关键作用，不仅促进了模型的稀疏性，还降低了对噪声数据的敏感性，提高了学习算法的鲁棒性。
总结来说，这篇研究论文提出了一个新颖的强化学习框架——L1-RC，它结合了嵌套优化和L1正则化，有效地解决了高维特征和数据稀缺带来的问题，提升了模型的泛化能力和计算效率。这对于实际应用中的在线决策问题、资源管理和控制任务具有重要的理论和实践意义。未来，研究人员可能会进一步探索如何将这种方法扩展到非线性价值函数或深度学习架构，以适应更复杂的环境和任务。
This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
SONG et al.: SPARSE PROXIMAL RL VIA NESTED OPTIMIZATION 3
transition (s, a, r, s
), the sample matrices are defined as
˜
≡
⎡
⎢
⎣
φ
T
1
.
.
.
φ
T
m
⎤
⎥
⎦
,
˜
≡
⎡
⎢
⎣
φ
T
1
.
.
.
φ
T
m
⎤
⎥
⎦
and
˜
R ≡
⎡
⎢
⎣
r
1
.
.
.
r
m
⎤
⎥
⎦
(4)
and we obtain an empirical version of (3)asfollows:
θ = u
∗
= arg min
u∈R
n×1
˜
u −
˜
R + γ
˜
θ
2
. (5)
The derivation from (3)to(5) can be referred to [20] and [22].
It has been proved that with m →∞, the fixed-point of (5)
approaches that of (3) with probability one.
A least squares problem orthogonally projects θ back to F
as a new fixed-point θ
∗
. We can solve fixed-point θ
∗
in the
following nested optimization problem [28], [33], [34]:
⎧
⎪
⎨
⎪
⎩
u
∗
= arg min
u∈R
n×1
˜
u −
˜
R + γ
˜
θ
2
2
θ
∗
= arg min
θ∈R
n×1
˜
θ −
˜
u
∗
2
2
.
(6)
The first step of (6) is to minimize the OPE and the second
is to minimize the FPE. In this paper, we refer to these two
steps as projection step and fixed-point step as in [28].
Given a fixed θ , the closed-form solution to u
∗
in the
projection step of (6) can be found as follows:
u
∗
= arg min
u∈R
n×1
˜
u −
˜
R + γ
˜
θ
2
2
=
˜
T
˜
−1
˜
T
˜
R + γ
˜
θ
. (7)
By substituting (7) into the fixed-point step in (6) and setting
θ = u, the nested optimization problem in (6) is changed to the
following optimization problem to minimize the mean-square
projected Bellman error (MSPBE):
u
∗
= arg min
u∈R
n×1
˜
u −
˜
˜
T
˜
−1
˜
T
˜
R + γ
˜
u
2
2
. (8)
Equation (8) is an empirical version, and it can be derived by
substituting (4) into the original definition of MSPBE in [8]:
MSPBE(θ) = 1/2V
θ
−TV
θ
2
D
, and = (
T
D)
−1
T
D
is the Bellman projection operator.
In [28], two schemes of
1
-regularization problem are
proposed, termed L
1
and L
21
. The difference lies in, where to
place the
1
penalty. L
21
scheme that places
1
penalty in the
fixed-point step forms a solvable Lasso problem by
1
solvers;
whereas, the
2
penalty in the projection step keeps the pro-
jection matrix nonsingular, but the effects on the algorithm
is not entirely clear. For these reasons, we choose the nested
optimization problem scheme that has an
1
penalty in the
fixed-point step. Differently, we use iterative refinement [36]
instead of the
2
penalty to keep the projection matrix nonsin-
gular, and ensure that the result of the projection step converge
to the unbiased solution. The nested optimization problem in
this paper is proposed as
⎧
⎪
⎨
⎪
⎩
u
∗
= arg min
u∈R
n×1
1
2
˜
u −
˜
R + γ
˜
θ
2
2
θ
∗
= arg min
θ∈R
n×1
1
2
˜
θ −
˜
u
∗
2
2
+ β
1
θ
1
(9)
Fig. 1. Graphical illustration of the proposed nested optimization problem.
where β
1
∈ R
+
is an
1
-regularization parameter. An equiv-
alent nested optimization problem of (9) including MSPBE
in (8) can be obtained as follows:
⎧
⎪
⎪
⎨
⎪
⎪
⎩
u
∗
= arg min
u∈R
n×1
1
2
˜
u −
˜
˜
T
˜
−1
˜
T
˜
R + γ
˜
θ
2
2
θ
∗
= arg min
θ∈R
n×1
1
2
˜
θ −
˜
u
∗
2
2
+ β
1
θ
1
.
(10)
We see that the nested optimization in (10) contains a sub-
problem minimizing MSPBE and a subproblem minimizing
a Lasso problem. Both subproblems are relatively easier to
solve than MSPBE with
1
-regularization. The equivalency
of (9) and (10) can be proved as follows. By substituting (7)
into the fixed-point step in (9) and setting θ = u, the fixed
point of (9) can be obtained as
θ
∗
= arg min
θ∈R
n×1
˜
θ −
˜
˜
T
˜
−1
˜
T
˜
R + γ
˜
θ
2
2
+ β
1
θ
1
. (11)
Also we can substitute the closed-form solution to projection
step in (10) into the corresponding fixed-point step as follows:
u
∗
= arg min
u∈R
n×1
˜
u −
˜
˜
T
˜
−1
˜
T
˜
R + γ
˜
θ
2
2
=
˜
T
˜
−1
˜
T
˜
˜
T
˜
−1
˜
T
˜
R + γ
˜
θ
θ
∗
= arg min
θ∈R
n×1
˜
θ −
˜
u
∗
2
2
+ β
1
θ
1
= arg min
θ∈R
n×1
˜
θ −
˜
˜
T
˜
−1
˜
T
˜
˜
T
˜
−1
˜
T
˜
R + γ
˜
θ
2
2
+ β
1
θ
1
= arg min
θ∈R
n×1
˜
θ −
˜
˜
T
˜
−1
˜
T
˜
R + γ
˜
θ
2
2
+ β
1
θ
1
. (12)
We choose the nested optimization problem in (10)asthe
regularization scheme in this paper. The graphical illustration
of this problem is shown in Fig. 1.
With a more generalized meaning, an elastic net
penalty [37] can be used
p
en
(
θ
)
≡ β
1
θ
1
+ β
θ
2
2
= β
1
θ
1
+ μ/β
1
θ
2
2
(13)
where β
2
∈ R
+
is an
2
-regularization parameter, μ ∈ R
+
is tradeoff weight between
2
and
1
penalties. The value of
剩余12页未读，继续阅读
2019-04-12 上传
2017-02-01 上传
2021-02-22 上传
2021-02-09 上传
2021-02-11 上传
2021-02-11 上传
2021-02-08 上传
2022-07-14 上传
2021-02-08 上传
2021-02-09 上传
weixin_38623249
- 粉丝: 10
- 资源: 957
我的内容管理
展开
最新资源
- NIST REFPROP问题反馈与解决方案存储库
- 掌握LeetCode习题的系统开源答案
- ctop：实现汉字按首字母拼音分类排序的PHP工具
- 微信小程序课程学习——投资融资类产品说明
- Matlab犯罪模拟器开发：探索《当蛮力失败》犯罪惩罚模型
- Java网上招聘系统实战项目源码及部署教程
- OneSky APIPHP5库：PHP5.1及以上版本的API集成
- 实时监控MySQL导入进度的bash脚本技巧
- 使用MATLAB开发交流电压脉冲生成控制系统
- ESP32安全OTA更新：原生API与WebSocket加密传输
- Sonic-Sharp: 基于《刺猬索尼克》的开源C#游戏引擎
- Java文章发布系统源码及部署教程
- CQUPT Python课程代码资源完整分享
- 易语言实现获取目录尺寸的Scripting.FileSystemObject对象方法
- Excel宾果卡生成器：自定义和打印多张卡片
- 使用HALCON实现图像二维码自动读取与解码
