Deep & Reinforcement Learning (CY-802 (B)) - Important Questions

Derive the Bellman optimality equation for the state-value function $V^*(s)$ in a finite Markov Decision Process (MDP). Write the corresponding Bellman optimality operator and prove that it is a contraction mapping under the sup-norm, hence showing why value iteration converges to $V^*$. In your derivation include the equation

$$V^*(s)=\max_a\sum_{s'}P(s'\mid s,a)\left(R(s,a,s')+\gamma V^*(s')\right)$$

and show the contraction inequality

$$\|T_V V- T_V W\|_\infty \le \gamma\|V-W\|_\infty\;.$$

Define a Markov Decision Process (MDP). Clearly state and explain its components: state space $S$, action space $A$, transition probabilities $P(s'\mid s,a)$, reward function $R(s,a,s')$, and discount factor $\gamma$. Provide a concise tabular specification (states, actions, transitions, rewards) for a small example MDP (at least 3 states) and explain how an episode would proceed.

Explain Value Iteration and Policy Iteration algorithms for solving finite MDPs. For Value Iteration give the update rule and policy extraction step. For Policy Iteration describe policy evaluation and policy improvement steps. For a small 3-state MDP perform two iterations of value iteration numerically (showing intermediate value vectors) and demonstrate how the greedy policy is extracted from the current value estimate. Discuss time and space complexity differences between the two methods.

Derive the Q-learning update rule starting from the Bellman optimality equation for the action-value function $Q^*(s,a)$. State why Q-learning is considered an off-policy temporal-difference control algorithm and list the standard conditions required for its convergence (step-size schedules, sufficient exploration, Markovian environment). Include the Bellman optimality equation:

$$Q^*(s,a)=\mathbb{E}_{s'}\left[R(s,a,s')+\gamma\max_{a'}Q^*(s',a')\right]\;,$$

and the incremental update form used in practice.

Describe Temporal-Difference (TD(0)) learning for state-value prediction and give its update rule. Present the SARSA algorithm and its update equation, then contrast SARSA (on-policy) with Q-learning (off-policy) in terms of their update targets and behaviour under exploration. Use the SARSA update:

$$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)\;.$$

Explain the Deep Q-Network (DQN) algorithm. Describe the role of the Q-network, experience replay buffer, and target network. Write the DQN squared-error loss used for a minibatch sampled from replay memory and define the target value explicitly. Use the following loss expressions:

$$L(\theta)=\mathbb{E}_{(s,a,r,s')\sim D}\left[\left(y^{\mathrm{DQN}}-Q(s,a;\theta)\right)^2\right]\;,$$

where

$$y^{\mathrm{DQN}}=r+\gamma\max_{a'}Q\left(s',a';\theta^{-}\right)\;,$$

and discuss how the target network parameters $\theta^{-}$ are maintained and why these components improve training stability.

Explain experience replay in Deep Q-Learning. State its purpose (breaking temporal correlations and improving sample efficiency), describe how a replay buffer operates, and summarize the idea of prioritized experience replay. Discuss practical trade-offs such as memory cost, staleness of samples, and non-stationarity introduced by changing policy.

Compare and contrast common exploration strategies: $\epsilon$-greedy, Boltzmann (softmax) exploration, and Upper Confidence Bound (UCB). Provide the Boltzmann action selection formula

$$\pi(a\mid s)=\frac{\exp\left(\dfrac{Q(s,a)}{\tau}\right)}{\sum_b\exp\left(\dfrac{Q(s,b)}{\tau}\right)}\;,$$

and a standard UCB selection rule:

$$a_t=\arg\max_a\left(\overline{Q}_a+c\sqrt{\dfrac{\ln t}{N_a}}\right)\;.$$

Explain the use of nonlinear function approximation (neural networks) for value and Q-function estimation in reinforcement learning. Describe why combining temporal-difference updates with nonlinear function approximation can cause instability or divergence. List and explain standard remedies (experience replay, target networks, double Q-learning, gradient clipping, batch normalization) that address these issues.

Describe the Policy Gradient framework and derive the REINFORCE (Monte Carlo policy gradient) estimator. Present the policy gradient theorem and the empirical estimator

$$\nabla_\theta J(\theta)=\mathbb{E}_{\tau}\left[\sum_t\nabla_\theta\log\pi_\theta(a_t\mid s_t)G_t\right]\;,$$

explain the role of the return $G_t$, and discuss variance reduction using a baseline. Outline how an actor-critic algorithm implements a learned baseline and briefly contrast actor-critic with pure policy-gradient methods.