Exercises

$\mathbf{W}_1 \in \mathbb{R}^{32 \times 64}, \quad \mathbf{b}_1 \in \mathbb{R}^{64}, \quad \mathbf{W}_2 \in \mathbb{R}^{64 \times 256}, \quad \mathbf{b}_2 \in \mathbb{R}^{256}$$

$|\theta| = 32 \times 64 + 64 + 64 \times 256 + 256 = 2048 + 64 + 16384 + 256 = 18752$$

The rule of thumb requires $N_{\text{train}} \geq 5|\theta|$ for good generalisation. Here $5 \times 18752 = 93\,760$, but we only have 300 samples. The ratio is $300/18752 \approx 0.016$, far below the recommended 5--10.

The 300 samples are grossly insufficient for this network. Options: (1) reduce $H$ to $\sim$8 (giving $\sim$2600 parameters), (2) use a model-based approach (deep unfolding) with far fewer parameters, or (3) augment data by training at multiple SNR values.

Computing $|s_m|^2 = I_m^2 + Q_m^2$ for each symbol:

Symbol	$|s_m|^2$
0	$1.1025 + 0.0004 = 1.1029$
1	$0.2601 + 0.7744 = 1.0345$
2	$0.2401 + 0.7921 = 1.0322$
3	$1.0816 + 0.0009 = 1.0825$
4	$0.2704 + 0.7569 = 1.0273$
5	$0.2500 + 0.7744 = 1.0244$
6	$0.0001 + 0.0001 = 0.0002$
7	$0.0000 + 0.0001 = 0.0001$

$$E_s = \frac{1}{8}(1.1029 + 1.0345 + 1.0322 + 1.0825 + 1.0273 + 1.0244 + 0.0002 + 0.0001)$$ $$= \frac{6.3041}{8} = 0.788$$

Symbols 0--5 lie approximately on a circle of radius $\approx 1.0$ at angles $\{0^\circ, 60^\circ, 120^\circ, 180^\circ, 240^\circ, 300^\circ\}$ --- this is essentially 6-PSK (regular hexagonal arrangement). Symbols 6 and 7, however, are clustered near the origin.

This is a (6,2) constellation: 6 points on a circle plus 2 near the centre. Classical 8-PSK places all 8 points on a circle with angular spacing $45^\circ$. The autoencoder has discovered an alternative arrangement that sacrifices the energy of symbols 6 and 7 (placing them at the origin where they are easily confused with each other under noise) to increase the minimum distance among the remaining 6 symbols.

Whether this is truly optimal depends on the prior probability of each symbol. If all symbols are equiprobable, the near-origin symbols are a weakness. This illustrates that small-scale autoencoder training can sometimes converge to suboptimal local minima.

$|\mathcal{A}| = J^K = 4^3 = 64 \text{ joint actions}KATEXPLACEHOLDER0END\text{Q-table entries} = |\mathcal{S}| \times |\mathcal{A}| = 27 \times 64 = 1728$$

Each user has a table of size $|\mathcal{S}| \times J = 27 \times 4 = 108$. Total for $K = 3$ users: $3 \times 108 = 324$ entries.

$\text{Reduction} = \frac{1728}{324} = 5.33\times$$The reduction grows exponentially with$K$: for$K = 8$users, the joint table has$27 \times 4^8 = 1,769,472$entries vs$8 \times 27 \times 4 = 864$for the per-user approach --- a$2048\times$ reduction. However, the per-user decomposition ignores inter-user coupling and may converge to a suboptimal (Nash equilibrium) rather than the globally optimal allocation.

$\text{Cost per client} = 5000 \times 4 \;\text{bytes} = 20\,000 \;\text{bytes} = 19.53 \;\text{KB} \approx 20 \;\text{KB}$$

$\text{Total} = R \times C \times 20 \;\text{KB} = 80 \times 10 \times 20 = 16\,000 \;\text{KB} = 15.6 \;\text{MB}$$(Plus the same amount for the server-to-client broadcast, giving$\sim$31 MB total bidirectional communication.)

$\text{Total} = R \times C_r \times 20 \;\text{KB} = 80 \times 3 \times 20 = 4800 \;\text{KB} = 4.7 \;\text{MB}$$A$3.3\times$ reduction. Partial participation also reduces the per-round latency (fewer clients to wait for), but may slow convergence because less data is represented per round.

Define the error $\mathbf{e}_i = \hat{\mathbf{h}}_i - \mathbf{h}_i$ and the hidden activation $\mathbf{a}_i = \sigma(\mathbf{W}_1\mathbf{y}_{p,i} + \mathbf{b}_1)$. Then $\hat{\mathbf{h}}_i = \mathbf{W}_2\mathbf{a}_i + \mathbf{b}_2$.

$$\frac{\partial\mathcal{L}}{\partial\mathbf{W}_2} = \frac{2}{N}\sum_{i=1}^N \mathbf{e}_i \, \mathbf{a}_i^T = \frac{2}{N}\sum_{i=1}^N (\mathbf{W}_2\mathbf{a}_i + \mathbf{b}_2 - \mathbf{h}_i)\,\mathbf{a}_i^T$$

In matrix form: $\frac{\partial\mathcal{L}}{\partial\mathbf{W}_2} = \frac{2}{N}\mathbf{E}^T\mathbf{A}$ where $\mathbf{E}$ and $\mathbf{A}$ are the error and activation matrices with samples as rows.

By the chain rule:

$$\frac{\partial\mathcal{L}}{\partial\mathbf{W}_1} = \frac{2}{N}\sum_{i=1}^N \underbrace{\mathrm{diag}(\mathbf{1}_{\mathbf{z}_i > 0})}_{\text{ReLU derivative}} \mathbf{W}_2^T \mathbf{e}_i \, \mathbf{y}_{p,i}^T$$

where $\mathbf{z}_i = \mathbf{W}_1\mathbf{y}_{p,i} + \mathbf{b}_1$ is the pre-activation. The diagonal matrix $\mathrm{diag}(\mathbf{1}_{\mathbf{z}_i > 0})$ zeroes out gradients for hidden units whose pre-activation was negative (inactive ReLU units).

If $\mathbf{y}_p \geq 0$ element-wise and $\mathbf{b}_1 = 0$, then $\mathbf{z}_i = \mathbf{W}_1\mathbf{y}_{p,i} \geq 0$ whenever $\mathbf{W}_1$ has non-negative entries. In this case, $\mathbf{1}_{\mathbf{z}_i > 0} = \mathbf{1}$ (all ones) and the ReLU becomes the identity:

$$\frac{\partial\mathcal{L}}{\partial\mathbf{W}_1} = \frac{2}{N}\sum_{i=1}^N \mathbf{W}_2^T \mathbf{e}_i \, \mathbf{y}_{p,i}^T$$

This simplification only holds at initialisation with non-negative weights; during training, some weights become negative and dead ReLU units appear.

With only per-layer scalar thresholds: $$|\theta| = L \text{ parameters}$$

For $L = 10$ layers: only 10 trainable parameters. This is remarkably few and explains the excellent sample efficiency of model-based deep unfolding.

Per layer:

• $\mathbf{W}^{(l)} \in \mathbb{R}^{50 \times 50}$: $2500$ parameters
• $\mathbf{S}^{(l)} \in \mathbb{R}^{50 \times 25}$: $1250$ parameters
• $\theta^{(l)}$: $1$ parameter

Per layer: $3751$ parameters. Total for $L$ layers: $3751L$.

For $L = 10$: $37\,510$ parameters --- still far fewer than a general black-box network mapping $\mathbb{R}^{25} \to \mathbb{R}^{50}$ would need for comparable depth.

Target NMSE: $-15$ dB $= 10^{-1.5} \approx 0.0316$.

Using $C\rho^L \leq 0.0316$ with $C = 1$ and $\rho = 0.7$:

$$0.7^L \leq 0.0316$$ $$L \ln(0.7) \leq \ln(0.0316)$$ $$L \geq \frac{\ln(0.0316)}{\ln(0.7)} = \frac{-3.454}{-0.357} \approx 9.7$$

So $L = 10$ LISTA layers suffice, compared to $T = 30$ ISTA iterations --- a $3\times$ reduction. With optimised (trained) thresholds and matrices, the effective $\rho$ can be smaller, potentially allowing even fewer layers.

With $\gamma = 0$, $Q^*(s, a) = r(s, a)$:

State	$p = 0.5$	$p = 1.0$	$p = 2.0$
low ($|h|^2 = 0.3$)	$\log_2(1.15) = 0.202$	$\log_2(1.3) = 0.379$	$\log_2(1.6) = 0.678$
med ($|h|^2 = 1.0$)	$\log_2(1.5) = 0.585$	$\log_2(2.0) = 1.000$	$\log_2(3.0) = 1.585$
high ($|h|^2 = 3.0$)	$\log_2(2.5) = 1.322$	$\log_2(4.0) = 2.000$	$\log_2(7.0) = 2.807$

For every state, the maximum Q-value is at $p = 2.0$:

$$\pi^*(s) = 2.0 \quad \forall s$$

This is unsurprising for a single-user system without a power constraint: more power always means more rate. In a multi-user setting with interference, the optimal policy would be state-dependent.

With $\alpha = 1$ and $\gamma = 0$, the update $Q(s,a) \leftarrow Q(s,a) + 1 \cdot [r - Q(s,a)] = r$ directly sets $Q(s,a) = r(s,a)$ after one visit.

Therefore, the Q-table is already optimal after one visit per pair, because the reward is deterministic (given the quantised state) and $\gamma = 0$ eliminates the need to estimate future returns. This is a special case; with stochastic rewards or $\gamma > 0$, convergence requires many visits.

Under the constant-gradient approximation:

$$\mathbf{w}_c^{(E)} = \mathbf{w} - E\eta\,\mathbf{g}_c = \mathbf{w} - E\eta\,\nabla F_c(\mathbf{w})$$

$\bar{\mathbf{w}} = \frac{1}{C}\sum_{c=1}^C \mathbf{w}_c^{(E)} = \mathbf{w} - E\eta\,\frac{1}{C}\sum_{c=1}^C \mathbf{g}_c = \mathbf{w} - E\eta\,\mathbf{g}$$

Centralised SGD: $\mathbf{w}_{\text{cent}} = \mathbf{w} - \eta_{\text{cent}}\,\mathbf{g}$.

FedAvg: $\bar{\mathbf{w}} = \mathbf{w} - E\eta\,\mathbf{g}$.

These are identical when $\eta_{\text{cent}} = E\eta$, i.e., the effective federated learning rate is $E$ times the local learning rate.

Crucially, this equivalence holds only under the constant-gradient assumption (i.e., $F_c$ is linear). For non-linear $F_c$, the gradient changes during local SGD, and each client drifts toward its own local optimum. The resulting "client drift" creates the heterogeneity bias in the FedAvg convergence bound. This is why the bias term $O(E\Gamma/\mu)$ in Theorem 31.4 grows with $E$.

$\frac{\partial \mathcal{S}_\theta(z)}{\partial z} = \begin{cases} 1 & \text{if } |z| > \theta \\ 0 & \text{if } |z| < \theta \end{cases}$$At$z = \pm\theta$, the function is not differentiable, but the subgradient is conventionally taken as 0 (consistent with treating the ReLU-like kink as having zero derivative).

This is identical to the derivative of the "dead zone" function --- values inside the threshold band have zero gradient (they contribute nothing to the output and receive no learning signal), while values outside pass gradients unchanged.

For $|z| > \theta$: $\mathcal{S}_\theta(z) = z - \theta\,\mathrm{sign}(z)$, so:

$$\frac{\partial \mathcal{S}_\theta(z)}{\partial \theta} = -\mathrm{sign}(z)$$

For $|z| < \theta$: $\mathcal{S}_\theta(z) = 0$, so:

$$\frac{\partial \mathcal{S}_\theta(z)}{\partial \theta} = 0$$

Summarising: $$\frac{\partial \mathcal{S}_\theta(z)}{\partial \theta} = \begin{cases} -\mathrm{sign}(z) & |z| > \theta \\ 0 & |z| < \theta \end{cases}$$

The gradient $\partial\mathcal{S}_\theta/\partial\theta = -\mathrm{sign}(z)$ (for active elements) tells us:

• If increasing $\theta$ would reduce the output magnitude of an element that should be large (positive contribution to loss), the gradient will push $\theta$ to decrease.
• If an element is spuriously active (non-zero output when the ground truth is zero), the loss gradient through this element will push $\theta$ to increase, killing the spurious entry.

In early LISTA layers, the training objective encourages a large threshold (aggressive sparsification to identify the correct support). In later layers, the objective encourages a small threshold (fine-tune the amplitudes of the identified non-zero entries). This automatic adaptation of sparsity level per layer is the key advantage over ISTA's fixed threshold.

Let $P = \frac{1}{M}\sum_{m=1}^M\|\mathbf{z}_m\|^2$. Then:

$$\frac{1}{M}\sum_{s=1}^M \|\mathbf{x}_s\|^2 = \frac{1}{M}\sum_{s=1}^M \frac{\|\mathbf{z}_s\|^2}{P} = \frac{1}{P} \cdot \frac{1}{M}\sum_{s=1}^M \|\mathbf{z}_s\|^2 = \frac{P}{P} = 1 \quad \checkmark$$

$\mathcal{L} = -\frac{1}{B}\sum_{i=1}^B \log \hat{p}_{s_i} = -\frac{1}{B}\sum_{i=1}^B \log\!\left[\mathrm{softmax}(\mathbf{l}_i)\right]_{s_i}$$where$\mathbf{l}_i = \mathbf{W}_4\sigma(\mathbf{W}_3\mathbf{y}_i + \mathbf{b}_3) + \mathbf{b}_4$ is the logit vector.

For a single sample with true label $s$:

$$\frac{\partial\mathcal{L}}{\partial\mathbf{l}} = \hat{\mathbf{p}} - \mathbf{e}_s$$

where $\hat{\mathbf{p}} = \mathrm{softmax}(\mathbf{l})$ and $\mathbf{e}_s$ is the one-hot vector with a 1 at position $s$.

Proof sketch: $\frac{\partial(-\log p_s)}{\partial l_j} = -\frac{1}{p_s}\frac{\partial p_s}{\partial l_j}$. For $j = s$: $\frac{\partial p_s}{\partial l_s} = p_s(1 - p_s)$, giving $-(1 - p_s) = p_s - 1$. For $j \neq s$: $\frac{\partial p_s}{\partial l_j} = -p_s p_j$, giving $p_j$. Combining: $\hat{\mathbf{p}} - \mathbf{e}_s$.

This elegant form is why softmax + cross-entropy is the standard choice for classification --- the gradient is simply the prediction error.

Since $\mathbf{h}$ and $\mathbf{y}$ are jointly Gaussian:

$$\hat{\mathbf{h}}_{\mathrm{MMSE}} = \mathbb{E}[\mathbf{h}|\mathbf{y}] = \mathbf{R}_{h y}\mathbf{R}_{y y}^{-1}\mathbf{y}$$

where $\mathbf{R}_{h y} = \mathbb{E}[\mathbf{h}\mathbf{y}^H] = \mathbf{R}_{HH}$ (since $\mathbf{y} = \mathbf{h} + \mathbf{n}$ and $\mathbf{h} \perp \mathbf{n}$) and $\mathbf{R}_{y y} = \mathbf{R}_{HH} + \sigma^2\mathbf{I}$.

Therefore: $\hat{\mathbf{h}}_{\mathrm{MMSE}} = \mathbf{R}_{HH}(\mathbf{R}_{HH} + \sigma^2\mathbf{I})^{-1}\mathbf{y}$.

For any estimator $g(\mathbf{y})$:

$$\mathbb{E}[\|\mathbf{h} - g(\mathbf{y})\|^2] = \mathbb{E}[\|\mathbf{h} - \hat{\mathbf{h}}_{\mathrm{MMSE}} + \hat{\mathbf{h}}_{\mathrm{MMSE}} - g(\mathbf{y})\|^2]$$

Expanding: $$= \mathbb{E}[\|\mathbf{h} - \hat{\mathbf{h}}_{\mathrm{MMSE}}\|^2] + \mathbb{E}[\|\hat{\mathbf{h}}_{\mathrm{MMSE}} - g(\mathbf{y})\|^2] + 2\operatorname{Re}\,\mathbb{E}[(\mathbf{h} - \hat{\mathbf{h}}_{\mathrm{MMSE}})^H( \hat{\mathbf{h}}_{\mathrm{MMSE}} - g(\mathbf{y}))]$$

By the orthogonality principle, the MMSE error $\mathbf{h} - \hat{\mathbf{h}}_{\mathrm{MMSE}}$ is orthogonal to any function of $\mathbf{y}$, so the cross-term vanishes. The second term is non-negative. Therefore:

$$\mathbb{E}[\|\mathbf{h} - g(\mathbf{y})\|^2] \geq \mathbb{E}[\|\mathbf{h} - \hat{\mathbf{h}}_{\mathrm{MMSE}}\|^2]$$

with equality iff $g(\mathbf{y}) = \hat{\mathbf{h}}_{\mathrm{MMSE}}$ a.s.

Minimise $J(\mathbf{W}) = \mathbb{E}[\|\mathbf{h} - \mathbf{W}\mathbf{y}\|^2]$:

$$\nabla_{\mathbf{W}} J = -2\mathbb{E}[(\mathbf{h} - \mathbf{W}\mathbf{y})\mathbf{y}^H] = -2(\mathbf{R}_{hy} - \mathbf{W}\mathbf{R}_{yy})$$

Setting to zero: $\mathbf{W}^* = \mathbf{R}_{hy}\mathbf{R}_{yy}^{-1} = \mathbf{R}_{HH}(\mathbf{R}_{HH} + \sigma^2\mathbf{I})^{-1}$, which is exactly the MMSE weight.

For jointly Gaussian $(\mathbf{h}, \mathbf{y})$, the conditional mean $\mathbb{E}[\mathbf{h}|\mathbf{y}]$ is linear in $\mathbf{y}$. This is a fundamental property of Gaussian distributions. Since the MMSE estimator (conditional mean) is already linear, no non-linear function of $\mathbf{y}$ can achieve a lower MSE. A non-linear NN trained with MSE loss will converge to the same linear mapping (plus some noise from finite-sample training).

Non-linear NNs offer an advantage only when the channel distribution is non-Gaussian (e.g., sparse channels, channels with discrete components, or channels corrupted by non-Gaussian interference).

With $L = a^2$, step size $1/L = 1/a^2$, and threshold $\lambda/L = \lambda/a^2$:

$$x^{(t+1)} = \mathcal{S}_{\lambda/a^2}\!\left( x^{(t)} - \frac{1}{a^2} a(ax^{(t)} - y)\right) = \mathcal{S}_{\lambda/a^2}\!\left( x^{(t)} - \frac{1}{a}(ax^{(t)} - y)\right)$$

Simplifying: $x^{(t+1)} = \mathcal{S}_{\lambda/a^2}(\frac{y}{a})$.

Note: in this 1D case, ISTA converges in one step because the gradient step already reaches the proximal minimiser.

LISTA update: $x^{(l+1)} = \mathcal{S}_\theta(wx^{(l)} + sy)$.

ISTA-initialised values: $$w = 1 - \frac{a^2}{a^2} = 0, \quad s = \frac{a}{a^2} = \frac{1}{a}, \quad \theta = \frac{\lambda}{a^2}$$

With $w = 0$, the update becomes $x^{(l+1)} = \mathcal{S}_{\lambda/a^2}(y/a)$ regardless of the current iterate, confirming the one-step convergence of 1D ISTA.

At a fixed point with $|wx^* + sy| > \theta$:

$$x^* = wx^* + sy - \theta\,\mathrm{sign}(wx^* + sy)$$ $$x^*(1 - w) = sy - \theta\,\mathrm{sign}(wx^* + sy)$$

For $sy > 0$ (and assuming $wx^* + sy > 0$):

$$x^* = \frac{sy - \theta}{1 - w}$$

With ISTA initialisation ($w = 0$): $x^* = sy - \theta = y/a - \lambda/a^2$.

The MAP estimate minimises: $$\hat{x}_{\mathrm{MAP}} = \arg\min_x \frac{1}{2\sigma^2}(y - ax)^2 + \lambda|x|$$

Taking the subdifferential and setting to zero: $$\frac{a}{\sigma^2}(a\hat{x} - y) + \lambda\,\mathrm{sign}(\hat{x}) = 0$$ $$\hat{x} = \frac{1}{a}\left(y - \frac{\lambda\sigma^2}{a}\mathrm{sign}(\hat{x})\right)$$

For $\hat{x} > 0$: $\hat{x} = \frac{y}{a} - \frac{\lambda\sigma^2}{a^2}$.

This is $\mathcal{S}_{\lambda\sigma^2/a^2}(y/a)$, i.e., soft-thresholding with threshold $\lambda\sigma^2/a^2$ rather than $\lambda/a^2$.

Comparison: ISTA uses threshold $\lambda/a^2$; MAP uses $\lambda\sigma^2/a^2$. They coincide when $\sigma^2 = 1$. LISTA can learn the correct threshold $\theta^* = \lambda\sigma^2/a^2$ from data, thereby matching the MAP estimator, while ISTA uses a fixed (possibly mismatched) threshold.

$Q^*(s_1, a_1) = 5 + 0.9[0.8 V^*(s_1) + 0.2 V^*(s_2)]KATEXPLACEHOLDER0ENDQ^*(s_1, a_2) = 1 + 0.9[0.8 V^*(s_1) + 0.2 V^*(s_2)]KATEXPLACEHOLDER1ENDQ^*(s_2, a_1) = 2 + 0.9[0.2 V^*(s_1) + 0.8 V^*(s_2)]KATEXPLACEHOLDER2ENDQ^*(s_2, a_2) = 8 + 0.9[0.2 V^*(s_1) + 0.8 V^*(s_2)]$$where$V^(s) = \max_a Q^(s, a)$.

From the equations, $Q^*(s_1, a_1) - Q^*(s_1, a_2) = 4 > 0$, so $V^*(s_1) = Q^*(s_1, a_1)$. Similarly, $Q^*(s_2, a_2) - Q^*(s_2, a_1) = 6 > 0$, so $V^*(s_2) = Q^*(s_2, a_2)$.

Let $V_1 = V^*(s_1)$ and $V_2 = V^*(s_2)$:

$$V_1 = 5 + 0.9(0.8 V_1 + 0.2 V_2) = 5 + 0.72 V_1 + 0.18 V_2$$ $$V_2 = 8 + 0.9(0.2 V_1 + 0.8 V_2) = 8 + 0.18 V_1 + 0.72 V_2$$

From the first: $0.28 V_1 - 0.18 V_2 = 5$, so $V_1 = (5 + 0.18 V_2)/0.28$.

From the second: $-0.18 V_1 + 0.28 V_2 = 8$, so $V_2 = (8 + 0.18 V_1)/0.28$.

Substituting: $V_1 = (5 + 0.18(8 + 0.18 V_1)/0.28)/0.28$

$0.28 V_1 = 5 + 0.18 \times (8 + 0.18 V_1)/0.28$

$0.0784 V_1 = 1.4 + 0.18(8 + 0.18 V_1) = 1.4 + 1.44 + 0.0324 V_1$

$0.046 V_1 = 2.84$, so $V_1 = 61.74$ and $V_2 = (8 + 0.18 \times 61.74)/0.28 = (8 + 11.11)/0.28 = 68.25$.

The full Q-table: $$Q^*(s_1, a_1) = 61.74, \quad Q^*(s_1, a_2) = 57.74$$ $$Q^*(s_2, a_1) = 62.25, \quad Q^*(s_2, a_2) = 68.25$$

$\pi^*(s_1) = a_1 \quad (Q^* = 61.74 > 57.74)KATEXPLACEHOLDER0END\pi^*(s_2) = a_2 \quad (Q^* = 68.25 > 62.25)$$Intuitively: in$s_1$, take the high-immediate-reward action ($R = 5$); in$s_2$, take the even higher immediate reward ($R = 8$). The optimal policy happens to be greedy w.r.t. immediate rewards in this example, but this is coincidental.

Start: $Q = 0$, state $s_1$, greedy ($\epsilon = 0$).

Step 1: All Q-values equal 0, greedy picks $a_1$ (arbitrary tie-breaking). $r = 5$. Next state: $s_1$ (prob 0.8). $Q(s_1,a_1) \leftarrow 0 + 0.5[5 + 0.9 \times 0 - 0] = 2.5$.

Step 2: $Q(s_1,a_1) = 2.5 > Q(s_1,a_2) = 0$, pick $a_1$. $r = 5$. Next: $s_2$ (prob 0.2, suppose transition). $Q(s_1,a_1) \leftarrow 2.5 + 0.5[5 + 0.9 \times 0 - 2.5] = 3.75$.

Step 3: State $s_2$, $Q(s_2,a_1) = Q(s_2,a_2) = 0$, pick $a_1$ (tie). $r = 2$. Next: $s_2$. $Q(s_2,a_1) \leftarrow 0 + 0.5[2 + 0.9 \times 0 - 0] = 1.0$.

Note: in step 3, the agent picks $a_1$ in $s_2$ (suboptimal --- the optimal action is $a_2$ with $R = 8$). It takes $a_1$ because both Q-values were 0 and the tie was broken in favour of $a_1$. Without exploration ($\epsilon = 0$), the agent may lock into $a_1$ for $s_2$ for many steps before the Q-value of $a_2$ gets updated. This illustrates the necessity of exploration.