  Risk sensitive decision making finds important applications in current day
use cases. Existing risk measures consider a single or finite collection of
random variables, which do not account for the asymptotic behaviour of
underlying systems. Conditional Value at Risk (CVaR) is the most commonly used
risk measure, and has been extensively utilized for modelling rare events in
finite horizon scenarios. Naive extension of existing risk criteria to
asymptotic regimes faces fundamental challenges, where basic assumptions of
existing risk measures fail. We present a complete simulation based approach
for sequentially computing Asymptotic CVaR (ACVaR), a risk measure we define on
limiting empirical averages of markovian rewards. Large deviations theory,
density estimation, and two-time scale stochastic approximation are utilized to
define a 'tilted' probability kernel on the underlying state space to
facilitate ACVaR simulation. Our algorithm enjoys theoretical guarantees, and
we numerically evaluate its performance over a variety of test cases.
