Title: Reinforcement Learning
Tags: Chapter-2

Q: What is the most important feature distinguishing reinforcement learning from other types of learning?
A: RL uses training information that evaluates the actions taken rather than instructs by giving correct actions

Q: What is the basis of supervised learning?
A: Purely instructive feedback

Q: Describe k-armed Bandit Problem
A: You are faced repeatedly with a choice among \(k\) different options, or actions. After each choice you receive a numerical reward chosen from a stationary probability distribution that depends on the action you selected. Your objective is to maximize the expected total reward over some time period, for example, over 1000 action selections, or time steps

Q: What is the difference between exploitation and exploration?
A: Exploitation is the right thing to do to maximize the expected reward on the one step, but exploration may produce the greater total reward in the long run.
If you maintain estimates of the action values, then at any time step there is at least one action whose estimated value is greatest. We call these the greedy actions. When you
select one of these actions, we say that you are exploiting your current knowledge of the values of the actions. If instead you select one of the nongreedy actions, then we say you are exploring, because this enables you to improve your estimate of the nongreedy action’s value.
The need to balance exploration and exploitation is a distinctive challenge that arises in reinforcement

Q: What are action-value methods?
A: Methods for estimating the values of actions and for using the estimates to make action selection decisions

Q: What is sample-average method?
A: A way to estimate action values by averaging the rewards actually received:
\[Q_t(a) = \frac{\text{sum of rewards when a taken prior to t}}{\text{number of times a taken prior to t}} = \frac{\sum^{t - 1}_{i = i}R_i\mathbb{1}_{A_i = a}}{\sum^{t - 1}_{i = i}\mathbb{1}_{A_i = a}}\]

Q: What is \(\epsilon\)-greedy methods
A: Greedy action selection always exploits current knowledge to maximize immediate reward; it spends no time at all sampling apparently inferior actions to see if they might really be better. A simple alternative is to behave greedily most of the time, but every once in a while, say with small probability \(\epsilon\) , instead select randomly from among all the actions with equal probability, independently of the action-value estimates

Q: In \(\epsilon\)-greedy action selection, for the case of two actions and \(\epsilon = 0.5\), what is the probability that the greedy action is selected?
A: The final answer is 75%.
The \(\epsilon\)-greedy algorithm has two distinct branches: Exploitation and Exploration. The greedy action can be chosen in both branches, which is the key to the problem. Let's assume Action A is the greedy action and Action B is the non-greedy one.
Path 1: The "Exploitation" Branch
The agent decides to exploit with probability  
- In this case, $1 - 0.5 = 0.5$ (or 50%).
- When the agent exploits, it always chooses the greedy action (Action A) by definition.
- So, this path contributes a 50% chance of selecting the greedy action.
Path 2: The "Exploration" Branch
The agent decides to explore with probability. When the agent explores, it chooses a random action uniformly from all available actions. Since there are 2 actions (A and B), the agent will pick Action A (the greedy one) with a probability of \(0.5 \times 0.5 = 0.25\)
The Final Solution
To get the total probability of the greedy action being selected, we add the probabilities from these two mutually exclusive paths:
\[P(\text{Greedy}) = P(\text{Exploit Path}) + P(\text{Explore Path}) = (1 - \epsilon) + 0.25 = 0.75\]
The general formula for the probability of selecting the greedy action in \(\epsilon\)-greedy is:
\[P(\text{Greedy Action}) = (1 - \epsilon) + (\frac{\epsilon}{k})\]
where \(k\) is the number of actions. In this case \(k = 2\). This logic is the foundation for the "exploration vs. exploitation" trade-off.

Q: Prove mathematically
\((1 - \alpha)^n + \sum_{i=1}^{n} \alpha(1 - \alpha)^{n-i} = 1\)
which is stated in section 2.5 on page 33 from the expanded Equation 2.6 in the book, which expands the update rule to show how \(Q_{n+1}\) relates to all past rewards and the initial estimate \(Q_1\)
A: \[\begin{equation} \begin{split} (1 - \alpha)^n + \sum_{i=1}^{n} \alpha(1 - \alpha)^{n-i} &= (1 - \alpha)^n + \alpha\left[ (1-\alpha) + (1-\alpha)^2 + \dots + (1-\alpha)^{n-1}\right] \\ &= (1-\alpha)^n + \alpha\frac{1-(1-\alpha)^n}{\alpha} \\ &= 1 \end{split} \end{equation}\]
We used formula for summing up geometri series:
\[\sum_{k=0}^{n-1} a r^k = S_n = \frac{a(1-r^n)}{1-r}\]