This post is going to mostly be propaganda for Thompson sampling. However, the presentation is quite different from the standard presentation. I will be working within a toy model, but I think some of the lessons will generalize. I end with some discussion of fairness and exploitation.

A Exploration/Exploitation Toy Model

Imagine you are interacting with the world over time. We are going to make a couple substantial assumptions. Firstly, we assume that you know what you are trying to optimize. Secondly, we assume that you get high quality feedback on the thing you are trying to optimize. In the spirit of the online learning community, we will be referring to your goal as "reward" rather than "utility."

On day $t$ , you choose an action, $a_{t} \in A$ , and then the environment responds with an observation $e_{t} \in E$ . Both you and the environment may respond randomly, and may react to the entire history of what has happened. (If you want the environment to act first, you could just make $a_{0}$ not matter.) We assume we have some fixed bounded reward function $r : E \to R$ , that you know. (If you want reward to be more of a function of the history, you can just include more history information in $e_{t}$ .)

We are going to be imagining agents that are myopically choosing $a_{t}$ , so as to maximize $r (e_{t})$ . The choice to do this, rather than e.g. maximizing the total reward of the next $m$ time steps, is mostly for simplicity. However, the choice not to have preferences that are over the entire future is basically the assumption that you get high quality feedback on what we are trying to optimize, which is a substantial philosophical assumption.

So, the environment can be thought of as a function, that takes in a history, $(a_{0} e_{0}) (a_{1} e_{1}) \dots (a_{t - 1} e_{t - 1}) a_{t}$ , and returns a probability distribution on $e_{t}$ which we then sample from. If the agent knew what the environment was, the agent would just choose the $a_{t}$ each round which maximizes the the expectation of $r (e_{t})$ . However, we want to model an agent that is uncertain about what environment it is interacting with, and learning over time.

Let us say that the agent has some probability distribution over possible environments. The set $H$ (for hypotheses) of possible environments is the set of functions that take in a string of the form $(a_{0} e_{0}) (a_{1} e_{1}) \dots (a_{t - 1} e_{t - 1}) a_{t}$ , and output a distri...