We develop a new stochastic programming methodology for determining optimal vaccination policies for a multi-community heterogeneous population. An optimal policy provides the minimum number of vaccinations required to drive post-vaccination reproduction number to below one at a desired reliability level. To generate a vaccination policy, the new method considers the uncertainty in COVID-19 related parameters such as efficacy of vaccines, age-related variation in susceptibility and infectivity to SARS-CoV-2, distribution of household composition in a community, and variation in human interactions. We report on a computational study of the new methodology on a set of neighboring U.S. counties to generate vaccination policies based on vaccine availability. The results show that to control outbreaks at least a certain percentage of the population should be vaccinated in each community based on pre-determined reliability levels. The study also reveals the vaccine sharing capability of the proposed approach among counties under limited vaccine availability. This work contributes a decision-making tool to aid public health agencies worldwide in the allocation of limited vaccines under uncertainty towards controlling epidemics through vaccinations.