Multi Armed Bandit (MAB)

Hola, I'm back! Was on a hiatus post baby and now I will try to write more regularly. So, lets get started. The multi-armed bandit problem was formulated in the 50s and is as follows: Suppose there are N slot machines (arms) and the player has to decide which machine to play. Each machine has an unknown probability of distributing a reward and the player has to decide which machines to play and in what order in order to maximize the reward. Note that the probability of reward generation of each machine is unknown otherwise the reward is maximized by simply picking up the machine with the largest probability. This problem has huge applications. For example, ad recommendation, news recommendation, in a clinical trial while trying to come up with the best treatment or in the portfolio management of the stocks.

The problem of choosing the best arm is complicated by the stochastic nature of the slot machines. A sub-optimal machine could generate a reward by random chance and similarly an optimal machine could not perform by chance. This gives rise to the principle of Exploration vs Exploitation . The exploration-exploitation tradeoff is the dilemma faced by the player in exploiting the current best strategy or in exploring the space and trying out a sub-optimal strategy in order to understand the users response. There are many mathematical models in place in trying to come up with an optimal solution and some of the popularly used approximate solutions are as follows:

ε greedy The approach is as follows: With a probability (1 - ε) play the machine with the largest probability and with a probability ε try a random machine.

Upper Confidence Bound (UCB) In the beginning play each machine atleast once. After that at each time t proceed by picking up the machine i that maximizes: 
x̄i + √ (2lnt/T)
where x̄i is the mean of the reward of machine i and T is the number of times the machine has been played. This is one of the most popular algorithm for the MAB problem and there are strong theoretical guarantees on the regret bounds for this algorithm.

Thompson Sampling This approach is gaining importance recently with emperical results shows their better performance as compared to the other methods. The idea behind this approach is to sample from the posterior for the mean value for each arm.

Comments

Post a Comment

Popular posts from this blog

MinHash, Bloom Filters and LSH

Lets talk about some large scale algorithms widely used in the document world. MinHash: Minhash is a really cute algorithm to determine how does a document compare to another. One simple way to compute document similarity is to compute the jaccard similarity between them. The jaccard similarity between the documents is computed as follows: def jaccard_similarity(set1: set, set2: set): if len(set1) == 0 or len(set2) == 0: return 0.0 common = len(set1.intersection(set2)) if common == 0: return 0.0 union = len(set1.union(set2)) return common / union One problem with Jaccard similarity is that it can take a lot of time to compute especially for large scale documents. The idea behind minhashing is to first operate on the space of document shingles. Shingles are basically any combination of k consecutive words of the document. For example, for the sentence "hi i am jaya" the possible 3 shingles are "hi i am" and "i am jaya...
Read more

Perceptron Algorithm

Image
The perceptron algorithm is a linear classifier using a linear function (w'x + b) to classify the points into two classes. The loss function for the perceptron algorithm just counts the points misclassified and then incrementally adjusts the weight vector and thus the decision boundary to appropriately classify the two classes. Perhaps this is the simplest algorithm one can think of to update the weight vector and is shown as follows: w(k+1) = w(k) + yt*xt if yt ≠ f(xt; w) i.e. we cycle through the training points and adjust the weight vector only if the points are misclassified. Note that our class labels are -1 and 1 and hence if the points are misclassified then y_t* f(xt; w) will be negative. In order to understand why the seemingly simple update rule works and leads to a convergence, lets closely examine it. One of the underlying assumption in the perceptron model is that the points are linearly separated hence there exists an w* such that y_t * f(xt; w*) ≥ γ for all...
Read more

Logistic Regression

The logistic regression method even though called regression has a unique ability to give posterior probability values for a data point to belong to a particular class and hence serve as a discriminative function useful for classification. The idea is simple, to use the logistic sigmoid function on the linear function of feature vector. p(y = 1| x) = σ(w'x +b) The likelihood function can be written as p(t|w) = Π y_i^t_i*(1 - y_i)^(1 - t_i) ln p(t|w) = Σ t_i*ln(y_i) + (1 - t_i)*ln(1 - y_i) The error function is computed by taking the negative of the log likelihood function and is computed as follows: E(w) = -ln p(t|w) Now, ∇E(w) is computed as follows: y = 1 / (1 + exp(-w'x) Taking derivative of both sides, ∇y/∇w = exp(-w'x)(x)/(1 + exp(-w'x))^2 ∇y/∇w = xy(1-y) Substituting the value in ∇E(w), we get ∇ E(w) = Σ (y_i - t_i)*x_i The derivative of the error function is similar to the least squares problem, although w...
Read more