[RL Note] 马尔可夫决策过程
1. 马尔可夫决策过程 前文中的$k$ 臂赌博机问题具有一些局限性：每次选择动作时的环境都是相同的，最优的动作保持不变，而且历史上作出的选择并不会影响到当前选择的动作的收益。在实际问题中，面对不同环境往往需要作出不同的选择，当下选择的动作会带来更长远的影响——影响未来环境（状态）和收益。 马尔可夫决策过程（Markov decision processe，MDP）给出了序列决策问题的一个更…
Read more
[RL Note] 基于置信度上界的动作选择
由于我们使用收益的样本来估计动作的价值，因此在估计中存在不确定性。通过试探可以降低估计的不确定性，从而在未来做出更好的选择。前文提到的 $\varepsilon$ – 贪心算法以一定概率进行探索，即随机地选择动作，这是一种盲目的选择。一种更好的试探的方法是，选择最有潜力的非贪心动作。衡量一个动作有多大“潜力”，需要考量这个动作的估计有多接近最大值，以及估计的不确定性（置信区间）。 …
Read more
[RL Note] 乐观初始值
1. 乐观初始值 在前文提到的学习算法中，如果一个动作 $a$ 从未被选择过，我们就无法根据历史数据去估计该动作的价值 $Q_t(a)$，此时需要为动作价值的估计设置一个初始值 $Q_1(a)$。这使得每个动作价值估计的初始值变成了一个需要配置的参数，通过选择合适的初始值，可以对试探和开发进行平衡。 使用乐观的初始值有利于试探。如果动作价值估计的初始值大于动作的真实价值，则在学习的初期，选…
Read more
[RL Note] 试探和开发
1. 开发和试探的冲突 通过估计各个动作的价值，在每一时刻都至少有一个动作具有最大的估计价值。选择具有最大估计价值的动作，即贪心动作，是开发（Exploitation）利用了历史上关于动作价值的知识，选择了距今为止表现最好的动作，以期最大化收益。 如果没有选择贪心动作，则称进行了试探（Expolration），通过尝试非贪心动作并记录其收益，可以改善对非贪心动作的价值的估计。试探没有选择当…
Read more
[RL Note] 动作价值估计的增量更新
1. 增量计算平均值 前文给出的估计动作价值的方法，需要保存所有历史数据，即历史上观测到的动作收益。这一计算实际上可以通过增量地方式更有效地进行。 考虑一个特定动作 $a$，记 $R_i$ 为这一动作被选择 $i$ 次后获得的收益，$Q_n$ 表示选择该动作 $n-1$ 次后对动作价值的估计，则 \begin{equation} Q_n \doteq \frac{R_1 + R_2 + \…
Read more
[RL Note] K 臂赌博机
1. 问题描述 $k$ 臂赌博机问题指的是在一个具有 $k$ 个拉杆的老虎机上进行赌博，每次赌博可以选择拉动一个拉杆，然后会得到一定的奖金收益。每个拉杆所带来的收益分布可能是不同的。通过重复地赌博，玩家可以学会只拉动带来收益最高的拉杆，从而最大化收益。 更一般的，$k$ 臂赌博机问题指的是重复地在 $k$ 个动作中进行选择，每次动作后会得到一定的收益，收益由所选动作决定的平稳概率分布产生。…
Read more
[DL Note] 概率论：常用概率分布
1. 伯努利分布 对于结果只有成功或失败的试验，令 \begin{equation} X= \begin{cases} 1 & 当试验结果为成功时 \\ 0 & 当试验结果为失败时 \end{cases} \end{equation} 则 $X$ 的分布列为 \begin{align} &p(0) = P\{X = 0\} = 1 …
Read more
[DL Note] 线性代数：行列式
行列式（determinant）将一个方阵映射到实数，方阵 $\boldsymbol A$ 的行列式记做 $\det A$，其值为 $\boldsymbol A$ 特征值的乘积。行列式的绝对值可以用来衡量一个矩阵经过矩阵乘法变换后扩大或缩小的情况。如果行列式为 $0$，则空间至少沿着某一维度完全收缩了，使其失去了所有的体积；如果行列式为 $1$，则变换保持空间体积不变。 可以使使用余因子展…
Read more
[DL Note] 线性代数：迹运算
迹（trace）运算 $\mathrm{Tr}$ 计算的是矩阵对角线元素的和，即 \begin{equation} \mathrm{Tr}(\boldsymbol A) = \sum_i A_{i, i} \tag{1} \end{equation} 矩阵的 Frobenius 范数可以通过迹运算表示为 \begin{equation} \Vert \boldsymbol A \Vert_F …
Read more
[DL Note] 线性代数：Moore-Penrose 伪逆
具有 $n$ 个未知数的 $m$ 个方程组成的线性方程组可以写成 \begin{equation} \boldsymbol A \boldsymbol x = \boldsymbol y \tag{1} \end{equation} 其中 $\boldsymbol A$ 是 $m \times n$ 矩阵。我们希望通过 $\boldsymbol A$ 的左逆 $\boldsymbol B$ 来…
Read more