(b) Reinforcement Learning:

Definition: Paradigm where agent learns optimal policy $\pi^*:S\to A$ by interacting with environment and maximizing cumulative reward, not from labeled examples but from delayed reward signal.

Components: Agent, Environment, State $s$, Action $a$, Reward $r$, Policy $\pi$, Value $V^\pi, Q^\pi$, Model $p(s'|s,a)$, discount $\gamma$.

Types:

• Model-free: No explicit model; directly learn $V/Q/\pi$. Value-based (Q-learning $Q(s,a)\leftarrow Q+\alpha[r+\gamma\max Q(s',a')-Q]$), Policy-based (REINFORCE $
  abla J=E[
  abla\log\pi(a|s) Q]$), Actor-Critic.
• Model-based: Learn/know $p(s'|s,a)$, plan via DP (Value Iteration, MCTS in AlphaGo).
• On-policy (SARSA) learns about $\pi$ being followed; off-policy (Q-learning) learns about optimal $\pi$ from any behavior.

Exploration-Exploitation: $\epsilon$-greedy, UCB, Thompson, entropy regularization.

Algorithms: Q-learning, SARSA, DQN (deep $Q$ with replay + target network), Policy Gradient, PPO, A3C.

Challenges: Credit assignment (delayed reward), exploration, instability, sample inefficiency.

Applications: Game playing (AlphaGo, Atari DQN), robotics control, autonomous driving, recommender systems (long-term engagement), finance trading.

Example: Grid maze: states = cells, actions = up/down/left/right, reward +10 goal, -1 wall, agent via Q-learning propagates values back from goal to learn shortest path.

Differences vs supervised: No correct output provided, only reward; sequential, action affects next state (non-i.i.d).

Rewards shape behavior; reward engineering crucial.