## Problem
You are faced repeatedly with a choice among n 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.

## Exploring and exploiting
Let expected or mean of reward of each action be called its *value*. At any time step if we choose best possible action as highest of our observed values of all actions. We call such action *greedy* and this process is called *exploiting*. If we choose one of the nongreedy action, this process will be called *exploration* because this may improve observed values of nongreedy actions which may be optimal.

## Action value method
we denote the true (actual) value of action a as $q∗(a)$, and the estimated value on the tth time step as $Q_t(a)$. If by the $t^{th}$ time step action $a$ has been chosen $K_a$ times prior to $t$, yielding rewards $R_1, R_2,...R_{K_a}$, then its value is estimated to be: 
$$Q_t(a) = \frac{R_1 + R_2 + .... + R_{K_a}}{K_a}$$

We choose explore with probability $\epsilon$ and choose greedy action with probability $(1-\epsilon)$ i.e Action with max $Q_t(a)$. This way of near greedy selection is called $\epsilon-$greedy method

## Softmax action selection

In Softmax action selection we choose *Exploration* action based on ranking given by *softmax action selection rules*. One method of ranking is *Gibbs, or Boltzmann, distribution*. It
chooses action $a$ on the $t^{th}$ time step with probability, $$\frac{e^{Q_t(a)/\tau}}{\sum_{i=1}^{n}{e^{Q_t(i)/\tau}}}$$


#### Optimized way to update mean
Let mean at time t is $m_t$. Let new observation at time $t+1$ is $x_{t+1}$.
$$
\begin{align}
m_t &= \frac{x_1 + x_2 + ....... + x_t}{t} \tag{1} \\
m_{t+1} &= \frac{x_1 + x_2 + ....... + x_t + x_{t+1}}{t+1} \\
&= \frac{m_t*t + x_{t+1}}{t+1} && \text{by (1)} \\
&= \frac{m_t*t + m_t -m_t + x_{t+1}}{t+1}  \\
&= \frac{m_t(t + 1) + (x_{t+1}-m_t)}{t+1}  \\
m_{t+1} &= m_t + \frac{x_{t+1}-m_t}{t+1}
\end{align}
$$




```python
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sb
%matplotlib inline
```


```python
#np.random.seed(seed=2017)

# Environment code
class Bandit:
    def __init__(self,n):
        self.n = n
        self.q_star_arr = np.random.normal(size=self.n)
        
    # get reward R
    def reward(self,a): 
        return np.random.normal(loc=self.q_star_arr[a])
    
    def getOptimal(self):
        return self.q_star_arr.argmax()
```


```python
class ActionValue:
    def __init__(self,n,epsilon,bandit,max_t = 1000):
        self.n = n
        self.bandit = bandit
        self.max_t = max_t
        self.Qta = np.zeros(n)
        self.Ka = np.zeros(n,dtype=int)
        self.optimalHistory = np.zeros(max_t)
        self.epsilon = epsilon        
        self.rewardHistory = np.zeros(max_t)
        self.algoRun()
    
    def algoRun(self):
        for t in range(self.max_t):
            greedyAction = self.Qta.argmax()
            
            if np.random.rand() < self.epsilon:#exploring
                curAction = np.random.randint(self.n -1)            
                #not to use greedyAction so
                if curAction>=greedyAction:
                    curAction += 1
            else:#exploiting
                curAction = greedyAction
                
            self.optimalHistory[t] = 1 if curAction == self.bandit.getOptimal() else 0
            curActionReward = self.bandit.reward(curAction)
            self.rewardHistory[t] = curActionReward
            self.Ka[curAction] += 1
            #update Qt(a)
            self.Qta[curAction] += (curActionReward - self.Qta[curAction])/self.Ka[curAction]            
            
# n =10
# bandit = Bandit(10)
# print(bandit.q_star_arr)
# max_t = 1000
# a1 = ActionValue(n,0.1,bandit,max_t=max_t)
# a1.algoRun()
# print(a1.Ka)
# a2 = ActionValue(n,0.01,bandit,max_t=max_t)
# a2.algoRun()
# print(a2.Ka)
# a3 = ActionValue(n,0.0,bandit,max_t=max_t)
# a3.algoRun()
# print(a3.Ka)
```


```python
class SoftmaxAction:
    def __init__(self,n,tau,bandit,max_t = 1000):
        self.n = n
        self.tau = tau
        self.bandit = bandit
        self.max_t = max_t
        self.Qta = np.zeros(n)
        self.Ka = np.zeros(n,dtype=int)
        self.optimalHistory = np.zeros(max_t)
        self.rewardHistory = np.zeros(max_t)
        self.algoRun()
    
    def algoRun(self):
        for t in range(self.max_t):
            probArray = np.exp(self.Qta/ self.tau) 
            probArray = probArray / sum(probArray)                
            actionList = list(range(len(self.Qta)))
            curAction = np.random.choice(actionList,p=probArray)
            self.optimalHistory[t] = 1 if curAction == self.bandit.getOptimal() else 0
            curActionReward = self.bandit.reward(curAction)
            self.rewardHistory[t] = curActionReward
            self.Ka[curAction] += 1
            #update Qt(a)
            self.Qta[curAction] += (curActionReward - self.Qta[curAction])/self.Ka[curAction]            

```


```python
class SoftmaxEpsilonGreedyAction:
    def __init__(self,n,epsilon,tau,bandit,max_t = 1000):
        self.n = n
        self.tau = tau
        self.bandit = bandit
        self.max_t = max_t
        self.Qta = np.zeros(n)
        self.Ka = np.zeros(n,dtype=int)
        self.optimalHistory = np.zeros(max_t)
        self.epsilon = epsilon        
        self.rewardHistory = np.zeros(max_t)
        self.algoRun()
    
    def algoRun(self):
        for t in range(self.max_t):
            greedyAction = self.Qta.argmax()
            
            if np.random.rand() < self.epsilon:#exploring
                probArray = np.exp(self.Qta/ self.tau) 
                actionList = list(range(len(self.Qta)))
                #not to use greedyAction so
                actionList.remove(greedyAction)
                probArray = np.delete(probArray, greedyAction)
                
                probArray = probArray / sum(probArray)
                curAction = np.random.choice(actionList,p=probArray)                
            else:#exploiting
                curAction = greedyAction
                
            self.optimalHistory[t] = 1 if curAction == self.bandit.getOptimal() else 0
            curActionReward = self.bandit.reward(curAction)
            self.rewardHistory[t] = curActionReward
            self.Ka[curAction] += 1
            #update Qt(a)
            self.Qta[curAction] += (curActionReward - self.Qta[curAction])/self.Ka[curAction]            
            
```


```python
class TestBed:
    def __init__(self, n, epsilon,tau,algoType,max_t = 1000):
        self.n = n
        self.maxExp = 2000
        self.max_t = max_t        
        self.epsilon = epsilon 
        self.tau = tau
        self.averageRewardHistory = np.zeros(self.max_t)
        self.averageOptimalHistory = np.zeros(self.max_t)
        
        for i in range(self.maxExp):            
            bandit = Bandit(n)
            if algoType=="ActionValue":
                exp = ActionValue(self.n,self.epsilon,bandit,max_t=self.max_t)
            elif algoType=="SoftmaxAction":
                exp = SoftmaxAction(self.n,self.tau,bandit,max_t=self.max_t)
            elif algoType=="SoftmaxEpsilonGreedyAction":
                exp = SoftmaxEpsilonGreedyAction(self.n,self.epsilon,self.tau,bandit,max_t=self.max_t)
                
            self.averageRewardHistory += exp.rewardHistory            
            self.averageOptimalHistory += exp.optimalHistory            
            
        self.averageRewardHistory /= self.maxExp
        self.averageOptimalHistory *= 100.0/self.maxExp
```


```python
n =10
max_t =1000
a2 = TestBed(n,0.01,None,"ActionValue",max_t)
a3 = TestBed(n,0.0,None,"ActionValue",max_t)
a4 = TestBed(n,None,0.2,"SoftmaxAction",max_t)
a5 = TestBed(n,None,0.05,"SoftmaxAction",max_t)
a6 = TestBed(n,0.01,0.2,"SoftmaxEpsilonGreedyAction",max_t)
a7 = TestBed(n,0.01,0.05,"SoftmaxEpsilonGreedyAction",max_t)



```


```python
t = range(max_t)
plt.plot(t,a2.averageRewardHistory,label='ActionValue: epsilon=0.01')
plt.plot(t,a3.averageRewardHistory,label='ActionValue: epsilon=0.0')
plt.plot(t,a4.averageRewardHistory,label='SA: tau=0.2')
plt.plot(t,a5.averageRewardHistory,label='SA: tau=0.05')
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
plt.show()
```


```python
plt.plot(t,a2.averageOptimalHistory,label='ActionValue: epsilon=0.01')
plt.plot(t,a3.averageOptimalHistory,label='ActionValue: epsilon=0.0')
plt.plot(t,a4.averageOptimalHistory,label='SA: tau=0.2')
plt.plot(t,a5.averageOptimalHistory,label='SA: tau=0.05')
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
plt.show()
```


```python
plt.plot(t,a2.averageRewardHistory,label='ActionValue: epsilon=0.01')
plt.plot(t,a3.averageRewardHistory,label='ActionValue: epsilon=0.0')
plt.plot(t,a6.averageRewardHistory,label='SEGA: epsilon=0.01 tau=0.2')
plt.plot(t,a7.averageRewardHistory,label='SEGA: epsilon=0.01 tau=0.05')
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
plt.show()
```


```python
plt.plot(t,a2.averageOptimalHistory,label='ActionValue: epsilon=0.01')
plt.plot(t,a3.averageOptimalHistory,label='ActionValue: epsilon=0.0')
plt.plot(t,a6.averageOptimalHistory,label='SEGA: epsilon=0.01 tau=0.2')
plt.plot(t,a7.averageOptimalHistory,label='SEGA: epsilon=0.01 tau=0.05')
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
plt.show()
```


```python
a8 = TestBed(n,None,0.1,"SoftmaxAction",max_t)
a9 = TestBed(n,None,0.15,"SoftmaxAction",max_t)
a10 = TestBed(n,0.1,0.15,"SoftmaxEpsilonGreedyAction",max_t)
a11 = TestBed(n,0.1,0.2,"SoftmaxEpsilonGreedyAction",max_t)
```


```python
plt.plot(t,a2.averageOptimalHistory,label='ActionValue: epsilon=0.01')
plt.plot(t,a3.averageOptimalHistory,label='ActionValue: epsilon=0.0')
plt.plot(t,a8.averageOptimalHistory,label='SA: tau=0.1')
plt.plot(t,a9.averageOptimalHistory,label='SA: tau=0.15')
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
plt.show()
```


```python
plt.plot(t,a2.averageOptimalHistory,label='ActionValue: epsilon=0.01')
plt.plot(t,a3.averageOptimalHistory,label='ActionValue: epsilon=0.0')
plt.plot(t,a10.averageOptimalHistory,label='SEGA: epsilon=0.1 tau=0.15')
plt.plot(t,a11.averageOptimalHistory,label='SEGA: epsilon=0.1 tau=0.2')
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
plt.show()
```


```python
plt.plot(t,a2.averageOptimalHistory,label='ActionValue: epsilon=0.01')
plt.plot(t,a9.averageOptimalHistory,label='SA: tau=0.15')
plt.plot(t,a10.averageOptimalHistory,label='SEGA: epsilon=0.1 tau=0.15')
plt.plot(t,a11.averageOptimalHistory,label='SEGA: epsilon=0.1 tau=0.2')
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
plt.show()
```


```python

```

da164d55472a948ea23d95453ae9bc308675e37f
ipynb
Jupyter Notebook
notebooks/Reinforcement_learning/RL_Part_1_ArmedBandit_Softmax.ipynb
rakesh-malviya/MLCodeGems
b9b2b4c2572f788724a7609499b3adee3a620aa4
Apache-2.0
2020-02-19T14:42:57.000Z
2020-02-19T14:42:57.000Z
notebooks/Reinforcement_learning/RL_Part_1_ArmedBandit_Softmax.ipynb
rakesh-malviya/MLCodeGems
b9b2b4c2572f788724a7609499b3adee3a620aa4
Apache-2.0
notebooks/Reinforcement_learning/RL_Part_1_ArmedBandit_Softmax.ipynb
rakesh-malviya/MLCodeGems
b9b2b4c2572f788724a7609499b3adee3a620aa4
Apache-2.0
2017-11-09T11:09:31.000Z
2020-12-17T06:38:28.000Z
Qwen/Qwen-72B
1. YES
2. YES