Munkres §53: Covering Spaces


Claim: If $Y$ has the discrete topology and $p:X\times Y\to X$ is projection on the first coordinate, then $p$ is a covering map.

Proof: Clearly, $p$ is continuous and surjective, and if $U_x$ is a neighborhood of $x\in X$, then
$$p^{-1}\left(U_x\right)=U_x\times Y=\bigsqcup_{y\in Y}\underbrace{U_x\times\left\{y\right\}}_{V_y},$$
where $\left.p\right|_{V_y}$ is a homeomorphism of $V_y$ onto $U_x$.
$$\tag*{$\blacksquare$}$$
Claim: If $U$ is evenly covered by $p$ and connected, then the partition of $p^{-1}\left(U\right)$ into slices is unique.

Proof: If there exist two distinct slices $\left\{V_\alpha\right\}$ and $\left\{W_\beta\right\}$, then there exists $\alpha'$ with $V_{\alpha'}\neq W_\beta$ for all $\beta$. If $\beta'$ is such that $A:=V_{\alpha'}\cap W_{\beta'}\neq\varnothing$, then
$$\bigcup_{\substack{\alpha\neq\alpha'\\\beta\neq\beta'}}V_\alpha\cap W_\beta=A^c.$$$$\tag*{$\Large↯$}$$
Claim: If $p:E\to B$ is a covering map, $B$ is connected, and $\left|p^{-1}\left(b_0\right)\right|=k$, then $\left|p^{-1}\left(b\right)\right|=k$ for all $b$, so $E$ is a $k$-fold covering of $B$.

Proof: Let $C:=\left\{b\in B:\left|p^{-1}\left(b\right)\right|=k\right\}$, $D:=\left\{b\in B:\left|p^{-1}\left(b\right)\right|\neq k\right\}$, and $b\in C$. Then there is a neighborhood $U\ni b$ such that there is a partition of $p^{-1}\left(U\right)$ into $k$ slices because each slice is homeomorphic to $U$. Therefore, for all $x\in U$, $\left|p^{-1}\left(x\right)\right|=k$, implying that $C$ is open. Similarly, $D$ is open. Finally, note that $C\cap D=\varnothing$ and $C\cup D=B$ by definition. $$\tag*{$\Large↯$}$$
Claim: If $q:X\to Y$ and $r:Y\to Z$ are covering maps and $r^{-1}\left(z\right)$ is finite for all $z\in Z$, then $p=r\circ q$ is a covering map.

Proof: Let $z\in Z$. Then there is a neighborhood $U$ of $z$ such that $\left\{U_i\right\}$ is a finite partition of $r^{-1}\left(U\right)$ into slices. Let $v_i$ be the only element in $r^{-1}\left(z\right)\cap U_i$. Then there is a neighborhood $V_i$ of $v_i$ such that $\left\{V_{i_\alpha}\right\}$ is a partition of $q^{-1}\left(V_i\right)$ into slices. Let$$C:=\bigcap_ir\left(U_i\cap V_i\right).$$Then $C$ is open and evenly covered by $r$. Let $W_{i_\alpha}:=q^{-1}\left(U_i\cap V_i\right)\cap V_{i_\alpha}$. Then $C$ is a neighborhood of $z$ such that $\left\{W_{i_\alpha}\right\}$ is a partition of $p^{-1}\left(C\right)$ into slices.$$\tag*{$\blacksquare$}$$
Claim: If $p:S^1\to S^1$ is defined by $z\mapsto z^n$, where $S^1:=\left\{z\in\mathbb C:\left|z\right|=1\right\}$, then $p$ is a covering map.

Proof: Let $z\in S^1$. Then $z=e^{i\theta'}$ for some $\theta'\in\left[0,2\pi\right)$. Define $\phi:\mathbb R\to S^1$ by $\theta\mapsto e^{i\theta}$, let $U:=\phi\left(\left(\theta'-\pi/2,\theta'+\pi/2\right)\right)$, and let $n=2$. Then$$p^{-1}\left(U\right)=\phi\left(\left(\frac12\theta'-\frac14\pi,\frac12\theta'+\frac14\pi\right)\right)\sqcup\phi\left(\left(\frac12\theta'+\frac34\pi,\frac12\theta'+\frac54\pi\right)\right).$$ This generalizes analogously to arbitrary $n$.$$\tag*{$\blacksquare$}$$
Claim: If $p:E\to B$ is a covering map and $B$ is Hausdorff, then $E$ is Hausdorff.

Proof: Let $x,y\in E$ be distinct. If $p(x)=p(y)$, then $x$ and $y$ are in different slices. Otherwise, there are neighborhoods $U$ and $V$ of $p\left(x\right)$ and $p\left(y\right)$ with slices $\left\{U_i\right\}$ and $\left\{V_i\right\}$. If $U$ and $V$ are disjoint, then $x$ and $y$ are in disjoint slices. Otherwise, since $B$ is Hausdorff, there are disjoint neighborhoods $U'$ and $V'$ of $p\left(x\right)$ and $p\left(y\right)$. Therefore, $p^{-1}\left(U'\right)\cap U_i$ and $p^{-1}\left(V'\right)\cap V_i$ are disjoint neighborhoods of $x$ and $y$. Analogous arguments work for $B$ regular, completely regular, and locally compact Hausdorff.$$\tag*{$\blacksquare$}$$
ClaimIf $p:E\to B$ is a covering map, $B$ is compact, and $p^{-1}\left(b\right)$ is finite for all $b$, then $E$ is compact.

Proof: Let $\left\{U_i\right\}$ be an open cover of $E$ and let $b\in B$. Then there is a neighborhood $V$ of $b$ such that $\left\{V_j\right\}$ is a finite partition of $p^{-1}\left(V\right)$ into slices. Let $U_{i_j}$ be such that $p^{-1}\left(b\right)\cap U_{i_j}\cap V_j\neq\varnothing$. Then $W_b:=\bigcap_jp\left(U_{i_j}\cap V_j\right)$ is a neighborhood of $b$ such that $p^{-1}\left(W_b\right)$ is covered by finitely-many $U_i$. Since $B$ is compact, so finitely-many $W_b$ cover $B$, implying that finitely-many $p^{-1}\left(W_b\right)$ cover $E$. Therefore, finitely-many $U_i$ cover $E$.$$\tag*{$\blacksquare$}$$

Reinforcement Learning, Pt. 1

A Markov Decision Process (MDP) is a $5$-tuple

$$(S,A,P,\gamma,R),$$
where

  1. $S$ is a set of states,
  2. $A$ is a set of actions,
  3. $P:(s,a,s')\mapsto[0,1]$ is a probability distribution representing the probability of going from state $s$ to state $s'$ after taking action $a$,
  4. $\gamma\in[0,1)$, and
  5. $R:S\to\mathbb R$ and $R:S\times A\to\mathbb R$ represent the reward for being in state $s$ and for being in state $s$ after taking action $a$, respectively.
A policy is a map $\pi:S\to A$.

A value associated to a policy $\pi$ is a map

$$\begin{align}V^\pi:S&\to\mathbb R\\s&\mapsto\mathbb E[R(s_0)+\gamma R(s_1)+\gamma^2R(s_2)+\cdots|s_0=s,\pi]\\&=R(s)+\gamma\sum_{s'\in S}P(s,\pi(s),s')V^\pi(s').\end{align}$$
The last expression above is called a Bellman equation.

A policy and its associated value are dual in the sense that one can be determined from the other.

The optimal value is the map

$$\begin{align}V^*:S&\to\mathbb R\\s&\mapsto\max_\pi V^\pi(s)\\&=R(s)+\gamma\max_{a\in A}\sum_{s'\in S}P(s,a,s')V^*(s').\end{align}$$

The optimal policy is the map

$$\begin{align}\pi^*:S&\to A\\s&\mapsto\arg\max_{a\in A}\sum_{s'\in S}P(s,a,s')V^*(s').\end{align}$$

The following is the value iteration algorithm:

  1. Set $V(s)=0$ for all $s\in S$.
  2. For all $s\in S$, set $$V(s)=R(s)+\gamma\max_{a\in A}\sum_{s'\in S}P(s,a,s')V(s').$$
  3. Repeat step 2 until convergence.
Convergence is due to the fact that $V$ is a contraction mapping.

The following is the policy iteration algorithm:

  1. Initialize $\pi$ randomly.
  2. Set $V=V^\pi$.
  3. For all $s\in S$, set $$\pi(s)=\arg\max_{a\in A}\sum_{s'\in S}P(s,a,s')V(s').$$
  4. Repeat step 2 until convergence.