  Companies like Google and Microsoft run billions of auctions every day to
sell advertising opportunities. Any change to the rules of these auctions can
have a tremendous effect on the revenue of the company and the welfare of the
advertisers and the users. Therefore, any change requires careful evaluation of
its potential impacts. Currently, such impacts are often evaluated by running
simulations or small controlled experiments. This, however, misses the
important factor that the advertisers respond to changes. Our goal is to build
a theoretical framework for predicting the actions of an agent (the advertiser)
that is optimizing her actions in an uncertain environment. We model this
problem using a variant of the multi-armed bandit setting where playing an arm
is costly. The cost of each arm changes over time and is publicly observable.
The value of playing an arm is drawn stochastically from a static distribution
and is observed by the agent and not by us. We, however, observe the actions of
the agent. Our main result is that assuming the agent is playing a strategy
with a regret of at most $f(T)$ within the first $T$ rounds, we can learn to
play the multi-armed bandits game (without observing the rewards) in such a way
that the regret of our selected actions is at most $O(k^4(f(T)+1)\log(T))$,
where $k$ is the number of arms.
