The Weighted Majority Algorithm is a randomized rule used to learn the best action amongst a fixed reference set.
We consider a model of a large number of single server queues. When a job arrives, we assume it chooses between queues. The job then chooses to join the shortest of these queues. We show that such choice can dramatically reduce queue sizes.
Here is the long run queue length; is the expected waiting time; is the arrival rate at the queue.
- The Hamilton-Jacobi-Bellman Equation.
- Heuristic derivation of the HJB equation.
- Continuous-time dynamic programs
- The HJB equation; a heuristic derivation; and proof of optimality.
- Markov Decisions Problems; Bellman’s Equation; Two examples
- Dynamic Programs; Bellman’s Equation; An example.