The answer is "$m+1$," not "$m$." A generalization of the problem you describe is to find a random vector $X \in \mathcal{X}$, where $\mathcal{X}$ is some multi-dimensional set, to solve: 

Problem 1: 
\begin{align} 
\mbox{Minimize: } \: \: & E[f(X)] \\
\mbox{Subject to: } \: \:  & E[g_i(X)] \leq b_i \: \: \forall i \in \{1, \ldots, m\} \\
& X \in \mathcal{X}
\end{align} 

An online variation is to find a sequence of random vectors $\{X(0), X(1), X(2), \ldots\}$ to solve: 

Problem 2: 
\begin{align} 
\mbox{Minimize: } \: \: & \limsup_{t\rightarrow\infty} \frac{1}{t}\sum_{\tau=0}^{t-1} E[f(X(\tau))] \\
\mbox{Subject to: }\: \:  & \limsup_{t\rightarrow\infty} \frac{1}{t}\sum_{\tau=0}^{t-1}E[g_i(X(\tau))] \leq b_i \: \: \forall i \in \{1, \ldots, m\} \\
& X(\tau) \in \mathcal{X} \: \: \forall \tau \in \{0, 1, 2,\ldots\}
\end{align}

Under mild conditions, optimality is described in the same way for both problems (the only technical issues are minor boundedness and closure type issues). Define the following set: 
$$ \mathcal{R} = \{(f(x), g_1(x), \ldots, g_m(x)) : x \in \mathcal{X}\} $$
For simplicity assume the set $\mathcal{R}$ is closed and bounded.  Define $Conv(\mathcal{R})$ as the convex hull of $\mathcal{R}$ (this is a closed, bounded, and convex set).  The problems 1 and 2 are feasible with infimum objective function value $f^*$ if and only if the following problem is feasible with the same minimum objective function value: 

Problem 3: 
\begin{align} 
\mbox{Minimize: } \: \:  & y_0\\
\mbox{Subject to:} \: \: & y_i \leq b_i \: \: \forall i \in \{1, \ldots, m\} \\
\: \: &   (y_0, \ldots, y_m) \in Conv(\mathcal{R})
\end{align} 

Now assume problem 3 is feasible and let $(y_0^*, \ldots, y_m^*)$ be an optimal solution (such exists by compactness).  This is a vector in $Conv(\mathcal{R})$ in $m+1$ dimensional space and hence can be achieved as a convex combination of at most $m+2$ points in $Conv(\mathcal{R})$ (by Caratheodory's theorem).  However, it can be shown this vector is on the _boundary_ of $Conv(\mathcal{R})$, and a simple extension of Caratheodory shows it can thus be achieved as a convex combination of at most $m+1$ points. 

***
The bound $m+1$ is "tight."  An example is a problem with $m=1$ constraint such as this:  Let $\mathcal{X} = \{0,1\}$ (consisting of two points).  Define $f(x) = x$, $g(x) = -x$. We want to solve: 
\begin{align} 
\mbox{Minimize: } \: \: & E[X] \\
\mbox{Subject to: } \: \:  & E[-X] \leq -0.5\\
 \: \: & X \in \{0, 1\} 
\end{align} 
The optimal solution is to allocate according to a random vector with $Pr[X=0]=Pr[X=1]=1/2$.  There is $1$ constraint ($m=1$), and here we need a solution with $1+1=2$ points of support. 

***
I have worked a lot with "Problem 2" type problems in stochastic optimization, where the "drift-plus-penalty" algorithm is a nice solver for these problems as well as more complex ones with random state changes.  I feel awkward giving two "self-references" but these are directly related to what I describe above: 

1) This develops the performance region $Conv(\mathcal{R})$ I allude to above, and gives online solvers: 

"Stochastic Network Optimization with Application to Communication and Queueing Systems," Morgan & Claypool, 2010.  
http://www.morganclaypool.com/doi/abs/10.2200/S00271ED1V01Y201006CNT007

2) "Distributed stochastic optimization via correlated scheduling," IEEE Transactions on Networking.  

http://ee.usc.edu/stochastic-nets/docs/distributed-optimization-ton.pdf

This paper uses the $m+1$ observation, and the footnote on page 13 is the same as my comment above about generalizing Caratheodory's theorem.