Hello reader, this blog is an attempt to keep the theory in the back of my mind as we get progressively swarmed with more RL papers. For this one particularly, the content follows the outline of the RL course that I took in my undergrad and I want to thank Prof. Kalyanakrishnan for teaching the course in a way such that I can look back to it even 3 years later.

Before we had multi-agent systems, we started from a much simpler case: repeated single decisions and no state. These are called multi-armed bandits. Add states and transitions to this, and we get Markov Decision processes (MDPs). But the transition and reward dynamics are still known. Now take that knowledge away, and you have what we call “RL.” Drop the single-agent assumption on top of that, and we get to multi-agent systems.

flowchart TD
    A["Multi-Armed Bandits"]
    B["Markov Decision Processes"]
    C["Reinforcement Learning"]
    D["Multi-Agent Systems"]

    A -->|"add states & transitions"| B
    B -->|"remove knowledge of dynamics"| C
    C -->|"drop the single-agent assumption"| D

Multi-Armed Bandits

Setup: you have multiple options to choose from and each option has a mean reward (that you don’t know). Your objective is to maximize your mean reward. What strategy do you use?

In the literature, option = arms. Why bandits? because whoever named it liked slot machines that robbed you of money. Hence, bandits. Now, the only way to figure out which arm to pull is explore arms and see which ones seem the best and then focusing on them. This gives the notion of a typical explore-exploit conundrum that differentiates algorithms that try to solve this problem.

Problem definition:

Set of Arms: \(A = \{1, 2, \dots, n\}\) where each arm \(a \in A\) is associated with a Bernoulli reward distribution with unknown mean \(p_a \in [0, 1]\).

At every iteration this happens: Given the history \(h^t = (a^0, r^0, \cdots, a^{t-1}, r^{t - 1})\) ,an arm \(a^t\) is sampled (or pulled) and a reward \(r^t\) is obtained. \(T\) is the total number of iterations, also called the horizon.

Let \(H\) denote the set of all possible histories till time t and let \(\Delta(A)\)¹ denote the set of all probability distributions over the arms.

A randomized algorithm is a mapping

Regret

Any algorithm wants to maximize the cumulative reward it obtains. The maximum reward that an algorithm can obtain over the horizon \(T\) is \(Tp^{*}\) (where \(p^*\) is the max avg. reward of an arm). The regret of an algorithm is defined by

Ideally, in the limit we would want regret to grow sub-linearly i.e. \(\lim_{T \to \infty} \frac{R_T}{T} = 0\).

Now, how to achieve sub-linear regret?

GLIE

1. You need to have infinite exploration: each arm must almost surely be pulled an infinite number of times. Without that there could be teeny tiny probability that you never explored the most optimal arm and not exploring that leads to a regret that grows linearly with \(T\) (can be proved).

2. The number of pulls that are greedy w.r.t. the empirical mean upto the horizon should be = T in the limit (abusing the notation a bit).

UCB [2002]

UCB is perhaps one of the most famous algorithms for multi-armed bandits. It achieves \(O(log(T))\) regret. The way it works is this:

At time t, define \(\text{ucb}_a^t = \hat{p}_a^t + \sqrt{\frac{2\ln(t)}{u_a^t}}\). Pull the arm with higest ucb.

\(\hat{p}_a^t\) = empirical mean of rewards from arm a,
\(u_a^t\) = number of times a has been pulled till time t

The correction factor \(\sqrt{\frac{2\ln(t)}{u_a^t}}\) is coming from the hoeffding inequality. From hoeffding we have,

\(\mathbb{P}(p > \hat{p} + \epsilon) \leq e^{-2u\epsilon^2}\).
In the ucb case, the original authors chose the confidence interval to be \(t^{-4}\). \(e^{-2u\epsilon^2} = t^{-4} \implies \epsilon = \sqrt{\frac{2\ln(t)}{u}}\)

KL-UCB

Heavy terms coming, but we will break it down.

where KL refers to KL divergence. Same drill as ucb, pick the arm with the highest ucb-kl term. In the above formula, q is supposed to represent the candidate values for the arm’s true mean. \(\mathrm{KL}(\hat{p}_a^t, q)\) captures how different true mean is from observed empirical mean. That is further scaled by the number of times that arm has been pulled. Theoretically, this is coming from the Chernoff bound:

In the kl-ucb case, the original authors chose the confidence interval to be \(\frac{1}{t(lnt)^c}\).

Thompson Sampling

Thompson sampling primarily utilizes beta distribution. If at time t, an arm a has \(s_{a}^t\) successes and \(f_{a}^t\) failures then the beta distribution represents a belief about \(p_a\).
\(x_a^{t}\) is sampled for each arm.

\(x_a^{t} ~ \beta(s_a^{t} + 1, f_a^{t} + 1)\).
In the next iteration the arm with the max \(x_a^{t}\) is pulled. Futher analysis is out of scope.

Markov decision Problems (MDPs)

Coming soon…