  We study the role of contextual information in the online learning problem of
brokerage between traders. At each round, two traders arrive with secret
valuations about an asset they wish to trade. The broker suggests a trading
price based on contextual data about the asset. Then, the traders decide to buy
or sell depending on whether their valuations are higher or lower than the
brokerage price.
  We assume the market value of traded assets is an unknown linear function of
a $d$-dimensional vector representing the contextual information available to
the broker. Additionally, we model traders' valuations as independent bounded
zero-mean perturbations of the asset's market value, allowing for potentially
different unknown distributions across traders and time steps. Consistently
with the existing online learning literature, we evaluate the performance of a
learning algorithm with the regret with respect to the gain from trade. If the
noise distributions admit densities bounded by some constant $L$, then, for any
time horizon $T$:
  - If the agents' valuations are revealed after each interaction, we provide
an algorithm achieving $O ( L d \ln T )$ regret, and show a corresponding
matching lower bound of $\Omega( Ld \ln T )$.
  - If only their willingness to sell or buy at the proposed price is revealed
after each interaction, we provide an algorithm achieving $O(\sqrt{LdT \ln T
})$ regret, and show that this rate is optimal (up to logarithmic factors), via
a lower bound of $\Omega(\sqrt{LdT})$.
  To complete the picture, we show that if the bounded density assumption is
lifted, then the problem becomes unlearnable, even with full feedback.
