8

Value iteration is one of the most commonly used methods to solve Markov decision processes. Its convergence rate obviously depends on the number of states and actions. However, the convergence rate also largely varies between different MDPs with a similar number of states/actions.

Are there specific characteristics that imply a slow convergence? And can we re-model such systems to accelerate the convergence of value iteration? For instance, in my experience, systems with sparse transition matrices generally converge considerably slower than systems with dense transition matrices. This holds in particular if there are so-called cycles in the transition matrix.

Michiel uit het Broek
  • 2,491
  • 2
  • 15
  • 36

1 Answers1

2

I will answer on the basis of one particular case of MDPs. There have been a few recent articles that extensively discuss the issues of the diversification of MDPs and introduce a new model known as the MDP-DIV (Markov Decision Process for Diversifying). For that I refer you to Xia et al. (2017).

It is identified that the main causes for slow convergence are data scarcity/sparse transition matrices as you have pointed out, and a large action space.

Two new approaches to accelerate the convergence rate are detailed in Liu et al. (2018). Here, I will quote the relevant parts of the abstract.

The MDP-DIV-kNN method adopts a $k$ nearest neighbor strategy, i.e., discarding the $k$ nearest neighbors of the recently-selected action (document), to reduce the diversification searching space.

The MDP-DIVNTN employs a pre-trained diversification neural tensor network (NTNDIV) as the evaluation model, and combines the results with MDP to produce the final ranking solution.

The experiment results demonstrate that the two proposed methods indeed accelerate the convergence rate of the MDP-DIV, which is 3x faster, while the accuracies produced barely degrade, or even are better.

References

[1] Xia, L., Xu, J., Lan, Y., Guo, J., Zeng, W., Cheng, X. (2017). Adapting markov decision process for search result diversification. pp. 535–544. SIGIR ’17, ACM, New York, NY, USA.

[2] Liu, F., Tang, R., Li, X., Ye, Y., Guo, H., He, X. (2018). Novel Approaches to Accelerating the Convergence Rate of Markov Decision Process for Search Result Diversification. https://arxiv.org/pdf/1802.08401.pdf.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55