is closest to that which would result from each potential routing decision. Then the learner assigns the WLR associated with that training data pair as the estimate for what WLR
would result from said routing decision. These WLR values are then used to choose among those potential routing decisions. The input-output data generated under this algorithm is adding to the training set as it is generated.

In this routing algorithm, the routers only estimate how their routing decisions (as reflected in their loads at individual time steps) will affect their WLR values (based on many agents' loads). It is also possible to calculate exactly how the routing decisions affect the routers' WLR's if, unlike the MB COIN, we had full knowledge of the loads of all agents in the system. In a way similar to ISPA, for each router we can evaluate the exact WLR value that would ensue from each of its candidate actions, under the assumption that windowed loads on all other routers are the same one wave into the future as they are now.  We call this algorithm for directly maximizing WLR (an algorithm we call the full knowledge COIN, or FK COIN).

Note that under the assumption behind the FK COIN, the action η chooses in wave κ ( τ )
that maximizes WLR will also maximize the world reward. In other words, WL reward is perfectly factored with respect to (wave-indexed) world reward, even though the associated utilities are not related that way (due to inaccuracy in our estimate of the effect set). Due to this factoredness, the FK COIN is equivalent to load balancing on world rewards. Since LB in general results in inferior performance compared to LB over time, and since the FK COIN is equivalent to LB, one might expect that its performance is suboptimal. Intuitively, this suboptimality reflects the fact that one should not choose the action only with regard to its effect on current reward, but also with concern for the reward of future waves. In the language of the COIN framework, this suboptimality can be viewed as a restatement of the fact that for our inexactly estimated effect set, the system will not be perfectly factored.

The learning algorithm of the MB COIN as described is extraordinarily crude. In addition, the associated scheme for choosing an action is purely exploitative, with no exploration whatsoever. Rather than choose some particular more sophisticated scheme and tune it to fit our simulations, we emulated using more sophisticated algorithms in general. We did this by modifying the MB COIN algorithm to occasionally have the FK COIN determine a router's action rather than the purely greedy learner outlined above. The steering parameter discussed in Section 5.5 determines how often the routing decision is based on the MB COIN as opposed to the FK COIN.

## 5. Simulation Results

In practice, it is very difficult to implement either FK COIN or LB. In this section we use experiments to investigate behavior of algorithms that can conceivably be used in practice. More precisely, based on the model and routing algorithms discussed above, we have performed simulations to compare the performance of ISPA and MB COIN across a variety of nnetworks, varying in size from five to eighteen routers. In all cases traffic was inserted into the network in a regular, non-stochastic manner at the sources. The results we report are averaged over 20 runs. We do not report error bars as they are all lower than 0.05.

In Sections 5.1 - 5.4 we analyze traffic patterns over four networks where ISPA suffers from the Braess' paradox. In contrast, the MB COIN almost never falls prey to the paradox