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.

Chess Gem

This is the most insane game that I have ever seen. It was between Stockfish and AlphaZero. It looks like Stockfish is giving up all of its pieces, but they are all poisoned.

Click on the title of the blog entry to render the embed because it appears to be buggy.