The ability to quantify how well an action is carried out, also known as action quality assessment (AQA), is widely studied across scientific disciplines due to its broad range of applications. Therefore, there has been a surging interest in the vision community to develop video-based AQA. Unfortunately, prior methods often ignore the score rubric used by human experts and fall short at quantifying the uncertainty of the model prediction. To bridge the gap, we present RICA^2--- a deep probabilistic model that integrates score rubric and accounts for prediction uncertainty for AQA. Central to our method lies in stochastic embeddings of action steps, defined on a graph structure that encodes the score rubric. The embeddings spread probabilistic density in the latent space, and allow our method to represent model uncertainty. The graph encodes the scoring criteria, based on which the quality scores can be decoded. We demonstrate that our method establishes new state-of-the-art on public benchmarks including FineDiving, MTL-AQA, and JIGSAWS, with superior performance in score prediction and uncertainty calibration.