Thompson sampling is one approach for Multi Armed Bandits problem and about the Exploration-Exploitation dilemma faced in reinforcement learning.
Challenge in solving such a problem is that we might end up fetching the same arm again and again. Bayesian approach helps us solving this dilemma by setting prior with somewhat high variance.
Here is the code for two armed bandit. One has success probability of 40% (bandit 0) and another has 25% (bandit 1).
We are using beta distribution for deciding which arm to pull. Beta distribution has two parameter alpha and beta. Higher values of alpha, pulls distribution towards 1. Beta distribution is always confined between 0 and 1.
How we train is that for each feedback we receive we increment alpha by 1 if it was success or beta by 1 in case of failure. For choosing the arm we draw random sample from the distribution of each arm and select the arm with highest value.
And here is simulation results. We see that initially both the the armed are pulled frequently but slowly arm 1 is pulled less and less, but it is never straight away zero.
Formula for multivariate gaussian distribution
Formula of univariate gaussian distribution
- There is normality constant in both equations
- Σ being a positive definite ensure quadratic bowl is downwards
- σ2 also being positive ensure that parabola is downwards
On Covariance Matrix
Definition of covariance between two vectors:
When we have more than two variable we present them in matrix form. So covariance matrix will look like
- Formula of multivariate gaussian distribution demands Σ to be singular and symmetric positive semidefinite, which in terms means sigma will be symmetric positive semidefinite.
- For some data above demands might not meet
Following derivations are available at :
- We can prove that when covariance matrix is diagonal (i.e there is variables are independent) multivariate gaussian distribution is simply multiplication of single gaussian distribution of each variable.
- It was derived that shape of isocontours (figure 1) is elliptical and axis length is proportional to individual variance of that variable
- Above is true even when covariance matrix is not diagonal and for dimension n>2 (ellipsoids)
Linear Transformation Interpretation
This was proved in two steps :
Step-1 : Factorizing covariance matrix
Step-2 : Change of variables, which we apply to density function