# Randomized program

### From Glossary

A randomized policy is a distribution over the policy set, that describes a policy as a random variable. This is not restricted to stochastic programs. The randomized form is called a *randomized program*, and it is the following semi-infinite program in response space:

where for finitely many and

In this form, the randomized program is an ordinary linear program if is finite. More generally, the definition of renders the summations well defined. One could interpret as a randomized policy: use with probability A *pure strategy* is when for some (so for
otherwise, is called a *mixed strategy*.

One key fact is that the solutions to the original mathematical program (in standard form) correspond to pure strategies in this randomized form. Further, a key to the Lagrangian Strong Duality Theorem is that every mixed strategy is dominated by a pure strategy. Moreover, this underlies the Generalized Lagrange Multiplier method, and there is no loss in optimality to restrict mixed strategies to satisfy the *Haar condition*: