Oracle in optimization
The definition of $\alpha$-Approximate  Stochastic oracle has been given in the paper that you provide on Page $3$.

Given a distribution $D$ over $\mathcal{L}$, an $\alpha$-approximate stochastic oracle $M(D)$ computes $x^*$ such that such that
$$\mathbb{E}_{L \sim D}[L(x^*)] \le  \alpha \min_{x \in \mathcal{X}} \mathbb{E}_{L \sim D}[L(x)]$$

You  need not know the details of $M$, but if you provide it with a distribution $D$, then it returns you an $x^*$ such that if you evaluate the expected loss it is an most $\alpha$ times the objective value of the minimum of the expected loss.
Notice that different papers use different definitions and you should find the definition in the paper itself, as you can see, the first paper uses a multiplicative definition but the second paper uses an additive definition.