Combining importance sampling and temporal difference control variates to simulate Markov Chains
Combining importance sampling and temporal difference control variates to simulate Markov Chains
复制标题
结合重要性采样和时间差异控制变量来模拟马尔可夫链
DOI：
10.1145/974734.974735
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
S. Juneja
中科院分区：
文献类型：
--
作者：
R. Randhawa;S. Juneja
众所周知，在估计与随机系统相关的性能指标时，一个好的重要性抽样分布（IS）可以使方差减少几个数量级，而一个坏的重要性抽样分布可能导致大的，甚至无限的方差。在本文中，我们研究如何估计方差的重要性抽样变化的措施可能会“阻尼”的重要性抽样与随机近似为基础的时间差（TD）方法相结合的敏感性。我们考虑一个有限的状态空间离散时间马尔可夫链（DTMC）的一步转移奖励和吸收的状态集，并专注于估计从任何状态开始的累积预期奖励吸收。在这种情况下，我们开发了充分的条件下，从组合方法产生的估计有一个均方误差，渐近等于零，即使通过使用唯一的重要性抽样变化的措施形成的估计有无穷大的方差。特别是，我们认为在排队网络中的小缓冲区溢出概率估计的问题，在文献中建议的措施的变化被证明在某些参数下具有无穷大的方差，并在适当的IS和TD方法的组合，可以从经验上看到有一个更快的收敛速度相比，天真的模拟。
It is well known that in estimating performance measures associated with a stochastic system a good importance sampling distribution (IS) can give orders of magnitude of variance reduction while a bad one may lead to large, even infinite, variance. In this paper we study how this sensitivity of the estimator variance to the importance sampling change of measure may be "dampened" by combining importance sampling with stochastic approximation based temporal difference (TD) method. We consider a finite state space discrete time Markov chain (DTMC) with one-step transition rewards and an absorbing set of states and focus on estimating the cumulative expected reward to absorption starting from any state. In this setting we develop sufficient conditions under which the estimate resulting from the combined approach has a mean square error that asymptotically equals zero even when the estimate formed by using only importance sampling change of measure has infinite variance. In particular, we consider the problem of estimating the small buffer overflow probability in a queuing network, where the change of measure suggested in literature is shown to have infinite variance under certain parameters and where the appropriate combination of IS and TD method can be empirically seen to have a much faster convergence rate compared to naive simulation.