是一种文件格式
json object和python的字典差不多。
json在python中可以以字符串形式读入。
json.loads()从内存中读取。
1 | import json |
json.load()从文件对象中读取。
假设有名为person.json的json文件
1 | { |
直接从文件对象中读取
1 | import json |
json.dumps()将字典转化为JSON字符串
1 |
|
json.dump()直接将字典写入文件对象
1 | import json |
1 | import json |
这一节介绍和process相关的命令，包含ps,top,kill, pstree, nice, fuser, lsof, pidof, /proc/等
ps [-Aauf] [xlj]
-A 所有的进程全部显示出来
a 现行终端机下所有程序，包含其他用户
u 有效用户相关的进程，主要以用户为主的格式来区分
f 用ASCII字符显示树状结构，表达进程间的关系
x 通常与a这个参数一块使用，显示所有程序，不以终端机来区分
l 较长，较详细的将该PID的信息列出
j 工作的格式
~$:ps aux 查看系统所有的进程数据
~$:ps -lA 查看所有系统的数据
~$:ps axjf 连同部分进程树状态
~$:ps aux | grep ‘sslocal’ #查看sslocal程序是否运行
~$:ps ax # 显示当前系统进程的列表
~$:ps aux #显示当前系统进程详细列表以及进程用户
~$:ps -A #列出进程号
~$:ps aux |grep 2222’|grep -v grep # 找出所有包含2222的进程，grep -v 过滤掉含有grep字符的行
~$:ps aux # 使用BSD格式显示进程
输出
USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND
USER
PID
%CPU 该进程使用掉的CPU资源百分比
%MEM 该进程占用物理内存百分比
VSZ 该进程占用虚拟内存量
RSS 该进程占用固定内存量(KB)
TTY pts/0 表示由网络连接进主机的进程
STAT 进程状态
START 该进程被触发的时间
TIME CPU时间
COMMAND 该进程实际命令
僵尸进程(
~\$:ps -ef # 使用标准格式显示进程
输出
UID PID PPID C STIME TTY TIME CMD
UID 用户名
PID 进程ID
PPID 父进程ID
C CPU占用百分比
STIME 进程启动到现在的时间
TTY 在哪个终端上运行，ps/0表示网络连接
TIME
CMD 命令的名称和参数
~\$:ps -l #仅查看自己相关的bash进程
输出
F S UID PID PPID C PR NI ADDZ SZ WCHAN TTY TIME CMD
F 说明进程权限
S 进程状态STAT
R(running) S(sleep) D(不可被唤醒的睡眠状态,通常是IO的进程) T(stop) Z(zombie僵尸状态)进程已终止，但无法被删除到到内存外,PCB还在，但是其他资源全部被收回，是由父进程负责收回资源。
UID/PID/PPID
C CPU使用率
PR/NI Priority/Nice的缩写，此进程被CPU执行的优先级
ADDR/SZ/WCHAN都与内存有关，ADDR是kernel function ,指出该进程在内存的哪个部分，如果是个running的过程，显示-;SZ代表用掉多少内存;WCHAN表示目前进程是否运行，-表示正在运行
TTY 使用的终端接口
TIME 使用掉的CPU时间，而不是系统时间
CMD command缩写,造成此进程被触发的命令
top [-d 数字] | top [-bnp]
-d 整个进程界面更新的秒数
-b 以批次的方式执行top，
-n 与-b搭配，意义是，需要进行几次top的输出结果
-p 指定某个PID来查看
在top执行中可以使用的命令
?查询所有的命令
P 按CPU使用率排序
M Mem排序
N PID排序
T CPU累计时间排序
k 给某个PID一个信号
r 给某个PID重新制定一个nice值
q 离开top软件
~\$:top -d 2 #每两秒钟刷新一次top，默认为5s
~\$:top -b -n 2 > ~/tmp/top.out
第一行top
目前时间
开机到现在时间 up n days , hh:mm
登陆的用户
系统在1,5,15分钟时的负载，batch工作方式负载小于0.8即为这个负载，代表的是1,5,15分钟，系统平均要负责多少个程序。越小说明系统越闲
第二行task
目前进程总量，分别有多少个处于什么状态，不能有处于zombie的进程，
第三行%cpu
wa代表的是I/Owait，系统变慢都是由于I/O产生问题较多
第四五行内存和swap使用情况，swap被使用的应该尽量少，否则说明物理内存实在不足。
第六行
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
PID 每个进程ID
USER 该进程所属用户
PR Priority 进程的优先级顺序，越小越早被执行
NI Nice 与Priority有关，越小越早被执行
VIRT
RES
SHR
S STAT
%CPU CPU使用率
%MEM 内存使用率
TIME+ CPU使用时间的累加
COMMAND
pstree [-A|-U] [-up]
-A 各进程树直接以ASCII字符连接
-U 各进程树之间以utf-8字符连接
-u 显示进程所属账号名
-p 显示pid
~\$:pstree -Aup
kill -signals %jobnumber 杀掉某个job
-l 列出所有signal
-1 重新读取一次参数的配置文件
-2 与ctrl+c 一样
-9 强制删除一个job，非正常状态
-15 让一个job正常结束
~\$:man 7 signal
kill -signal %jobnum
kill -signal pid
这两种情况是不同的，第一种是job，第二种是pid,不能弄混
killall [-iIe] 用来删除某个服务
-i iteractive
-e exact
-I 忽略大小写
~\$:killall utserver
~\$:killall -1 syslogd
~\$:killall -9 httpd
~\$:killall -i -9 bash
PRI(priority)与NI(nice)
PRI值是由内核动态调整的，用户无法直接调整PRI值
PRI(new)=PRI(old)+nice
nice值虽然可以影响PRI，但是并不是说原来PRI为50,nice为5,就会让PRI变为55,
这是需要经过系统分析之后决定的
nice值
a.可调整范围为-20~19
b.root可随意调整任何人的nice值-20~19间的任意一个值
c.一般用户仅可以调整自己nice值，且范围在0~19
d.一般用户仅可将nice值调高，而无法降低
e.调整nice值的方法
新执行的命令手动设置nice值
nice -n [number] command
~\$:nice -n -5 vim &
renice [number] command
~\$:ps -l | grep ‘\*bash\$’
~\$:renice 10 \$(ps -l|grep ‘bash\$’ | awk ‘{print \$4}’)
fuser [-muv] [-k [i] [-signal]] name
-m 后面接的文件名会主动提到文件顶层
-u user
-v verbose
-k SIGKILL
-i 询问用户，与-k搭配
-signal -1,-15等，默认为-9
~\$:mount -o loop ubuntu.iso /mnt/iso
~\$:cd /mnt/iso
~\$:umount /mnt/iso
error
~\$:fuser -muv /mnt/iso
…
~\$:cd
~\$:umount /mnt/iso
~\$:fuser -muv /proc
~\$:fuser -ki /bin/bash
lsof [-uaU] [+d]
-a 相当于and连接符
-u 某个用户的相关进程打开的文件
-U Unix like 的socket文件类型
+d 某个目录下被打开的文件
~\$:lsof +d ~/Desktop
~\$:lsof -u mxx | grep ‘bash’
~\$:lsof -u mxx -a -U
pidof [-sx] program_name
-s 仅列出一个pid而不列出所有的pid
-x 列出该进程可能的ppid的pid
ps -A |grep “command” | awk '{print $1}'
pidof 'command’
pgrep ‘command’
/proc/cmdline 加载kernel执行的参数
/proc/cpuinfo CPU相关信息
/proc/devices 主要设备代号 与mknod相关
/proc/filesystems 目前已加载的文件系统
/proc/interrupts 系统上IRQ分配状态
/proc/ioports 目前系统上每个设备配置的I/O地址
/proc/loadavg top/uptime显示的负载
/proc/kcore 内存大写
/proc/meminfo free
/proc/modules 目前系统已加载的模块列表，可想成驱动程序
/proc/mounts mount
/proc/swaps 系统加载的内存使用的分区记录
/proc/partitions fdisk -l
/proc/pci PCI总线上每个设备的详细情况 lspci
/proc/uptime uptime
/proc/version 内核版本 uname -a
/proc/bus/\* 总线设备，USB设备
如passwd，当触发passwd之后，会取得一个新的进程与PID,该PID产生时通过SUID给予该PID特殊的权限设置。
在一个bash中执行passwd会衍生出一个passwd进程，而且权限为root
~\$:passwd &
~\$:pstree -up找到该进程
1.《鸟哥的LINUX私房菜》基础篇
free [-bkmg] -t
-t 输出结果中显示free和swap加在一起的总量
free -h
1 | ~$:sudo dmidecode -t memory |grep "Number Of Devices" |awk '{print $NF}' # 卡槽数量 |
df -h 查看磁盘占用情况
du -h --max-depth=2 统计当前目录下深度为2的文件和目录大小
top
点击查看cpu信息命令
uname [-asrmpi]
-a 所有系统相关的信息，
-s 系统内核名称
-r 内核版本
-m 本系统硬件名称
-p CPU类型，与-m类似，显示的是CPU类型
-i 硬件平台
uptime
netstat [-atunlp]
-a 将目前系统上所有连接监听，socket列出来
-t 列出tcp网络数据包的数据
-u 列出udp网络数据包的数据
-n 不列出进程的服务名称，以端口号来显示
-l 列出目前正在网络监听(listen)的服务
-p 列出该网络服务的进程pid
~$:netstat -tnlp #找出目前系统上已经在监听的网络连接及其PID
dmesg | more
dmesg | grep -i 'sd’
dmesg | grep -i ‘eth’
man vmstat 查看各字段含义
vmstat 动态查看系统资源
vmstat [-a] display active and inactive memory
vmstat [-d] report sisk statistics
vmstat [-p 分区] Detailed statistics about partition
vmstat [-S 单位] B K M G
vmstat [-f] displays the num of forks since boot
~$:vmstat
~$:vmstat -a
~$:vmstat -p /dev/sda1
~$:vmstat -S M
~$:vmstat -f
1.《鸟哥的LINUX私房菜》
目的：有一些shell脚本的参数需要调整，在shell中处理有些麻烦，就用python控制参数，然后调用shell，问题就是如何将shell脚本的输出进行重定向。最开始我想直接用python调用终端中shell重定向的语法，我用的是os.system(command)，command包含重定向的命令，在实践中证明是不可行的。为什么？？？留待解决。
找到的解决方案是调用subprocess包，将要执行的命令存入一个list，将这个list当做参数传入，获得返回值，进行文件读写。这里拿ls命令举个例子，注意一点是，包含重定向语句的ls命令使用os.system()也能重定向成功，我使用的一个命令就不行了。
1 | subprocess.call(['ls', '-l', '.']) # 直接将程序执行结果输出，没有返回值。 |
1 | results = subprocess.Popen(['ls', '-l', '.'], |
1 | result = subprocess.run(['ls', '-l'], stdout=subprocess.PIPE) |
1.https://stackoverflow.com/questions/4760215/running-shell-command-and-capturing-the-output
2.https://linuxhandbook.com/execute-shell-command-python/
~/.bashrc文件详细内容，代码地址
1 | 使用alias给常用文件夹起别名 |
在.bashrc文件中会发现下面几行：
1 | if [ -f ~/.bash_aliases ]; then |
即.bashrc包含.bash_aliases文件。
.bash_aliases放置常用的命令别名。
关于vim详细介绍，可以查看linux-vim
vimrc文件如下，代码地址
1 | 使用四个空格代替tab键 |
1.《鸟哥的LINUX私房菜》基础篇
2.https://github.com/yangyangwithgnu/use_vim_as_ide
3.https://vi.stackexchange.com/questions/9028/what-is-the-command-for-select-all-in-vim-and-vsvim/9029
standard input(file handle 0)：标准输入，process利用这个file handle从用户读取数据
standard output(file handle 1)：标准输出，process向这个file handle写normal infor，会将输出输出到屏幕
standard error(file handle 2)：标准错误，process向这个file hanle写error infor
, >>, <, <<
是将std output进行重定向，>>是将std output进行追加。如果要将std error重定向或者追加，需要使用2表示表示std error。
~$:ls -ld /etc/ >~/etc_dir.txt
~$:find / -name ~/.bashrc >find_result
~$:find / -name ~/.bashrc >fing_right 2> find_error
~$:find / -name ~/.bashrc > find_result 2>/dev/null
~$:find / -name ~/.bashrc >find_result 2>&1
~$:cat > catfile
>
>
> ctrl + D
cat > catfile < ~/.bashrc
cat > catfile << “eof”
~$:my_command <inputfile 2>errorfile | grep XYZ
执行my_command，
打开inputfile文件作为标准输入，
打开errorfile文件作为标准错误，
|重定向上述命令的结果到grep 命令
1 | echo "hello" |
2>&1是将stderr重定向到stdout，比如command >/dev/null 2>&1是先将comand的stdout重定向到/dev/null中，然后将stderr重定向到stdout，因为stdout已经指向了/dev/null，所以stderr就重定向到了/dev/null。command >out.txt 2>&1是先将stdout重定向到out.txt，然后将stderr重定向到stdout，也就是out.txt。
1 | command > output_error.txt 2>&1， |
&>是bash的扩展，而2>&1是standard Bourne/POSIX shell。
</dev/null/dev/null是一个神奇的文件，它代表null device，会抛弃所有写入它的数据，但是会report写操作成功了，并且它不会向读取它的任何process提供任何数据，也就是向读取它的程序发送一个EOF。
所以</dev/null会发送一个EOF到stdin，&就是将程序放在后台运行，&的详细介绍可见linux process
这时候如果再加一个重定向命令，就是将命令的输出重定向到某个文件中而不在stdout中显示。
1 | ~$:nohup sslocal -c /etc/shadowsocks_v6.json </dev/null &>>~/.log/ss-local.log & # 后台运行sslocal |
1.https://unix.stackexchange.com/questions/27955/the-usage-of-dev-null-in-the-command-line
2.https://stackoverflow.com/questions/3385201/confused-about-stdin-stdout-and-stderr
3.https://stackoverflow.com/questions/818255/in-the-shell-what-does-21-mean
4.https://askubuntu.com/questions/635065/what-is-the-differences-between-and-21
TD方法是DP和MC方法的结合，像MC一样，TD可以不需要model直接从experience中学习，像DP一样，TD是bootstrap的方法。
本章的结构和之前一样，首先研究policy evaluation或者叫prediction问题，即给定一个policy $\pi$，估计$v_{\pi}$；然后研究control问题。DP,TD,MC方法都是使用GPI方法解control问题，不同点在于prediction问题的解法。
为什么叫TD？
因为TD更新是基于不同时间上两个estimate的估计进行的。
TD和MC都是利用采样获得的experience求解prediction问题。给定policy $\pi$下的一个experience，TD和MC方法使用该experience中出现的non-terminal state $S_t$估计$v_{\pi}$的$V$。他们的不同之处在于MC需要等到整个experience的return知道以后，把这个return当做$V(S_t)$的target，every visit MC方法的更新规则如下：
$$V(S_t) = V(S_t) + \alpha \left[G_t - V(S_t)\right]\tag{1}$$
其中$G_t$是从时刻$t$到这个episode结束的return，$\alpha$是一个常数的步长，这个方法叫做$constant-\alpha$ MC。MC方法必须等到一个episode结束，才能进行更新，因为只有这个时候$G_t$才知道。为了更方便的训练，就有了TD方法。TD方法做的改进是使用$t+1$时刻state $V(S_{t+1})$的估计值和reward $R_{t+1}$的和作为target：
$$V(S_t) = V(S_t) + \alpha \left[R_{t+1}+\gamma V(S_{t+1}) - V(S_t)\right]\tag{2}$$
如果V在变的话，是不是应该是下面的公式？？
$$V_{t+1}(S_t) = V_t(S_t) + \alpha \left[R_{t+1}+\gamma V_t(S_{t+1}) - V_t(S_t)\right]$$
即只要有了到$S_{t+1}$的transition并且接收到了reward $R_{t+1}$就可以进行上述更新。MC方法的target是$G_t$，而TD方法的target是$\gamma V(S_{t+1} + R_{t+1})$，这种TD方法叫做$TD-0$或者$one\ step\ TD$，它是$TD(\lambda)$和$n-step\ TD$的一种特殊情况。
下面是$TD(0)$的完整算法：
算法1 Tabular TD(0) for $V$
输入： 待评估的policy $\pi$
算法参数：步长$\alpha \in (0,1]$
初始化： $V(s), \forall s\in S^{+}，V(terminal) = 0$
Loop for each episode
$\qquad$初始化$S$
$\qquad A\leftarrow \pi(a|S)$
$\qquad$Loop for each step of episode
$\qquad\qquad$执行action $A$，得到$S’$和$R$
$\qquad\qquad V(S) = V(S) + \alpha \left[R + \gamma V(S’) - V(S)\right]$
$\qquad\qquad$$S\leftarrow S’$
$\qquad$Until $S$ 是terminal state
$TD(0)$是bootstrap方法，因为它基于其他state的估计value进行更新。从第三章中我们知道：
\begin{align*}
v_{\pi}(s) & = \mathbb{E}_{\pi}\left[G_t\right]\tag{3}\\
& = \mathbb{E}_{\pi}\left[R_{t+1}+\gamma G_{t+1}| S_t = s\right]\tag{4}\\
& = \mathbb{E}_{\pi}\left[R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_t = s\right]\tag{5}\\
\end{align*}
MC使用式子$(3)$的estimate作为target，而DP使用式子$(5)$的estimate作为target。MC方法用一个sample的return代替式子$(3)$中真实的未知expected return $G_t$；DP是用$V(S_{t+1})$作为$v_{\pi}(S_{t+1})$的一个估计，因为$v_{\pi}(S_{t+1})$的真实值是不知道的。TD结合了MC的采样以及DP的bootstrap，它对式子$(4)$的tranisition进行sample，同时使用$v_{\pi}$的估计值$V$进行计算。
TD的backup图如图所示。TD和MC updates被称为sample updates，因为这两个算法的更新都牵涉到采样一个sample successor state，使用这个state的value和它后继的这条路上的reward计算一个backed-up value，然后根据这个值更新该state的value。sample updates和DP之类的expected updates的不同在于，sample updates使用一个sample successor进行更新，expected updates使用所有可能的successors distribution进行更新。
$R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$可以看成一种error，衡量了$S_t$当前的estimated value $V(S_t)$和一个更好的estimated value之间的差异$R_{t+1} +\gamma V(S_{t+1})$，我们把它叫做$TD-error$，用$\delta_t$表示。$\delta_t$是$t$时刻的$TD-error$，在$t+1$时刻可用，用公式表示是：
$$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \tag{6}$$
如果$V$在一个episode中改变的话，那么上述公式是不是应该写成：
$$\delta_t = R_{t+1} + \gamma V_t(S_{t+1}) - V_t(S_t)$$
应该在$t$时刻，计算的TD error是用来更新$t+1$时刻的value的。如果$V$在一个episdoe中不变的话，就像MC方法一样，那么MC error可以写成TD errors的和。
\begin{align*}
G_t - V(S_t) & = R_{t+1} + \gamma G_{t+1} - V(S_t) + \gamma V(S_{t+1}) - \gamma V(S_{t+1})\\
& = R_{t+1} + \gamma V(S_{t+1}) - V(S_t) + \gamma G_{t+1} - \gamma V(S_{t+1})\\
& = \delta_t + \gamma G_{t+1} - \gamma V(S_{t+1})\\
& = \delta_t + \gamma(G_{t+1} - V(S_{t+1}))\\
& = \delta_t + \gamma\delta_{t+1} + \gamma^2(G_{t+2} - V(S_{t+2}))\\
& = \delta_t + \gamma\delta_{t+1} + \gamma^2\delta_{t+2} + \cdots + \gamma^{T-t-1}\delta_{T-1} + \gamma^{T-t}(G_T-V(S_T))\\
& = \delta_t + \gamma\delta_{t+1} + \gamma^2\delta_{t+2} + \cdots + \gamma^{T-t-1}\delta_{T-1} + \gamma^{T-t}(0-0)\\
& = \sum_{k=t}^{T-1} \gamma^{k-t}\delta_k \tag{7}\\
\end{align*}
如果$V$在一个episode中改变了的话，像$TD(0)$一样，这个公式就不精确成立了，如果$\alpha$足够小的话，还是近似成立的。
$$\delta_t = R_{t+1} + \gamma V_t(S_{t+1}) - V_t(S_t)$$
\begin{align*}
V_{t+1}(S_t) &= V_t(S_t) + \alpha \left[R_{t+1}+\gamma V_t(S_{t+1}) - V_t(S_t)\right]\\
&= V_t(S_t) + \alpha \delta_t
\end{align*}
\begin{align*}
G_t - V_t(S_t) & = R_{t+1} + \gamma G_{t+1} - V_t(S_t) + \gamma V_{t+1}(S_{t}) - \gamma V_{t+1}(S_{t})\\
& = R_{t+1} + \gamma V_{t+1}(S_{t}) - V_t(S_t) + \gamma G_{t+1}- \gamma V_{t+1}(S_{t})\\
& = R_{t+1} + \gamma (V_t(S_t) + \alpha \delta_t) - V_t(S_t) + \gamma G_{t+1}- \gamma V_{t+1}(S_{t})\\
& = R_{t+1} + \gamma V_t(S_t) - V_t(S_t) + \gamma \alpha \delta_t + \gamma G_{t+1}- \gamma V_{t+1}(S_{t})\\
\end{align*}
然而上面是错误的，因为$\delta_t$需要的是$V_t(S_{t+1})$
\begin{align*}
G_t - V_t(S_t) & = R_{t+1} + \gamma G_{t+1} - V_t(S_t) + \gamma V_{t+1}(S_{t+1}) - \gamma V_{t+1}(S_{t+1})\\
& = R_{t+1} + \gamma V_{t+1}(S_{t+1}) - V_t(S_t) + \gamma G_{t+1}- \gamma V_{t+1}(S_{t+1})\\
\end{align*}
\begin{align*}
\delta_t &= R_{t+1} + \gamma V_t(S_{t+1}) - V_t(S_t)\\
\delta_{t+1} &= R_{t+2} + \gamma V_{t+1}(S_{t+2}) - V_{t+1}(S_{t+1})\\
\delta_{t+2} &= R_{t+3} + \gamma V_{t+2}(S_{t+3}) - V_{t+2}(S_{t+2})\\
\delta_{t+3} &= R_{t+4} + \gamma V_{t+3}(S_{t+4}) - V_{t+3}(S_{t+3})\\
\end{align*}
\begin{align*}
&\delta_t+\delta_{t+1}+\delta_{t+2}+\delta_{t+3}\\
= &R_{t+1} + \gamma V_t(S_{t+1}) - V_t(S_t)\\
+&R_{t+2} + \gamma V_{t+1}(S_{t+2}) - V_{t+1}(S_{t+1})\\
+&R_{t+3} + \gamma V_{t+2}(S_{t+3}) - V_{t+2}(S_{t+2})\\
+&R_{t+4} + \gamma V_{t+3}(S_{t+4}) - V_{t+3}(S_{t+3})\\
\end{align*}
OK。。。还是没有算出来。。
TD的一个例子。每天下班的时候，你会估计需要多久能到家。你回家的事件和星期，天气等相关。在周五的晚上6点，下班之后，你估计需要30分钟到家。到车旁边是$6:05$，而且天快下雨了。下雨的时候会有些堵车，所以估计从现在开始大概还需要$35$分钟才能到家。十五分钟后，下了高速，这个时候你估计总共的时间是$35$分钟（包括到达车里的$5$分钟）。然后就遇到了堵车，真正到达家里的街道是$6:40$，三分钟后到家了。
| State | Elapsed Time | Predicted Time to Go | Predicted Total Time |
|---|---|---|---|
| leaveing office | 0 | 30 | 30 |
| reach car | 5 | 35 | 40 |
| 下高速 | 20 | 15 | 35 |
| 堵车 | 30 | 10 | 40 |
| 门口的街道 | 40 | 3 | 43 |
| 到家 | 43 | 0 | 43 |
rewards是每一个journey leg的elapsed times，这里我们研究的是evaluation问题，所以可以直接使用elapsed time，如果是control问题，要在elapsed times前加负号。state value是expected time。上面的第一列数值是reward，第二列是当前state的value估计值。
如果使用$\alpha = 1$的TD和MC方法。对于MC方法，对于$S_t$的所有state，都有：
\begin{align*}
V(S_t) &= V(S_t) + (G_t - V(S_t))\\
& = G_t \\
& = 43
\end{align*}
对于TD方法，让$\gamma=1$，有：
\begin{align*}
V(S_t) &= V_t(S_t) + \alpha (R_{t+1} + \gamma V_t(S_{t+1}) - V(S_t))\\
&= R_{t+1} + V_t(S_{t+1})
\end{align*}
TD是bootstrap方法，相对于MC和DP来说，TD的好处有以下几个：
但是具体TD好还是MC好，目前还没有明确的数学上的理论证明。而实践上表明，TD往往要比constant $\alpha$ MC算法收敛的快。
如果我们只有很少的experience的话，比如有$10$个episodes，或者有$100$个timesteps。这种情况下，我们会重复的使用这些这些experience进行训练直到算法收敛。具体方法是，给定一个approximate value function $V$，在每一个只要不是terminal state的时间$t$处，计算MC和TD增量，最后使用所有增量之和只更新value function一次。举个例子好了，假如我们有三个episdoes，
A,B,C
B,A
A,A
更新的方法是，$V(A) = V(A) + \alpha(G_1 - V(A) + G_2 - V(A) + G_{31} - V(A) + G_{32} -V(A))$
这种方法叫做batch updating，因为只有在一个batch完全处理完之后才进行更新，其实这个和DP挺像的，只不过DP直接利用的是environment dynamic，而我们使用的是样本。
在batch updating中，TD(0)一定会收敛到一个与$\alpha$无关的结果，只要$\alpha$足够下即可，同理batch constant $\alpha$ MC算法同样条件下也会收敛到一个确定的结果，只不过和batch TD结果不同而已。Normal updating的方法并没有朝着整个batch increments的方法移动，但是大概方向差不多。其实就是一个把整个batch的所有experience的increment加起来一起更新，一个是每一个experience更新一次，就这么点区别。
具体来说，batch TD和batch MC哪个更好一些呢？这就牵扯到他们的原理了。Batch MC的目标是最小化training set上的mse，而batch TD的目标是寻找Markov process的最大似然估计。一般来说，maximum likeliood estimate是进行参数估计的。在这里的话，TD使用mle从已有episodes中生成markov process模型的参数：从$i$到$j$的transition probatility是观测到从$i$到$j$的transition所占的百分比，对应的expected reward是观测到的rewards的均值。给出了这个model之后，如果这个模型是exactly correct的话，那么我们就可以准确的计算出value function的estimate，这个成为certainty-equivalence estimate，因为它相当于假设markov process的model是一致的，而不是approximated，一般来说，batch TD(0)收敛到cetainty-equivalence estimate。
从而，我们可以简单的解释以下为什么batch TD比batch MC收敛的快。因为batch TD计算的是真实的cetainty-equivalence estimate。同样的，对于non batch的TD和MC来说，虽然TD没有使用cetainty-equivalence，但是它们大概在向那个方向移动。
尽管cetrinty-equivalence是最优解，但是，但是，但是，cost太大了，如果有$n$个states，计算mle需要$n^2$的空间，计算value function时候，需要$n^3$的计算步数。当states太多的话，实际上并不可行，还是老老实实的使用TD把，只会用不超过$n$的空间。。
Sarsa是一个on-policy的 TD control算法。按照GPI的思路来，先进行policy evaluation，在进行policy improvement。首先解prediction问题，按照以下action value的$TD(0)$公式估计当前policy $\pi$下，所有action和state的$q$值$q_{\pi}(s,a)$：
$$Q(S_t,A_T) \leftarrow Q(S_t,A_t) + \alpha \left[R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) -Q(S_t,A_t)\right] \tag{8}$$
当$S_{t+1} = 0$时，$Q(S_{t+1}, A_{t+1})=0$，相应的backup diagram如下图所示。
第二步解control问题，在on-policy的算法中，不断的估计behaviour policy $\pi$的$q_{\pi}$，同时改变$\pi$朝着$q_{\pi}$更大的方向移动。Sarsa算法中，behaviour policy和target policy是一样的，在不断的改变。完整的算法如下：
Sarsa算法(on-policy control) 估计$Q\approx q_$*
对于所有$s\in S^{+}, a\in A(s)$，随机初始化$Q(s,a)$，$Q(terminal, \cdot) = 0$
Loop for each episode
$\qquad$ 获得初始状态$S$
$\qquad$ 使用policy（如$\epsilon$-greedy算法）根据state $S$选择当前动作$A$
$\qquad$ Loop for each step of episode
$\qquad\qquad$ 采取action，得到R和S’
$\qquad\qquad$ 使用policy（和上面的policy一样）根据S’选择A’
$\qquad\qquad Q(S,A) \leftarrow Q(S,A) + \alpha \left[R+ \gamma Q(S’,A’) - Q(S,A)\right]$
$\qquad\qquad S\leftarrow S’, A\leftarrow A’$
$\qquad$ until $S$是terminal
$$Q(S_t,A_T) \leftarrow Q(S_t,A_t) + \alpha \left[R_{t+1} + \gamma max Q(S_{t+1}, A_{t+1}) -Q(S_t,A_t)\right]\tag{9}$$
这一节介绍的是off-policy的TD contrl算法，Q-learning。对于off-policy算法来说，behaviour policy用来选择action，target policy是要评估的算法。在Q-learning算法中，直接学习的就是target policy的optimal action value function $q_{*}$，和behaviour policy无关。完整的Q-learning算法如下：
Q-learning算法(off-policy control) 估计$\pi \approx \pi_{*}$
对于所有$s\in S^{+}, a\in A(s)$，随机初始化$Q(s,a)$，$Q(terminal, \cdot) = 0$
Loop for each episode
$\qquad$ 获得初始状态$S$
$\qquad$ Loop for each step of episode
$\qquad\qquad$ 使用behaviour policy（如$\epsilon$-greedy算法）根据state $S$选择当前动作$A$
$\qquad\qquad$ 执行action $A$，得到$R$和$S’$
$\qquad\qquad Q(S,A) \leftarrow Q(S,A) + \alpha \left[R+ \gamma max Q(S’,A’) - Q(S,A)\right]$
$\qquad\qquad S\leftarrow S’$
$\qquad$ until $S$是terminal
Q-learning对所有next state-action pairs取了max操作。如果不是取max，而是取期望呢？
\begin{align*}
Q(S_t,A_T) & \leftarrow Q(S_t,A_t) + \alpha \left[R_{t+1} + \gamma \mathbb{E}_{\pi}\left[ Q(S_{t+1}, A_{t+1})| S_{t+1} \right] -Q(S_t,A_t)\right]\\
&\leftarrow Q(S_t,A_t) + \alpha \left[R_{t+1} + \gamma \sum_a\pi(a|S_{t+1})Q -Q(S_t,A_t)\right]\tag{10}
\end{align*}
其他的和Q-learning保持一致。给定next state $S_{t+1}$，算法在expectation上和sarsa移动的方向一样，所以被称为expected sarsa。这个算法可以是on-policy，但是通常它是是off-policy的。比如，on-policy的话，policy使用$\epsilon$ greedy算法，off-policy的话，behaviour policy使用stochastic policy，而target policy使用greedy算法，这其实就是Q-learning算法了。所以，Expected Sarsa实际上是对Q-learning的一个归纳，同时又有对Sarsa的改进。
Q-learning和Expected Sarsa的backup diagram如下所示：
Sarsa是on-policy的，behaviour policy和target policy一直在变（$\epsilon$在变），但是behaviour policy和target policy一直都是一样的。
Q-learning是off-policy的，target policy和behaviour policy一直都不变（可能$\epsilon$会变，但是这个不是Q-learning的重点），behaviour policy保证exploration，target policy是greedy算法。
Q-learning是off-policy算法，那么又为什么one-step Q-learning不需要importance sampling？Importance sampling的作用是为了使用policy $b$下观察到的rewards估计policy $\pi$下的expected rewards。尽管在Q-learning中，behaviour policy和target policy不同，behaviour policy仅仅用来采样$s_t, a_t, R_{t+1}$，在更新$Q$值时，使用target policy(epsilon policy)生成的实际上是$a’ = \max_a Q(s_{t+1}, a)$。Target policy和behaviour policy不同的实际上是$a_t$，但是在更新$Q$值时，用的也是$a_t$。也就是说使用behaviour policy选择的是$a_t$，接下来使用target policy选择执行$a_t$后的新action $a_{t+1}$。
Q(0)和Expected Sarsa(0)都没有使用importance sampling，因为在$Q(s,a)$中，action $a$已经被选择了，用哪个policy选择的是无关紧要的，TD error可以使用$Q(s’,*)$上的boostrap进行计算，而不需要behaviour policy。
目前介绍的所有control算法，都涉及到target polices的maximization操作。Q-learning中有greedy target policy，Sarsa的policy通常是$\epsilon$ greedy，也会牵扯到maximization。Max操作会引入一个问题，加入某一个state，它的许多action对应的$q(s,a)=0$，然后它的估计值$Q(s,a)$是不确定的，可能比$0$大，可能比$0$小，还可能就是$0$。如果使用max $Q(s,a)$的话，得到的值一定是大于等于$0$的，显然有一个positive bias，这就叫做maximization bias。
给出如下的一个例子：
这个MDP有四个state，A,B,C,D，C和D是terminal state，A总是start state，并且有left和right两个action，right action转换到C，reward是0,left action转换到B，reward是$0$，B有很多个actions，都是转换到$D$，但是rewards是不同，reward服从一个均值为$-0.5$，方差为$1.0$的正态分布。所以reward的期望是负的，$-0.5$。这就意味着在大量实验中，reward的均值往往是小于$0$的。
基于这个假设，在A处总是选择left action是很蠢的，但是因为其中有一些reward是positive，如果使用max操作的话，整个policy会倾向于选择left action，这就造成了在一些episodes中，reward是正的，但是如果在long run中，reward的期望就是负的。
那么为什么会出现这种问题呢？
用$X1$和$X2$表示reward的两组样本数据。如下所示：
在$X1$这组样本中，样本均值是$-0.43$，X2样本均值是$-0.36$。在增量式计算样本均值$\mu$时，得到的最大样本均值的期望是$0.09$，而实际上计算出来的期望的最大值$\mathbb{E}(X)$是$-0.36$。要使用$\mathbb{E} \left[max\ (\mu)\right]$估计$max\ \mathbb{E}(X)$，显然它们的差距有点大，$max(\mu)$是$max E(X)$的有偏估计。也就是说使用$max Q(s’,a’)$更新$Q(s,a)$时，$Q(s,a)$并没有朝着它的期望$-0.5$移动。估计这只是一个直观的解释，严格的证明可以从论文中找。
那么怎么解决这个问题呢，就是同时学习两个$Q$函数$Q_1, Q_2$，这两个$Q$函数的地位是一样的，每次随机选择一个选择action，然后更新另一个。证明的话，Van Hasselt证明了$\mathbb{E}(Q_2(s’,a*)\le max\ Q_1(s’,a*)$，也就是说$Q_1(s,a)$不再使用它自己的max value进行更新了。
下面是$Q$-learning和Double $Q$-learning在训练过程中在A处选择left的统计：
可以看出来，Double $Q$-learning要比$Q$-learning收敛的快和好。
当然，Sarsa和Expected Sarsa也有maximization bias问题，然后有对应的double版本，Double Sarsa和Double Expected Sarsa。
之前介绍了state value function和action value function。这里介绍一个afterstate value function，afterstate value function就是在某个state采取了某个action之后再进行评估，一开始我想这步就是action value function。事实上不是的，action value function估计的是$Q(s,a)$，重点是state和action这些pair，对于afterstate value来说，可能有很多个state和action都能到同一个next state，这个时候它们的作用是一样的，因为我们估计的是next state的value。
象棋就是一个这样的例子。。这里只是介绍一下，还有很多各种各样特殊的形式，它们可以用来解决各种各样的特殊问题。具体可以自己多了解一下。
这一章主要介绍了最简单的一种TD方法，one-step，tabular以及model-free。接下来的两章会介绍一些n-step的TD方法，可以和MC方法联系起来，以及包含一个模型的方法，和DP联系起来。在第二部分的时候，会将tabular的TD扩展到function approximation的形式，和deep learning以及artificial neural networks联系起来。
1.《reinforcement learning an introduction》第二版
2.https://stats.stackexchange.com/a/297892
3.https://towardsdatascience.com/double-q-learning-the-easy-way-a924c4085ec3
4.https://stats.stackexchange.com/a/347090/254953
更多介绍可以点击查看reinforcement learning an introduction 第三章
$\mathcal{S}$是有限states set，包含所有state的可能取值
$\mathcal{A}$是有限actions set，包含所有action的可能取值
$P:\mathcal{S}\times \mathcal{A}\times \mathcal{S} \rightarrow \mathbb{R}$是transition probability distribution，或者写成$p(s_{t+1}|s_t,a_t)$
$R:\mathcal{S}\times \mathcal{A}\rightarrow \mathbb{R}$是reward function
$\gamma \in (0, 1)$
$\rho_0$是初始状态$s_0$服从的distribution，$s_0\sim \rho_0$
定义为tuple $\left(\mathcal{S},\mathcal{A},P,R,\rho_0, \gamma\right)$
选择action，stochastic policy表示为：$\pi_\theta: \mathcal{S}\rightarrow P(\mathcal{A})$，其中$P(\mathcal{A})$是选择$\mathcal{A}$中每个action的概率，$\theta$表示policy的参数，$\pi_\theta(a_t|s_t)$是在$s_t$处取action $a_t$的概率
定义
$$G_t =\mathbb{E} \left[\sum_{k=t}^{\infty} \gamma^{k-t} R_{k+1}\right] \tag{1}$$
为expected discounted returns，表示从$t$时刻开始的expected discounted return；
state value function的定义是从$t$时刻的$s_t$开始的累计期望折扣奖励：
$$V^{\pi} (s_t) = \mathbb{E}_{a_{t}, s_{t+1},\cdots\sim \pi}\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \right] \tag{2}$$
或者有时候也定义成从$t=0$开始的expected return：
$$V^{\pi} (s_0) = \mathbb{E}_{\pi}\left[G_0|S_0=s_0;\pi\right]=\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty} \gamma^t R_{t+1}|S_0=s_0;\pi \right] \tag{3}$$
action value function定义为从$t$时刻的$s_t, a_t$开始的累计期望折扣奖励：
$$Q^{\pi} (s_t, a_t) = \mathbb{E}_{s_{t+1}, a_{t+1},\cdots\sim\pi}\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \right] \tag{4}$$
或者有时候也定义为从$t=0$开始的return的期望：
$$Q^{\pi} (s_0, a_0) = \mathbb{E}_{\pi}\left[G_0|S_0=s_0,A_0=a_0;\pi\right]=\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty} \gamma^t R_{t+1}|S_0=s_0,A_0=a_0;\pi \right] \tag{5}$$
$$A^{\pi} (s,a) = Q^{\pi}(s,a) -V^{\pi} (s) \tag{6}$$
其中$a_t\sim \pi(a_t|s_t), s_{t+1}\sim P(s_{t+1}|s_t, a_t)$。$V^{\pi} (s)$可以看成状态$s$下所有$Q(s,a)$的期望，而$A^{\pi} (s,a)$可以看成当前的单个$Q(s,a)$是否要比$Q(s,a)$的期望要好，如果为正，说明这个$Q$比$Q$的期望要好，否则就不好。
优势函数的期望是$0$：
$$\mathbb{E}_{\pi}\left[A^{\pi}(s,a)\right] = \mathbb{E}_{\pi}\left[Q^{\pi}(s,a) - V^{\pi}(s)\right] = \mathbb{E}_{\pi}\left[Q^{\pi}(s,a)\right] - \mathbb{E}_{\pi}\left[V^{\pi}(s)\right] = V^{\pi}(s) - V^{\pi}(s) = 0$$
Agents的目标是找到一个policy，最大化从state $s_0$开始的expected return：$J(\pi)=\mathbb{E}_{\pi} \left[G_0|\pi\right]$，或者写成：
$$\eta(\pi)= \mathbb{E}_{s_0, a_0, \cdots\sim \pi}\left[\sum_{t=0}^{\infty} \gamma^t R_{t+1}\right] \tag{7}$$
表示$t=0$时policy $\pi$的expected discounted return，其中$s_0\sim\rho_0(s_0)$, $a_t\sim\pi(a_t|s_t)$, $s_{t+1}\sim P(s_{t+1}|s_t,a_t)$。
用$p(s_0\rightarrow s,t,\pi)$表示从$s_0$经过$t$个timesteps到$s$的概率，则policy $\pi$下$s$服从的概率分布为：
$$\rho^{\pi} (s) = \int_S \sum_{t=0}^{\infty} \gamma^{t} \rho_0(s_0)p(s_0\rightarrow s, t,\pi)ds_0 \tag{8}$$
其中$\rho_0(s_0)$是初始状态$s_0$服从的概率分布，当指定$s_0$时，可以看成$\rho_0(s_0) = 1$。$\rho^{\pi} (s)$可以理解为：
$$\rho^{\pi} (s) = P(s_0 = s) +\gamma P(s_1=s) + \gamma^2 P(s_2 = s)+\cdots \tag{9}$$
表示policy $\pi$下state $s$出现的概率。在每一个timestep $t$处，$s_t=s$都有一定概率发生的，也就是式子$9$。
定义average reward $\eta$为在state distribution $\rho^\pi $和policy $\pi_\theta$上的期望：
\begin{align*}
\eta(\pi) &= \int_S \rho^{\pi} (s) \int_A \pi(s,a) R^{\pi}(s,a)dads\\
&= \mathbb{E}_{s\sim \rho^{\pi} , a\sim \pi}\left[R^{\pi}(s,a)\right] \tag{10}\\
\end{align*}
其中$R(s,a) = \mathbb{E}\left[ r_{t+1}|s_t=s, a_t=a\right]$，是state action pair $(s,a)$的immediate reward的期望值。
根据average reward，给出一种新的state-action value的定义方式：
$$Q^{\pi} (s,a) = \sum_{t=0}^{\infty} \mathbb{E}\left[R_t - \eta(\pi)|s_0=s,a_0=a,\pi\right], \forall s\in S, a\in A \tag{11}$$
Value function定义还和原来一样，形式没有变，但是因为$Q$计算方法变了，所以$V$的值也变了：
$$V^{\pi} (s) = \mathbb{E}_{\pi(a’;s)}\left[Q^{\pi}(s,a’)\right] \tag{12}$$
对于average reward来说，它的stationary distribution和accumulated reward有一些不同：
$$\rho^{\pi}(s) = \lim_{t\rightarrow \infty}Pr\left[s_t=s|s_0, \pi\right] \tag{13}$$
表示的是当MDP稳定之后，state $s$出现的概率。
这两种方式，accumulated reward需要加上折扣因子，而average reward不需要。我们常见的都是accumulated reward这种方式的动作值函数以及状态值函数。
online方法中训练数据一直在不断增加，基本上强化学习都是online的，而监督学习是offline的。
behaviour policy是采样的policy。
target policy是要evaluation的policy。
behaviour policy和target policy是不是相同的，相同的就是on-policy，不同的就是off-policy，带有replay buffer的都是off-policy的方法。
当前value的计算是否基于其他value的估计值。
常见的bootstrap算法有DP，TD-gamma
MC算法不是bootstrap算法。
values-based方法主要有policy iteration和value iteration。policy iteration又分为policy evaluation和policy improvement。
给出一个任务，如果可以使用value-based。随机初始化一个policy，然后可以计算这个policy的value function，这就叫做policy evaluation，然后根据这个value function，可以对policy进行改进，这叫做policy improvement，可以证明policy一定会更好。policy evaluation和policy improvement交替迭代，在线性case下，收敛性是可以证明的，在non-linear情况下，就不一定了。
policy iteraion中，policy evaluation每一次都要进行收敛后才进行policy improvemetn，如果policy evalution只进行一次，然后就进行一次policy improvemetn的话，也就是policy evalution的粒度变小后，就是value iteration。
value-based方法只适用于discrete action space，对于contionous action space的话，就无能为力了。这个时候就有了policy gradient，给出一个state，policy gradient给出一个policy直接计算出相应的action，然后给出一个衡量action好坏的指标，直接对policy的参数求导，最后收敛之后就求解出一个使用与contionous的policy
如果policy gradient的metrics选择使用value function，一般是aciton value function的话，我们把这个value function叫做critic，然后把policy叫做actor。通过value funciton Q对policy的参数求导进行优化。
critic跟policy没有关系，而critic指导actor的训练，通过链式法则实现。critic对a求偏导，a对actor的参数求偏导。
1.https://stats.stackexchange.com/questions/897/online-vs-offline-learning
1 | void in_place_swap(int *x, int *y) |
有一个问题就是，如果x和y指向同一个变量，因为x^x=0，所以这个代码会失效。
今天在看Reinforcment Learning: an Introduction第五章的时候，写了figure_5_4的代码，然后跟github上作者写出来的效率差了太多。
最后对比了一下代码，发现了原因，是因为做了太多重复运算。
1 | import numpy as np |
1.https://github.com/ShangtongZhang/reinforcement-learning-an-introduction/tree/master/chapter05
打开Settings >> Dock，可以设置dock的位置和大小，以及自动隐藏。这些是ubuntu安装的默认配置。
为了更多的设置，需要安装dconf-editor，dconf相当于windows注册表的gnome，存储应用程序设置的gnome技术。
~\$:sudo apt install dconf-tools
按下Win键，搜索dconfig-editor，打开它。
找到org>>gnome>>shell>>extensions>>dash-to-dock，然后就可以修改相应的配置了。也可以在命令行中进行相应的设置，这里就不说了，可以查看参考文献尝试。
~\$:sudo apt install gnome-tweak-tool
~\$:gnome-tweaks
找到Power选项，设置Suspend when lapto lid is closed为OFF。[6]
~\$:sudo apt-get install lm-sensors
然后执行以下命令进行配置：
~\$:sudo sensors-detect
执行sensors命令获得各项硬件的温度
~\$:sensors
~\$:sudo apt install gnome-tweak-tool
~\$:gnome-shell --version
gnome tweak用来查看本地的gnome 插件。
ubuntu 提供了gnome-shell-extensions包，该包中有部分gnome扩展。然后可以使用gnome tweaks查看已经安装的程序。
~\$:sudo apt install gnome-shell-extensions
在firfox或者chrome上安装相应的gnome shell integration插件，直接google搜索安装就行了。
这个时候是不能添加插件的，因为还缺少一个东西，叫做native host connector
这种方法和从ubuntu仓库中装extension的不同之处是，ubuntu包中的扩展是固定的一部分，这中方法可以自定义安装。
安装完之后可以直接在浏览器的gnome shell integration插件上查看在浏览器上安装的gnome shell扩展，也可以使用gnome tweaks查看浏览器上安装的shell extensions。
执行以下命令进行安装，chrome-gnome-shell并不是代表chrome浏览器的意思，用任何浏览器都要执行以下命令
~\$:sudo apt install chrome-gnome-shell
查看gnome shell版本
~\$:gnome-shell --version
直接打开gnome shell extensions图形化界面进行搜索安装
搜索
~\$:sudo apt search gnome-shell-extension
安装
~\$:sudo apt install gnome-shell-extension-package-name
下载系统主题文件，解压缩，放置在/usr/share/themes文件夹下。然后在tweaks中的Apperance选项修改。
下载鼠标和图标主题，放置在/usr/share/icons文件夹下。
1.https://linuxconfig.org/how-to-customize-dock-panel-on-ubuntu-18-04-bionic-beaver-linux
2.https://zhuanlan.zhihu.com/p/37852274
3.https://askubuntu.com/questions/15832/how-do-i-get-the-cpu-temperature
4.https://linuxhint.com/install_gnome3_extensions_ubuntu_1804/
5.https://linux.cn/article-9447-1.html
6.https://askubuntu.com/a/1062401
7.https://zhuanlan.zhihu.com/p/37852274