XcloveHsy's Blog

【RL】Actor&Critic 结合价值与策略学习 同时对最优Q值以及最优策略进行学习，最终策略网络的输出即为最优动作。 Actor网络（策略网络）\(\pi(a|s;\theta)\)，近似\(Policy\ \pi\)控制Agent做动作，利用Policy Gradient训练网络 Critic网络（价值网络）\(Q_\pi(a,s;w)\)对策略进行评价。通过TD Learning训练网络 image-20231205150114928 特点: 策略梯度方法和价值估计方法的结合； 直接的得到最优动作； 动作空间既可以是离散的，也可以是连续的。 Actor&Critic State-value function: \(V_\pi(s)=\sum_a \pi(a \mid s) \cdot Q_\pi(s, a) \approx \sum_a \pi(a \mid s ; \boldsymbol{\theta}) \cdot q(s, a ; \mathbf{w}) .\) \(\pi(a|s)\) 是策 ...

【RL】Policy-Based Learning 基于策略学习 思想：直接对最优策略进行估计。 随机性策略：对状态到最优动作概率分布之间的映射进行估计，然后从该概率分布中进行采样得到输出动作。 确定性策略： 直接对状态到最优动作之间的映射进行估计。 算法特点：神经网络的输出即为最优动作，动作空间既可以是离散的也可以是连续的。 直接输出动作的最大好处就是, 它能在一个连续区间内挑选动作, 而基于值的, 比如 Q-learning, 它如果在无穷多的动作中计算价值, 从而选择行为, 这, 它可吃不消. 核心内容 利用策略网络\(\pi(a|s;\theta)\)去近似价值函数\(\pi(a|s)\) Agent根据策略网络的输出，概率抽样选择Action \(a_t \sim \pi\left(\cdot \mid s_t\right)\) 通过策略梯度（Policy Gradient）寻览策略网络 策略梯度算法通过最大化\(\mathbb{E}_s[V(s;\theta)]\)，训练网络参数 image-20231205120520822 ...

【RL】Value-Based Learning 基于价值学习 Discounted Return \[ \begin{aligned} U_t& =R_t+\gamma\cdot R_{t+1}+\gamma^2\cdot R_{t+2}+\gamma^3\cdot R_{t+3}+\gamma^4\cdot R_{t+4} \\ & =R_t+\gamma\cdot (R_{t+1}+\gamma^2\cdot R_{t+2}+\gamma^3\cdot R_{t+3}+\gamma^4\cdot R_{t+4}) \\ & =R_t+\gamma\cdot U_{t+1} \end{aligned} \] Identity: \(U_t=R_t+\gamma\cdot U_{t+1}\) TD Target Assume \(R_t\) depends on \((S_t, A_t, S_{t+1})\) \[ \begin{aligned} Q_\pi\left(s_t, a_t\right) & =\mathbb ...

【RL】基本概念 概率统计 随机变量：一个未知的量，它的值取决于一个随机事件的结果。 概率密度函数：随机变量在某个确定的取值点附近的可能性（连续概率分布 & 离散概率分布） 期望：连续分布（p(x)和f(x)的乘积做定积分） & 离散分布（对p(x)和f(x)的乘积进行连加） 随机抽样： from numpy.random import choice / sample = choice(['a','b','c'], size=100, p=[0.2,0,5,0,3]) 简介 基本概念 监督学习： 用于处理分类与回归问题，这类问题的任务是对输入X与输入Y之间的映射关系进行拟合，从而对不同X对应的Y进行预测 强化学习：用于求解序列决策问题，这一类问题的任务是求解一个策略用于指导机器在不同状态下选择最佳动作。 核心思想：强化学习的做法是让机器自行对动作进行探索，然后根据环境的反馈，不断地对策略进行调整，最终目标是使得环境收益尽可能地大。 image-20231205150300996 State & Action ...

Leetcode-n皇后 题目描述 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 示例 image-20240731172857954 输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。 1 <= n <= 9 思路 经典的回溯问题。 定义数组Q存储已经放皇后的位置\((i, Q[i])\) 根据row进行回溯，判断皇后放在\([1,n]\) col是否有效，执行路径如下： image-20240731173548183 AC代码 12345678910111 ...

动态规划 背包问题 0-1背包 转移方程：\(dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]]+w[i])\) 12345678910int v[N], w[N], dp[N][N];int n, m;// dp[i][j] 为考虑1-i个物品，背包容积为j时的最大价值for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(j >= v[i]) dp[i][j] = max(dp[i-1][j-v[i]]+w[i], dp[i-1][j]); else dp[i][j] = dp[i-1][j]; }} 在计算 \(dp[i][j]\) 时，只会用到\(dp[i-1][j]\)，不会用到比\(i\)更早的状态。 因此可以考虑因此可以去掉第一个维度，反复利用同一个一维数组。 转移方程：$dp[j] = max(dp[j], dp[i-1][j-v[i]]+w[i]) $ 1 ...

搜索与图论 树和图的存储 树是一种特殊的图，与图的存储方式相同。 对于无向图中的边ab，存储两条有向边a->b, b->a。 因此我们可以只考虑有向图的存储。 邻接矩阵：g[a][b] 存储边a->b 邻接表 (前向星)： 1234567891011121314151617181920const int N = 1e5+10;struct Node{ int to, ne, w; }node[N*2];int head[N], idx;// 添加一条边 a -w-> bvoid addEdge(int a, int b, int w){ node[idx].to = b; node[idx].ne = head[a]; node[idx].w = w; head[a] = idx++;}// 初始化idx = 0;memset(head, -1, sizeof(head)); 树与图的遍历 时间复杂度 O(n+m) n 表示点数， m表示边数 深度优先遍历 ...

STL技巧 vector数组 变长数组，倍增的思想 12345678size() 返回元素个数empty() 返回是否为空clear() 清空front()/back()push_back()/pop_back()begin()/end()[]\\ 支持比较运算，按字典序 pair<int, int>二元组 123first, 第一个元素second, 第二个元素支持比较运算，以first为第一关键字，以second为第二关键字（字典序） string字符串 12345size()/length() 返回字符串长度empty()clear()substr(起始下标，(子串长度)) 返回子串c_str() 返回字符串所在字符数组的起始地址 queue队列 123456size()empty()push() 向队尾插入一个元素front() 返回队头元素back() 返回队尾元素pop() 弹出队头元素 priority_queue优先队列 默认是大根堆 123456size()empty()push() \\ 插入一个元素top() ...

数据结构 单调栈（Monotone Stack） 常见模型：找出每个数左边离它最近的比它大/小的数 单调递增栈 保证栈内元素单调递增。（从栈顶到栈底） 只有比栈顶大的元素才能直接进栈 首先先将栈中比当前元素大的元素出栈 出栈时，新元素是出栈元素向后找第一个比其小的元素 所有出栈后，栈顶元素是新元素向前找第一个比其小的元素 再将当前元素出栈 123456789101112stack<int> st;for(int i = 0; i < n; i++){ while(!st.empty() && st.top >= nums[i]){ // 判断栈顶是否符合单调递增关系 // 新元素是出栈元素向后找第一个比其小的元素 st.pop(); } // 栈顶元素是新元素向前找第一个比其小的元素 st.push(nums[i]); // 具体逻辑.. } 830. 单调栈 - AcWing题库 单调递减栈 ...

基础算法 常用头文件 1234567891011121314151617181920212223#include<algorithm>#include<bitset>#include<cctype>#include<climits>#include<cmath>#include<cstdio>#include<cstring>#include<deque>#include<iostream>#include<map>#include<queue>#include<set>#include<stack>#include<string>#include<vector>#include<unordered_map>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair <int, ...