The Reasonable Effectiveness of the Multiplicative Weights Update Algorithm

papad

Christos Papadimitriou, who studies multiplicative weights in the context of biology.

Hard to believe

Sanjeev Arora and his coauthors consider it “a basic tool [that should be] taught to all algorithms students together with divide-and-conquer, dynamic programming, and random sampling.” Christos Papadimitriou calls it “so hard to believe that it has been discovered five times and forgotten.” It has formed the basis of algorithms in machine learning, optimization, game theory, economics, biology, and more.

What mystical algorithm has such broad applications? Now that computer scientists have studied it in generality, it’s known as the Multiplicative Weights Update Algorithm (MWUA). Procedurally, the algorithm is simple. I can even describe the core idea in six lines of pseudocode. You start with a collection of n objects, and each object has a weight.

Set all the object weights to be 1.
For some large number of rounds:
   Pick an object at random proportionally to the weights
   Some event happens
   Increase the weight of the chosen object if it does well in the event
   Otherwise decrease the weight

The name “multiplicative weights” comes from how we implement the last step: if the weight of the chosen object at step t is w_t before the event, and G represents how well the object did in the event, then we’ll update the weight according to the rule:

\displaystyle w_{t+1} = w_t (1 + G)

Think of this as increasing the weight by a small multiple of the object’s performance on a given round.

Here is a simple example of how it might be used. You have some money you want to invest, and you have a bunch of financial experts who are telling you what to invest in every day. So each day you pick an expert, and you follow their advice, and you either make a thousand dollars, or you lose a thousand dollars, or something in between. Then you repeat, and your goal is to figure out which expert is the most reliable.

This is how we use multiplicative weights: if we number the experts 1, \dots, N, we give each expert a weight w_i which starts at 1. Then, each day we pick an expert at random (where experts with larger weights are more likely to be picked) and at the end of the day we have some gain or loss G. Then we update the weight of the chosen expert by multiplying it by (1 + G / 1000). Sometimes you have enough information to update the weights of experts you didn’t choose, too. The theoretical guarantees of the algorithm say we’ll find the best expert quickly (“quickly” will be concrete later).

In fact, let’s play a game where you, dear reader, get to decide the rewards for each expert and each day. I programmed the multiplicative weights algorithm to react according to your choices. Click the image below to go to the demo.

mwua

This core mechanism of updating weights can be interpreted in many ways, and that’s part of the reason it has sprouted up all over mathematics and computer science. Just a few examples of where this has led:

  1. In game theory, weights are the “belief” of a player about the strategy of an opponent. The most famous algorithm to use this is called Fictitious Play, and others include EXP3 for minimizing regret in the so-called “adversarial bandit learning” problem.
  2. In machine learning, weights are the difficulty of a specific training example, so that higher weights mean the learning algorithm has to “try harder” to accommodate that example. The first result I’m aware of for this is the Perceptron (and similar Winnow) algorithm for learning hyperplane separators. The most famous is the AdaBoost algorithm.
  3. Analogously, in optimization, the weights are the difficulty of a specific constraint, and this technique can be used to approximately solve linear and semidefinite programs. The approximation is because MWUA only provides a solution with some error.
  4. In mathematical biology, the weights represent the fitness of individual alleles, and filtering reproductive success based on this and updating weights for successful organisms produces a mechanism very much like evolution. With modifications, it also provides a mechanism through which to understand sex in the context of evolutionary biology.
  5. The TCP protocol, which basically defined the internet, uses additive and multiplicative weight updates (which are very similar in the analysis) to manage congestion.
  6. You can get easy \log(n)-approximation algorithms for many NP-hard problems, such as set cover.

Additional, more technical examples can be found in this survey of Arora et al.

In the rest of this post, we’ll implement a generic Multiplicative Weights Update Algorithm, we’ll prove it’s main theoretical guarantees, and we’ll implement a linear program solver as an example of its applicability. As usual, all of the code used in the making of this post is available in a Github repository.

The generic MWUA algorithm

Let’s start by writing down pseudocode and an implementation for the MWUA algorithm in full generality.

In general we have some set X of objects and some set Y of “event outcomes” which can be completely independent. If these sets are finite, we can write down a table M whose rows are objects, whose columns are outcomes, and whose i,j entry M(i,j) is the reward produced by object x_i when the outcome is y_j. We will also write this as M(x, y) for object x and outcome y. The only assumption we’ll make on the rewards is that the values M(x, y) are bounded by some small constant B (by small I mean B should not require exponentially many bits to write down as compared to the size of X). In symbols, M(x,y) \in [0,B]. There are minor modifications you can make to the algorithm if you want negative rewards, but for simplicity we will leave that out. Note the table M just exists for analysis, and the algorithm does not know its values. Moreover, while the values in M are static, the choice of outcome y for a given round may be nondeterministic.

The MWUA algorithm randomly chooses an object x \in X in every round, observing the outcome y \in Y, and collecting the reward M(x,y) (or losing it as a penalty). The guarantee of the MWUA theorem is that the expected sum of rewards/penalties of MWUA is not much worse than if one had picked the best object (in hindsight) every single round.

Let’s describe the algorithm in notation first and build up pseudocode as we go. The input to the algorithm is the set of objects, a subroutine that observes an outcome, a black-box reward function, a learning rate parameter, and a number of rounds.

def MWUA(objects, observeOutcome, reward, learningRate, numRounds):
   ...

We define for object x a nonnegative number w_x we call a “weight.” The weights will change over time so we’ll also sub-script a weight with a round number t, i.e. w_{x,t} is the weight of object x in round t. Initially, all the weights are 1. Then MWUA continues in rounds. We start each round by drawing an example randomly with probability proportional to the weights. Then we observe the outcome for that round and the reward for that round.

# draw: [float] -> int
# pick an index from the given list of floats proportionally
# to the size of the entry (i.e. normalize to a probability
# distribution and draw according to the probabilities).
def draw(weights):
    choice = random.uniform(0, sum(weights))
    choiceIndex = 0

    for weight in weights:
        choice -= weight
        if choice <= 0:
            return choiceIndex

        choiceIndex += 1

# MWUA: the multiplicative weights update algorithm
def MWUA(objects, observeOutcome, reward, learningRate numRounds):
   weights = [1] * len(objects)
   for t in numRounds:
      chosenObjectIndex = draw(weights)
      chosenObject = objects[chosenObjectIndex]

      outcome = observeOutcome(t, weights, chosenObject)
      thisRoundReward = reward(chosenObject, outcome)

      ...

Sampling objects in this way is the same as associating a distribution D_t to each round, where if S_t = \sum_{x \in X} w_{x,t} then the probability of drawing x, which we denote D_t(x), is w_{x,t} / S_t. We don’t need to keep track of this distribution in the actual run of the algorithm, but it will help us with the mathematical analysis.

Next comes the weight update step. Let’s call our learning rate variable parameter \varepsilon. In round t say we have object x_t and outcome y_t, then the reward is M(x_t, y_t). We update the weight of the chosen object x_t according to the formula:

\displaystyle w_{x_t, t} = w_{x_t} (1 + \varepsilon M(x_t, y_t) / B)

In the more general event that you have rewards for all objects (if not, the reward-producing function can output zero), you would perform this weight update on all objects x \in X. This turns into the following Python snippet, where we hide the division by B into the choice of learning rate:

# MWUA: the multiplicative weights update algorithm
def MWUA(objects, observeOutcome, reward, learningRate, numRounds):
   weights = [1] * len(objects)
   for t in numRounds:
      chosenObjectIndex = draw(weights)
      chosenObject = objects[chosenObjectIndex]

      outcome = observeOutcome(t, weights, chosenObject)
      thisRoundReward = reward(chosenObject, outcome)

      for i in range(len(weights)):
         weights[i] *= (1 + learningRate * reward(objects[i], outcome))

One of the amazing things about this algorithm is that the outcomes and rewards could be chosen adaptively by an adversary who knows everything about the MWUA algorithm (except which random numbers the algorithm generates to make its choices). This means that the rewards in round t can depend on the weights in that same round! We will exploit this when we solve linear programs later in this post.

But even in such an oppressive, exploitative environment, MWUA persists and achieves its guarantee. And now we can state that guarantee.

Theorem (from Arora et al): The cumulative reward of the MWUA algorithm is, up to constant multiplicative factors, at least the cumulative reward of the best object minus \log(n), where n is the number of objects. (Exact formula at the end of the proof)

The core of the proof, which we’ll state as a lemma, uses one of the most elegant proof techniques in all of mathematics. It’s the idea of constructing a potential function, and tracking the change in that potential function over time. Such a proof usually has the mysterious script:

  1. Define potential function, in our case S_t.
  2. State what seems like trivial facts about the potential function to write S_{t+1} in terms of S_t, and hence get general information about S_T for some large T.
  3. Theorem is proved.
  4. Wait, what?

Clearly, coming up with a useful potential function is a difficult and prized skill.

In this proof our potential function is the sum of the weights of the objects in a given round, S_t = \sum_{x \in X} w_{x, t}. Now the lemma.

Lemma: Let B be the bound on the size of the rewards, and 0 < \varepsilon < 1/2 a learning parameter. Recall that D_t(x) is the probability that MWUA draws object x in round t. Write the expected reward for MWUA for round t as the following (using only the definition of expected value):

\displaystyle R_t = \sum_{x \in X} D_t(x) M(x, y_t)

 Then the claim of the lemma is:

\displaystyle S_{t+1} \leq S_t e^{\varepsilon R_t / B}

Proof. Expand S_{t+1} = \sum_{x \in X} w_{x, t+1} using the definition of the MWUA update:

\displaystyle \sum_{x \in X} w_{x, t+1} = \sum_{x \in X} w_{x, t}(1 + \varepsilon M(x, y_t) / B)

Now distribute w_{x, t} and split into two sums:

\displaystyle \dots = \sum_{x \in X} w_{x, t} + \frac{\varepsilon}{B} \sum_{x \in X} w_{x,t} M(x, y_t)

Using the fact that D_t(x) = \frac{w_{x,t}}{S_t}, we can replace w_{x,t} with D_t(x) S_t, which allows us to get R_t

\displaystyle \begin{aligned} \dots &= S_t + \frac{\varepsilon S_t}{B} \sum_{x \in X} D_t(x) M(x, y_t) \\ &= S_t \left ( 1 + \frac{\varepsilon R_t}{B} \right ) \end{aligned}

And then using the fact that (1 + x) \leq e^x (Taylor series), we can bound the last expression by S_te^{\varepsilon R_t / B}, as desired.

\square

Now using the lemma, we can get a hold on S_T for a large T, namely that

\displaystyle S_T \leq S_1 e^{\varepsilon \sum_{t=1}^T R_t / B}

If |X| = n then S_1=n, simplifying the above. Moreover, the sum of the weights in round T is certainly greater than any single weight, so that for every fixed object x \in X,

\displaystyle S_T \geq w_{x,T} \leq  (1 + \varepsilon)^{\sum_t M(x, y_t) / B}

Squeezing S_t between these two inequalities and taking logarithms (to simplify the exponents) gives

\displaystyle \left ( \sum_t M(x, y_t) / B \right ) \log(1+\varepsilon) \leq \log n + \frac{\varepsilon}{B} \sum_t R_t

Multiply through by B, divide by \varepsilon, rearrange, and use the fact that when 0 < \varepsilon < 1/2 we have \log(1 + \varepsilon) \geq \varepsilon - \varepsilon^2 (Taylor series) to get

\displaystyle \sum_t R_t \geq \left [ \sum_t M(x, y_t) \right ] (1-\varepsilon) - \frac{B \log n}{\varepsilon}

The bracketed term is the payoff of object x, and MWUA’s payoff is at least a fraction of that minus the logarithmic term. The bound applies to any object x \in X, and hence to the best one. This proves the theorem.

\square

Briefly discussing the bound itself, we see that the smaller the learning rate is, the closer you eventually get to the best object, but by contrast the more the subtracted quantity B \log(n) / \varepsilon hurts you. If your target is an absolute error bound against the best performing object on average, you can do more algebra to determine how many rounds you need in terms of a fixed \delta. The answer is roughly: let \varepsilon = O(\delta / B) and pick T = O(B^2 \log(n) / \delta^2). See this survey for more.

MWUA for linear programs

Now we’ll approximately solve a linear program using MWUA. Recall that a linear program is an optimization problem whose goal is to minimize (or maximize) a linear function of many variables. The objective to minimize is usually given as a dot product c \cdot x, where c is a fixed vector and x = (x_1, x_2, \dots, x_n) is a vector of non-negative variables the algorithm gets to choose. The choices for x are also constrained by a set of m linear inequalities, A_i \cdot x \geq b_i, where A_i is a fixed vector and b_i is a scalar for i = 1, \dots, m. This is usually summarized by putting all the A_i in a matrix, b_i in a vector, as

x_{\textup{OPT}} = \textup{argmin}_x \{ c \cdot x \mid Ax \geq b, x \geq 0 \}

We can further simplify the constraints by assuming we know the optimal value Z = c \cdot x_{\textup{OPT}} in advance, by doing a binary search (more on this later). So, if we ignore the hard constraint Ax \geq b, the “easy feasible region” of possible x‘s includes \{ x \mid x \geq 0, c \cdot x = Z \}.

In order to fit linear programming into the MWUA framework we have to define two things.

  1. The objects: the set of linear inequalities A_i \cdot x \geq b_i.
  2. The rewards: the error of a constraint for a special input vector x_t.

Number 2 is curious (why would we give a reward for error?) but it’s crucial and we’ll discuss it momentarily.

The special input x_t depends on the weights in round t (which is allowed, recall). Specifically, if the weights are w = (w_1, \dots, w_m), we ask for a vector x_t in our “easy feasible region” which satisfies

\displaystyle (A^T w) \cdot x_t \geq w \cdot b

For this post we call the implementation of procuring such a vector the “oracle,” since it can be seen as the black-box problem of, given a vector \alpha and a scalar \beta and a convex region R, finding a vector x \in R satisfying \alpha \cdot x \geq \beta. This allows one to solve more complex optimization problems with the same technique, swapping in a new oracle as needed. Our choice of inputs, \alpha = A^T w, \beta = w \cdot b, are particular to the linear programming formulation.

Two remarks on this choice of inputs. First, the vector A^T w is a weighted average of the constraints in A, and w \cdot b is a weighted average of the thresholds. So this this inequality is a “weighted average” inequality (specifically, a convex combination, since the weights are nonnegative). In particular, if no such x exists, then the original linear program has no solution. Indeed, given a solution x^* to the original linear program, each constraint, say A_1 x^*_1 \geq b_1, is unaffected by left-multiplication by w_1.

Second, and more important to the conceptual understanding of this algorithm, the choice of rewards and the multiplicative updates ensure that easier constraints show up less prominently in the inequality by having smaller weights. That is, if we end up overly satisfying a constraint, we penalize that object for future rounds so we don’t waste our effort on it. The byproduct of MWUA—the weights—identify the hardest constraints to satisfy, and so in each round we can put a proportionate amount of effort into solving (one of) the hard constraints. This is why it makes sense to reward error; the error is a signal for where to improve, and by over-representing the hard constraints, we force MWUA’s attention on them.

At the end, our final output is an average of the x_t produced in each round, i.e. x^* = \frac{1}{T}\sum_t x_t. This vector satisfies all the constraints to a roughly equal degree. We will skip the proof that this vector does what we want, but see these notes for a simple proof. We’ll spend the rest of this post implementing the scheme outlined above.

Implementing the oracle

Fix the convex region R = \{ c \cdot x = Z, x \geq 0 \} for a known optimal value Z. Define \textup{oracle}(\alpha, \beta) as the problem of finding an x \in R such that \alpha \cdot x \geq \beta.

For the case of this linear region R, we can simply find the index i which maximizes \alpha_i Z / c_i. If this value exceeds \beta, we can return the vector with that value in the i-th position and zeros elsewhere. Otherwise, the problem has no solution.

To prove the “no solution” part, say n=2 and you have x = (x_1, x_2) a solution to \alpha \cdot x \geq \beta. Then for whichever index makes \alpha_i Z / c_i bigger, say i=1, you can increase \alpha \cdot x without changing c \cdot x = Z by replacing x_1 with x_1 + (c_2/c_1)x_2 and x_2 with zero. I.e., we’re moving the solution x along the line c \cdot x = Z until it reaches a vertex of the region bounded by c \cdot x = Z and x \geq 0. This must happen when all entries but one are zero. This is the same reason why optimal solutions of (generic) linear programs occur at vertices of their feasible regions.

The code for this becomes quite simple. Note we use the numpy library in the entire codebase to make linear algebra operations fast and simple to read.

def makeOracle(c, optimalValue):
    n = len(c)

    def oracle(weightedVector, weightedThreshold):
        def quantity(i):
            return weightedVector[i] * optimalValue / c[i] if c[i] > 0 else -1

        biggest = max(range(n), key=quantity)
        if quantity(biggest) < weightedThreshold:
            raise InfeasibleException

        return numpy.array([optimalValue / c[i] if i == biggest else 0 for i in range(n)])

    return oracle

Implementing the core solver

The core solver implements the discussion from previously, given the optimal value of the linear program as input. To avoid too many single-letter variable names, we use linearObjective instead of c.

def solveGivenOptimalValue(A, b, linearObjective, optimalValue, learningRate=0.1):
    m, n = A.shape  # m equations, n variables
    oracle = makeOracle(linearObjective, optimalValue)

    def reward(i, specialVector):
        ...

    def observeOutcome(_, weights, __):
        ...

    numRounds = 1000
    weights, cumulativeReward, outcomes = MWUA(
        range(m), observeOutcome, reward, learningRate, numRounds
    )
    averageVector = sum(outcomes) / numRounds

    return averageVector

First we make the oracle, then the reward and outcome-producing functions, then we invoke the MWUA subroutine. Here are those two functions; they are closures because they need access to A and b. Note that neither c nor the optimal value show up here.

    def reward(i, specialVector):
        constraint = A[i]
        threshold = b[i]
        return threshold - numpy.dot(constraint, specialVector)

    def observeOutcome(_, weights, __):
        weights = numpy.array(weights)
        weightedVector = A.transpose().dot(weights)
        weightedThreshold = weights.dot(b)
        return oracle(weightedVector, weightedThreshold)

Implementing the binary search, and an example

Finally, the top-level routine. Note that the binary search for the optimal value is sophisticated (though it could be more sophisticated). It takes a max range for the search, and invokes the optimization subroutine, moving the upper bound down if the linear program is feasible and moving the lower bound up otherwise.

def solve(A, b, linearObjective, maxRange=1000):
    optRange = [0, maxRange]

    while optRange[1] - optRange[0] > 1e-8:
        proposedOpt = sum(optRange) / 2
        print("Attempting to solve with proposedOpt=%G" % proposedOpt)

        # Because the binary search starts so high, it results in extreme
        # reward values that must be tempered by a slow learning rate. Exercise
        # to the reader: determine absolute bounds for the rewards, and set
        # this learning rate in a more principled fashion.
        learningRate = 1 / max(2 * proposedOpt * c for c in linearObjective)
        learningRate = min(learningRate, 0.1)

        try:
            result = solveGivenOptimalValue(A, b, linearObjective, proposedOpt, learningRate)
            optRange[1] = proposedOpt
        except InfeasibleException:
            optRange[0] = proposedOpt

    return result

Finally, a simple example:

A = numpy.array([[1, 2, 3], [0, 4, 2]])
b = numpy.array([5, 6])
c = numpy.array([1, 2, 1])

x = solve(A, b, c)
print(x)
print(c.dot(x))
print(A.dot(x) - b)

The output:

Attempting to solve with proposedOpt=500
Attempting to solve with proposedOpt=250
Attempting to solve with proposedOpt=125
Attempting to solve with proposedOpt=62.5
Attempting to solve with proposedOpt=31.25
Attempting to solve with proposedOpt=15.625
Attempting to solve with proposedOpt=7.8125
Attempting to solve with proposedOpt=3.90625
Attempting to solve with proposedOpt=1.95312
Attempting to solve with proposedOpt=2.92969
Attempting to solve with proposedOpt=3.41797
Attempting to solve with proposedOpt=3.17383
Attempting to solve with proposedOpt=3.05176
Attempting to solve with proposedOpt=2.99072
Attempting to solve with proposedOpt=3.02124
Attempting to solve with proposedOpt=3.00598
Attempting to solve with proposedOpt=2.99835
Attempting to solve with proposedOpt=3.00217
Attempting to solve with proposedOpt=3.00026
Attempting to solve with proposedOpt=2.99931
Attempting to solve with proposedOpt=2.99978
Attempting to solve with proposedOpt=3.00002
Attempting to solve with proposedOpt=2.9999
Attempting to solve with proposedOpt=2.99996
Attempting to solve with proposedOpt=2.99999
Attempting to solve with proposedOpt=3.00001
Attempting to solve with proposedOpt=3
Attempting to solve with proposedOpt=3  # note %G rounds the printed values
Attempting to solve with proposedOpt=3
Attempting to solve with proposedOpt=3
Attempting to solve with proposedOpt=3
Attempting to solve with proposedOpt=3
Attempting to solve with proposedOpt=3
Attempting to solve with proposedOpt=3
Attempting to solve with proposedOpt=3
Attempting to solve with proposedOpt=3
Attempting to solve with proposedOpt=3
[ 0.     0.987  1.026]
3.00000000425
[  5.20000072e-02   8.49831849e-09]

So there we have it. A fiendishly clever use of multiplicative weights for solving linear programs.

Discussion

One of the nice aspects of MWUA is it’s completely transparent. If you want to know why a decision was made, you can simply look at the weights and look at the history of rewards of the objects. There’s also a clear interpretation of what is being optimized, as the potential function used in the proof is a measure of both quality and adaptability to change. The latter is why MWUA succeeds even in adversarial settings, and why it makes sense to think about MWUA in the context of evolutionary biology.

This even makes one imagine new problems that traditional algorithms cannot solve, but which MWUA handles with grace. For example, imagine trying to solve an “online” linear program in which over time a constraint can change. MWUA can adapt to maintain its approximate solution.

The linear programming technique is known in the literature as the Plotkin-Shmoys-Tardos framework for covering and packing problems. The same ideas extend to other convex optimization problems, including semidefinite programming.

If you’ve been reading this entire post screaming “This is just gradient descent!” Then you’re right and wrong. It bears a striking resemblance to gradient descent (see this document for details about how special cases of MWUA are gradient descent by another name), but the adaptivity for the rewards makes MWUA different.

Even though so many people have been advocating for MWUA over the past decade, it’s surprising that it doesn’t show up in the general math/CS discourse on the internet or even in many algorithms courses. The Arora survey I referenced is from 2005 and the linear programming technique I demoed is originally from 1991! I took algorithms classes wherever I could, starting undergraduate in 2007, and I didn’t even hear a whisper of this technique until midway through my PhD in theoretical CS (I did, however, study fictitious play in a game theory class). I don’t have an explanation for why this is the case, except maybe that it takes more than 20 years for techniques to make it to the classroom. At the very least, this is one good reason to go to graduate school. You learn the things (and where to look for the things) which haven’t made it to classrooms yet.

Until next time!

A Rook Game

Problem: Two players take turns moving a rook on an 8×8 chessboard. The rook is only allowed to move south or west (but not both in a single turn), and may move any number of squares in the chosen direction on a turn. The loser is the player who first cannot move the rook. What is the optimal play for any starting position?

rook-board

Solution: Take advantage of the symmetry of the board. If the rook is not on the diagonal, the optimal strategy is to move it to the diagonal. Then when the other player moves it off, your next move is to move it back to the diagonal. If your opponent starts their turn with the rook always on the diagonal, then you will never lose, and by the symmetry of the board you can always move the rook back to the diagonal. This provides an optimal algorithm for either player. In particular, if the rook starts on a square that is not on the diagonal, then player 1 can guarantee a win, and otherwise player 2 can.

Symmetry is one of the most powerful tools in all of mathematics, and this is a simple albeit illustrative example of its usage.

Want to make a great puzzle game? Get inspired by theoretical computer science.

Two years ago, Erik Demaine and three other researchers published a fun paper to the arXiv proving that most incarnations of classic nintendo games are NP-hard. This includes almost every Super Mario Brothers, Donkey Kong, and Pokemon title. Back then I wrote a blog post summarizing the technical aspects of their work, and even gave a talk on it to a room full of curious undergraduate math majors.

But while bad tech-writers tend to interpret NP-hard as “really really hard,” the truth is more complicated. It’s really a statement about computational complexity, which has a precise mathematical formulation. Sparing the reader any technical details, here’s what NP-hard implies for practical purposes:

You should abandon hope of designing an algorithm that can solve any instance of your NP-hard problem, but many NP-hard problems have efficient practical “good-enough” solutions.

The very definition of NP-hard means that NP-hard problems need only be hard in the worst case. For illustration, the fact that Pokemon is NP-hard boils down to whether you can navigate a vastly complicated maze of trainers, some of whom are guaranteed to defeat you. It has little to do with the difficulty of the game Pokemon itself, and everything to do with whether you can stretch some subset of the game’s rules to create a really bad worst-case scenario.

So NP-hardness has very little to do with human playability, and it turns out that in practice there are plenty of good algorithms for winning at Super Mario Brothers. They work really well at beating levels designed for humans to play, but we are highly confident that they would fail to win in the worst-case levels we can cook up. Why don’t we know it for a fact? Well that’s the P \ne NP conjecture.

Since Demaine’s paper (and for a while before it) a lot of popular games have been inspected under the computational complexity lens. Recently, Candy Crush Saga was proven to be NP-hard, but the list doesn’t stop with bad mobile apps. This paper of Viglietta shows that Pac-man, Tron, Doom, Starcraft, and many other famous games all contain NP-hard rule-sets. Games like Tetris are even known to have strong hardness-of-approximation bounds. Many board games have also been studied under this lens, when you generalize them to an n \times n sized board. Chess and checkers are both what’s called EXP-complete. A simplified version of Go fits into a category called PSPACE-complete, but with the general ruleset it’s believed to be EXP-complete [1]. Here’s a list of some more classic games and their complexity status.

So we have this weird contrast: lots of NP-hard (and worse!) games have efficient algorithms that play them very well (checkers is “solved,” for example), but in the worst case we believe there is no efficient algorithm that will play these games perfectly. We could ask, “We can still write algorithms to play these games well, so what’s the point of studying their computational complexity?”

I agree with the implication behind the question: it really is just pointless fun. The mathematics involved is the very kind of nuanced manipulations that hackers enjoy: using the rules of a game to craft bizarre gadgets which, if the player is to surpass them, they must implicitly solve some mathematical problem which is already known to be hard.

But we could also turn the question right back around. Since all of these great games have really hard computational hardness properties, could we use theoretical computer science, and to a broader extent mathematics, to design great games? I claim the answer is yes.

[1] EXP is the class of problems solvable in exponential time (where the exponent is the size of the problem instance, say n for a game played on an n \times n board), so we’re saying that a perfect Chess or Checkers solver could be used to solve any problem that can be solved in exponential time. PSPACE is strictly smaller (we think; this is open): it’s the class of all problems solvable if you are allowed as much time as you want, but only a polynomial amount of space to write down your computations. 

A Case Study: Greedy Spiders

Greedy spiders is a game designed by the game design company Blyts. In it, you’re tasked with protecting a set of helplessly trapped flies from the jaws of a hungry spider.

A screenshot from Greedy Spiders.

A screenshot from Greedy Spiders. Click to enlarge.

In the game the spider always moves in discrete amounts (between the intersections of the strands of spiderweb) toward the closest fly. The main tool you have at your disposal is the ability to destroy a strand of the web, thus prohibiting the spider from using it. The game proceeds in rounds: you cut one strand, the spider picks a move, you cut another, the spider moves, and so on until the flies are no longer reachable or the spider devours a victim.

Aside from being totally fun, this game is obviously mathematical. For the reader who is familiar with graph theory, there’s a nice formalization of this problem.

The Greedy Spiders Problem: You are given a graph G_0 = (V, E_0) and two sets S_0, F \subset V denoting the locations of the spiders and flies, respectively. There is a fixed algorithm A that the spiders use to move. An instance of the game proceeds in rounds, and at the beginning of each round we call the current graph G_i = (V, E_i) and the current location of the spiders S_i. Each round has two steps:

  1. You pick an edge e \in E_i to delete, forming the new graph G_{i+1} = (V, E_i).
  2. The spiders jointly compute their next move according to A, and each spider moves to an adjacent vertex. Thus S_i becomes S_{i+1}.

Your task is to decide whether there is a sequence of edge deletions which keeps S_t and F disjoint for all t \geq 0. In other words, we want to find a sequence of edge deletions that disconnects the part of the graph containing the spiders from the part of the graph containing the flies.

This is a slightly generalized version of Greedy Spiders proper, but there are some interesting things to note. Perhaps the most obvious question is about the algorithm A. Depending on your tastes you could make it adversarial, devising the smartest possible move at every step of the way. This is just as hard as asking if there is any algorithm that the spiders can use to win. To make it easier, A could be an algorithm represented by a small circuit to which the player has access, or, as it truly is in the Greedy Spiders game, it could be the greedy algorithm (and the player can exploit this).

Though I haven’t heard of the Greedy Spiders problem in the literature by any other name, it seems quite likely that it would arise naturally. One can imagine the spiders as enemies traversing a network (a city, or a virus in a computer network), and your job is to hinder their movement toward high-value targets. Perhaps people in the defense industry could use a reasonable approximation algorithm for this problem. I have little doubt that this game is NP-hard [2], but the purpose of this article is not to prove new complexity results. The point is that this natural theoretical problem is a really fun game to play! And the game designer’s job is to do what game designers love to do: add features and design levels that are fun to play.

Indeed the Greedy Spiders folks did just that: their game features some 70-odd levels, many with multiple spiders and additional tools for the player. Some examples of new tools are: the ability to delete a vertex of the graph and the ability to place a ‘decoy-fly’ which is (to the greedy-algorithm-following spiders) indistinguishable from a real fly. They player is usually given only one or two uses of these tools per level, but one can imagine that the puzzles become a lot richer.

[2]: In the adversarial case it smells like it’s PSPACE-complete, being very close to known PSPACE-hard problems like Cops and Robbers and Generalized Geography

Examples

I can point to a number of interesting problems that I can imagine turning into successful games, and I will in a moment, but before I want to make it clear that I don’t propose game developers study theoretical computer science just to turn our problems into games verbatim. No, I imagine that the wealth of problems in computer science can serve as inspiration, as a spring board into a world of interesting gameplay mechanics and puzzles. The bonus for game designers is that adding features usually makes problems harder and more interesting, and you don’t need to know anything about proofs or the details of the reductions to understand the problems themselves (you just need familiarity with the basic objects of consideration, sets, graphs, etc).

For a tangential motivation, I imagine that students would be much more willing to do math problems if they were based on ideas coming from really fun games. Indeed, people have even turned the stunningly boring chore of drawing an accurate graph of a function into a game that kids seem to enjoy. I could further imagine a game that teaches programming by first having a student play a game (based on a hard computational problem) and then write simple programs that seek to do well. Continuing with the spiders example they could play as the defender, and then switch to the role of the spider by writing the algorithm the spiders follow.

But enough rambling! Here is a short list of theoretical computer science problems for which I see game potential. None of them have, to my knowledge, been turned into games, but the common features among them all are the huge potential for creative extensions and interesting level design.

Graph Coloring

Graph coloring is one of the oldest NP-complete problems known. Given a graph G and a set of colors \{ 1, 2, \dots, k \}, one seeks to choose colors for the vertices of G so that no edge connects two vertices of the same color.

coloring

Now coloring a given graph would be a lame game, so let’s spice it up. Instead of one player trying to color a graph, have two players. They’re given a k-colorable graph (say, k is 3), and they take turns coloring the vertices. The first player’s goal is to arrive at a correct coloring, while the second player tries to force the first player to violate the coloring condition (that no adjacent vertices are the same color). No player is allowed to break the coloring if they have an option. Now change the colors to jewels or vegetables or something, and you have yourself an award-winning game! (Or maybe: Epic Cartographer Battles of History)

An additional modification: give the two players a graph that can’t be colored with k colors, and the first player to color a monochromatic edge is the loser. Add additional move types (contracting edges or deleting vertices, etc) to taste.

Art Gallery Problem

Given a layout of a museum, the art gallery problem is the problem of choosing the minimal number of cameras so as to cover the whole museum.

artgallery

This is a classic problem in computational geometry, and is well-known to be NP-hard. In some variants (like the one pictured above) the cameras are restricted to being placed at corners. Again, this is the kind of game that would be fun with multiple players. Rather than have perfect 360-degree cameras, you could have an angular slice of vision per camera. Then one player chooses where to place the cameras (getting exponentially more points for using fewer cameras), and the opponent must traverse from one part of the museum to the other avoiding the cameras. Make the thief a chubby pig stealing eggs from birds and you have yourself a franchise.

For more spice, allow the thief some special tactics like breaking through walls and the ability to disable a single camera.

This idea has of course been the basis of many single-player stealth games (where the guards/cameras are fixed by the level designer), but I haven’t seen it done as a multiplayer game. This also brings to mind variants like the recent Nothing to Hide, which counterintuitively pits you as both the camera placer and the hero: you have to place cameras in such a way that you’re always in vision as you move about to solve puzzles. Needless to say, this fruit still has plenty of juice for the squeezing.

Pancake Sorting

Pancake sorting is the problem of sorting a list of integers into ascending order by using only the operation of a “pancake flip.”

panackesortJust like it sounds, a pancake flip involves choosing an index in the list and flipping the prefix of the list (or suffix, depending on your orientation) like a spatula flips a stack of pancakes. Now I think sorting integers is boring (and it’s not NP-hard!), but when you forget about numbers and that one special configuration (ascending sorted order), things get more interesting. Instead, have the pancakes be letters and have the goal be to use pancake flips to arrive at a real English word. That is, you don’t know the goal word ahead of time, so it’s the anagram problem plus finding an efficient pancake flip to get there. Have a player’s score be based on the number of flips before a word is found, and make it timed to add extra pressure, and you have yourself a classic!

The level design then becomes finding good word scrambles with multiple reasonable paths one could follow to get valid words. My mother would probably play this game!

Bin Packing

Young Mikio is making sushi for his family! He’s got a table full of ingredients of various sizes, but there is a limit to how much he can fit into each roll. His family members have different tastes, and so his goal is to make everyone as happy as possible with his culinary skills and the options available to him.

Another name for this problem is bin packing. There are a collection of indivisible objects of various sizes and values, and a set of bins to pack them in. Your goal is to find the packing that doesn’t exceed the maximum in any bin and maximizes the total value of the packed goods.

binpacking

I thought of sushi because I recently played a ridiculously cute game about sushi (thanks to my awesome friend Yen over at Baking And Math), but I can imagine other themes that suggest natural modifications of the problem. The objects being packed could be two-dimensional, there could be bonuses for satisfying certain family members (or penalties for not doing so!), or there could be a super knife that is able to divide one object in half.

I could continue this list for quite a while, but perhaps I should keep my best ideas to myself in case any game companies want to hire me as a consultant. 🙂

Do you know of games that are based on any of these ideas? Do you have ideas for features or variations of the game ideas listed above? Do you have other ideas for how to turn computational problems into games? I’d love to hear about it in the comments.

Until next time!

Bandits and Stocks

So far in this series we’ve seen two nontrivial algorithms for bandit learning in two different settings. The first was the UCB1 algorithm, which operated under the assumption that the rewards for the trials were independent and stochastic. That is, each slot machine was essentially a biased coin flip, and the algorithm was trying to find the machine with the best odds. The second was the Exp3 algorithm, which held the belief that the payoffs were arbitrary. In particular this includes the possibility that an adversary is setting the payoffs against you, and so we measured the success of an algorithm in terms of how it fares against the best single action (just as we did with UCB1, but with Exp3 it’s a nontrivial decision).

Before we move on to other bandit settings it’s natural to try to experiment with the ones we have on real world data. On one hand it’s interesting to see how they fare outside academia. And more relevantly to the design of the future bandit algorithms we’ll see on this blog, we need to know what worldly problems actually provide in terms of inputs to our learning algorithm in each round.

But another interesting issue goes like this. In the real world we can’t ever really know whether the rewards of the actions are stochastic or adversarial. Many people believe that adversarial settings are far too pathological to be realistic, while others claim that the assumptions made by stochastic models are too strict. To weigh in on this dispute, we’ll dip into a bit of experimental science and see which of the two algorithms performs better on the problem of stock trading. The result is then evidence that stocks behave stochastically or adversarially. But we don’t want to stir up too many flames, so we can always back up behind the veil of applied mathematics (“this model is too simple anyway”).

Indeed the model we use in this post is rather simplistic. I don’t know as much as I should (or as my father would have me know) about stock markets. In fact, I’m more partial to not trade stocks on principle. But I must admit that average-quality stock data is easy to come by, and the basic notions of market interactions lend themselves naturally to many machine learning problems. If the reader has any ideas about how to strengthen the model, I welcome suggestions in the comments (or a fork on github).

A fair warning to the reader, we do not solve the problem of trading stocks by any means. We use a model that’s almost entirely unrealistic, and the results aren’t even that good. I’m quite nervous to publish this at all, just because above all else it reveals my gaping ignorance on how stock markets work. But this author believes in revealing ignorance as learning, if for nothing else than that it provides extremely valuable insight into the nature of a problem and an appreciation of its complexity. So criticize away, dear readers.

As usual, all of the code and data we use in this post is available on this blog’s Github page. Our language of choice for this post is Python.

This little trader got lucky.

This little trader got lucky. Could it be because he’s got TEN MONITORS?!

Stocks for Dummies (me)

A quick primer on stocks, which is only as detailed as it needs to be for this post: a stock is essentially the sum of the value of all the assets of a company. A publicly traded company divides their stock into a number of “shares,” and owning a share represents partial ownership of the company. If you own 50% of the shares, you own 50% of the company. Companies sell shares or give them to employees as benefits (or options), and use the money gained through their sale for whatever they see fit. The increase in the price of a stock generally signifies the company is successful and growing; for example, stocks generally rise when a hotly anticipated product is announced.

The stock of a company is traded through one of a number of markets called stock exchanges. The buying and selling interactions are recorded and public, and there are many people in the world who monitor the interactions as they happen (via television, or programmatically) in the hopes of noticing opportunities before others and capitalizing on them. Each interaction induces a change on the price of a share of stock: whenever a share is bought at a certain price, that is the established and recorded price of a share (up to some fudging by brokers which is entirely mysterious to me). In any case, the prices go up and down, and they’re often bundled into “bars” which summarize the data over a certain period of time. The bars we use in this post are daily, and consist of four numbers: the open, the price at the beginning of the day, the high and low, which are self-explanatory, and the close, which is the price at the end of the day.

Bandits and Daily Stock Trading

Now let’s simplify things as much as possible. Our bandit learning algorithm will interact with the market as follows: each day it chooses whether or not to buy a single dollar’s worth of a stock, and at the end of the day it sells the stock and observes the profit. There are no brokers involved, and the price the algorithm sees is the price it gets. In bandit language: the stocks represent actions, and the amount of profit at the end of a day constitutes the payoff of an action in one round. Since small-scale stock price movement is generally very poorly understood, it makes some level of sense to assume the price movements within a given day are adversarial. On the other hand, since we understand them so poorly, we might be tempted to just call them “random” fluctuations, i.e. stochastic. So this is a nice little testbed for seeing which assumption yields a more successful algorithm.

Unlike the traditional image of stock trading where an individual owns shares of a stock over a long period of time, our program will operate on a daily time scale, and hence cannot experience the typical kinds of growth. Nevertheless, we can try to make some money over time, and if it’s a good strategy, we could scale up the single dollar to whatever we’re willing to risk. Specifically, the code we used to compute the payoff is

def payoff(stockTable, t, stock, amountToInvest=1.0):
   openPrice, closePrice = stockTable[stock][t]

   sharesBought = amountToInvest / openPrice
   amountAfterSale = sharesBought * closePrice

   return amountAfterSale - amountToInvest

The remainder of the code is interfacing with the Exp3 and UCB1 functions we gave in previous posts, and data shuffling. We got our data from Google Finance, and we provide it, along with all of the code used in the making of this post, on this blog’s Github page. Before we run our experiments, let’s give a few reasons why this model is unrealistic.

  1. We assume we can buy/sell fractional shares of a stock, which to my knowledge is not possible. Though this experiment could be redone where you buy a single share of a stock, or with mutual funds/currency exchange/whatever replacing stocks, we didn’t do it this way.
  2. Brokerage fees can drastically change the success of an algorithm which trades frequently.
  3. Open and close prices are not typical prices. People will often make decisions based on the time of day, but then again we might expect this to be just another reason that Exp3 would perform better than UCB1.
  4. We’re not actually trading in the stock market, and so we’re ignoring the effects of our own algorithm on the prices in the market.
  5. It’s impossible to guarantee you get to use the opening price and closing price in your transactions.
  6. UCB1 and Exp3 don’t use all of the information available. Indeed, they assume that they would not be able to see the outcome of an action they did not take, but with stocks you can get a good estimate of how much money you would have made had you chosen a different stock.
  7. Each trial in a bandit learning problem is identical from the learner’s perspective, but one often keeps a stock around while making other decisions.

We’ll come back to #6 after seeing the raw experiments for an unaltered UCB1 and Exp3, because there is a natural extension of the algorithm to handle additional information. I’m sure there are other glaring issues with the experimental setup, and the reader should feel free to rant about it in the comments. It won’t stop me from running the algorithm and seeing what happens just for fun.

Data Sets

We ran the experiment on two sets of stocks. The first set consisted of nine random stocks, taken from the random stocks twitter feed, with 5 years of past data. The stocks are:

lxrx, keg, cuba, tdi, brks, mux, cadx, belfb, htr

And you can view more information about these particular stocks via Google Finance. The second set was a non-random choice of nine Fortune 500 companies with 10 years of past data. The stocks were

amzn, cost, jpm, gs, wfc, msft, tgt, aapl, wmt

And again more information about these stocks is available via Google Finance. For the record, here were the cumulative payoffs of each of the nine Fortune 500 companies:

f500-cumulative-rewards

The cumulative rewards for the nine Fortune 500 companies over the last ten years of data.

Interestingly, the company which started off with the best prospects (Apple), turned out to have the worst cumulative reward by the end. The long-term winners in our little imaginary world happen to be Amazon, Costco, and Goldman Sachs. Perhaps this gives credence to the assumption that payoffs are adversarial. A learner can easily get tricked into putting too much faith in one action early on.

And for the random stocks:

The cumulative payoff for the nine randomly chosen stocks.

The cumulative payoff for the nine randomly chosen stocks for the last five years of data.

The random stocks clearly perform worse and more variably overall (although HTR surpasses most of the Fortune 500 companies, despite its otherwise relatively modest stock growth over the last five years). To my untrained eyes these movements look more like a stochastic model than an adversarial one.

Experiments

Here is a typical example of a run of Exp3 on the Fortune 500 data set (using \gamma = 0.33, recall \gamma measures the amount of uniform exploration performed):

(Expected payoff, variance) over 1000 trials is (1.122463919564572, 0.5518037498918705)
For a single run: 
Payoff was 1.12
Regret was 2.91
Best stock was amzn at 4.02
weights: '0.00, 0.00, 0.00, 0.46, 0.52, 0.00, 0.00, 0.00, 0.01'

And one for UCB1:

(Expected payoff, variance) over 1000 trials is (1.1529891576139333, 0.5012825847001482)
For a single run: 
Payoff was 1.73
Regret was 2.29
Best stock was amzn at 4.02
ucbs: '0.234, 0.234, 0.234, 0.234, 0.234, 0.234, 0.234, 0.234, 0.234'

The results are quite curious. Indeed, the expected payoff seems to be a whopping 110% return! The variance of these results is quite high, and so it’s not at all impossible that the algorithm could have a negative return. But just as often it would return around 200% profit. 

Before we go risking all our money on this strategy, let’s take a closer look at what’s happening in the algorithm. It appears that for UCB1 the upper confidence bounds assigned to each action are the same! In other words, even after ten years of trials, no single stock “shined” above the others in the eyes of UCB1. It may seem that Exp3 has a leg up on UCB1 in this respect, because it’s clear that it gives higher weights to some stocks over others. However, running the algorithm multiple times shows drastically different weight distributions, and if we average the resulting weights over a thousand rounds, we see that they all have roughly the same mean and variance (the mean being first in the pair):

weight stats for msft: (0.107, 0.025)
weight stats for jpm: (0.109, 0.027)
weight stats for tgt: (0.110, 0.029)
weight stats for gs: (0.112, 0.025)
weight stats for wmt: (0.110, 0.027)
weight stats for aapl: (0.111, 0.027)
weight stats for amzn: (0.120, 0.029)
weight stats for cost: (0.113, 0.026)
weight stats for wfc: (0.107, 0.023)
Indeed, the best stock, Amazon, had an average weight just barely larger (and more variable) than any of the other stocks. So this evidence points to the conclusion that neither EXP3 nor UCB1 has any clue which stock is better. Pairing this with the fact that both algorithms nevertheless perform well would suggest that a random choice of action at each step is equally likely to do well. Indeed, when we run with a “random bandit” that just chooses actions uniformly at random, we get the following results:
(Expected payoff, variance) over 1000 trials is (1.1094227056931132, 0.4403783017367529)
For a single run: 
Payoff was 3.13
Regret was 0.90
Best stock was amzn at 4.02

It’s not quite as good as either Exp3 or UCB1, but it’s close and less variable, which means a lot to an investor. In other words, it’s starting to look like Exp3 and UCB1 aren’t doing significantly better than random at all, and that a monkey would do well in this system (for these particular stocks).

Of course, Fortune 500 companies are pretty successful by definition, so let’s turn our attention to the random stocks:

For the random bandit learner:

(Expected payoff, variance) over 1000 trials is (-0.23952295977625776, 1.0787311145181104)
For a single run: 
Payoff was -2.01
Regret was 3.92
Best stock was htr at 1.91

For UCB1:

(Expected payoff, variance) over 1000 trials is (-0.3503593899029112, 1.1136234992964154)
For a single run: 
Payoff was 0.26
Regret was 1.65
Best stock was htr at 1.91
ucbs: '0.315, 0.315, 0.315, 0.316, 0.315, 0.315, 0.315, 0.315, 0.316'

And for Exp3:

(Expected payoff, variance) over 1000 trials is (-0.25827976810345593, 1.2946101887058519)
For a single run: 
Payoff was -0.34
Regret was 2.25
Best stock was htr at 1.91
weights: '0.08, 0.00, 0.14, 0.06, 0.48, 0.00, 0.00, 0.04, 0.19'

But again Exp3 has no idea what stocks are actually best, with the average, variance over 1000 trials being:

weight stats for lxrx: '0.11, 0.02'
weight stats for keg: '0.11, 0.02'
weight stats for htr: '0.12, 0.02'
weight stats for cadx: '0.10, 0.02'
weight stats for belfb: '0.11, 0.02'
weight stats for tdi: '0.11, 0.02'
weight stats for cuba: '0.11, 0.02'
weight stats for mux: '0.11, 0.02'
weight stats for brks: '0.11, 0.02'

The long and short of it is that the choice of Fortune 500 stocks was inherently so biased toward success than a monkey could have made money investing in them, while the average choice of stocks had, if anything, a bias toward loss. And unfortunately using an algorithm like UCB1 or Exp3 straight out of the box doesn’t produce anything better than a monkey.

Issues and Improvements

There are two glaring theoretical issues here that we haven’t yet addressed. One of these goes back to issue #5 in that list we gave at the beginning of the post: the bandit algorithms are assuming they have less information than they actually have! Indeed, at the end of a day of stock trading, you have a good idea what would have happened to you had you bought a different stock, and in our simplified world you can know exactly what your profit would have been. Recalling that UCB1 and Exp3 both maintained some numbers representing the strength of an action (Exp3 had a “weight” and UCB1 an upper confidence bound), the natural extension to both UCB1 and Exp3 is simply to modify the beliefs about all actions after any given round. This is a pretty simple improvement to make in our implementation, since it just changes a single weight update to a loop. For Exp3:

for choice in range(numActions):
   rewardForUpdate = reward(choice, t)
   scaledReward = (rewardForUpdate - rewardMin) / (rewardMax - rewardMin)
   estimatedReward = 1.0 * scaledReward / probabilityDistribution[choice]
   weights[choice] *= math.exp(estimatedReward * gamma / numActions)

With a similar loop for UCB1. This code should be familiar from our previous posts on bandits. We then rerun the new algorithms on the same data sets, and the results are somewhat surprising. First, UCB1 on Fortune 500:

(Expected payoff, variance) over 1000 trials is (3.530670654982728, 0.007713190816014095)
For a single run: 
Payoff was 3.56
Regret was 0.47

This is clearly outperforming the random bandit learning algorithm, with an average return of 350%! In fact, it does almost as well as the best stock, and the variance is quite low. UCB1 also outperforms Exp3, which fares comparably to its pre-improved self. That is, it’s still not much better than random:

(Expected payoff, variance) over 1000 trials is (1.1424797906901956, 0.434335471375294)
For a single run: 
Payoff was 1.24
Regret was 2.79

And also for the random stocks, UCB1 with improvements outperforms Exp3 and UCB1 without improvements. UCB1:

(Expected payoff, variance) over 1000 trials is (0.680211923900068, 0.04226672915962647)
For a single run:
Payoff was 0.82
Regret was 1.09

And Exp3:

(Expected payoff, variance) over 1000 trials is (-0.2242152508929378, 1.1312843329929194)
For a single run: 
Payoff was -0.16
Regret was 2.07

We might wonder why this is the case, and there is a plausible explanation. See, Exp3 has a difficult life: it has to assume that at any time the adversary can completely change the game. And so Exp3 must remain vigilant, continuing to try options it knows to be terrible for fear that they may spontaneously do well. Exp3 is the grandfather who, after 75 years of not winning the lotto, continues to buy tickets every week. A better analogy might be a lioness who, even after being moved to the zoo, stays up all night to protect a cub from predators. This gives us quite a new perspective on Exp3: the world really has to be that messed up for Exp3 to be useful. As we saw, UCB1 is much more eager to jump on a winning bandwagon, and it paid off in both the good (Fortune 500) and bad (random stock) scenarios. All in all, this experiment would provide some minor evidence that the stock market (or just this cheesy version of it) is more stochastic than adversarial.

The second problem is that we’re treating these stocks as if they were isolated from the rest of the world. Indeed, along with each stock comes some kind of context in the form of information about that stock. Historical prices, corporate announcements, cyclic boom and bust, what the talking heads think, all of this may be relevant to the price fluctuations of a stock on any given day. While Exp3 and UCB1 are ill-equipped to handle such a rich landscape, researchers in bandit learning have recognized the importance of context in decision making. So much so, in fact, that an entire subfield of “Contextual Bandits” was born. John Langford, perhaps the world’s leading expert on bandit learning, wrote on his blog in 2007,

I’m having difficulty finding interesting real-world k-Armed Bandit settings which aren’t better thought of as Contextual Bandits in practice. For myself, bandit algorithms are (at best) motivational because they can not be applied to real-world problems without altering them to take context into account.

I tend to agree with him. Bandit problems almost always come with some inherent additional structure in the real world, and the best algorithms will always take advantage of that structure. A “context” associated with each round is perhaps the weakest kind of structure, so it’s a natural place to look for better algorithms.

So that’s what we’ll do in the future of this series. But before then we might decide to come up with another experiment to run Exp3 and UCB1 on. It would be nice to see an instance in which Exp3 seriously outperforms UCB1, but maybe the real world is just stochastic and there’s nothing we can do about it.

Until next time!