Applied Probability Notes – Page 13

Max-Weight Scheduling

We define a discrete-time queueing network where there are restrictions on which queues can be served simultaneously. We give a policy for serving queues which is stable whenever it is possible to stabilize the queueing network.

Continue reading “Max-Weight Scheduling”

Blackwell Approachability

Sequentially a player decides to play $\{p_t\}_{t=1}^\infty$ and his adversary decides $\{q_t\}_{t=1}^\infty$ . At time $t$ , a decision $(p_t,q_t)$ results in a vector payoff $A(p_t,q_t)\in {\mathbb R}^k$ . Given $a_t$ is the average vector payoff at time $t$ , Blackwell’s Approachability Theorem is a necessary and sufficient condition so that, regardless of the adversary’s decisions, the player makes the sequence of vectors $\{a_t\}_{t=1}^\infty$ approach a convex set ${\mathcal A}$ .

Continue reading “Blackwell Approachability”

Weighted Majority Algorithm

The Weighted Majority Algorithm is a randomized rule used to learn the best action amongst a fixed reference set.

Continue reading “Weighted Majority Algorithm”

Power-of-k Choices

We consider a model of a large number of single server queues. When a job arrives, we assume it chooses between $k$ queues. The job then chooses to join the shortest of these queues. We show that such choice can dramatically reduce queue sizes.

Continue reading “Power-of-k Choices”

Little’s Law

$\bar{N}=\lambda \bar{W}.$

Here $\bar{N}$ is the long run queue length; $\bar{W}$ is the expected waiting time; $\lambda$ is the arrival rate at the queue.

Continue reading “Little’s Law”

Diffusion Control Problems

The Hamilton-Jacobi-Bellman Equation.
Heuristic derivation of the HJB equation.

Continue reading “Diffusion Control Problems”

Continuous Time Dynamic Programs

Continuous-time dynamic programs
The HJB equation; a heuristic derivation; and proof of optimality.

Continue reading “Continuous Time Dynamic Programs”