Markov karar süreçlerinde yapısal sınıflar ve dinamik programlama yöntemlerinin etkinliği

Abstract

IV ÎZET Bu çalışmada, standart ardışık yaklaşımlar,, Jakobi, Gauss- Seidelj ekstrapolasyon ve değer-kökenli yöntemler gibi bazı dinamik programlama algoritmalarının etkinliği ile Iskontolu toplam maliyet problemleri diye bilinen önemli bir Markov karar süreci problemi sınıfının yapısı arasındaki ilişkiler araştırılmıştır. Markov karar süreçleri kuramının ve 'uygula ma potansiyelinin i960' dan bu yana hızla gelişmesine karşın konunun gerçek yaşamdaki kullanımı henüz ait düzeydedir. Bu nun ana nedeni gerçek yaşam problemlerinin karmaşık ve büyük ölçekli yapısıdır. Uygulamada, bir Markov karar süreci mode linin farklı parametre değerleri için tekrar tekrar çözülmesi gerektiğinden hesaplama için harcanan çabada yapılacak her tür indirgeme çok önemli olacaktır. Bu indirgeme kullanılan algoritmanın etkinliğine, bu etkinlik ise Markov karar süre ci probleminin yapısına bağlıdır. Ancak bu ilişkilerin nite liği henüz yeterince bilinmemektedir. işte bu çalışmada, bu problem bir çok değişkenli varyans analizi (Ç.D.V.A.) düzeni altında incelenmiştir. Bu istatistiksel yaklaşım, etkinlik- yapı probleminin çözümü için gerekli olan iyi-tasarlanmış de ney düzenlerinden birisidir. Konuyla ilişkili kuramsal so-' nuçiar ve teknik meteryai özetlendikten sonra, iki deneme et kenli ve beş değişkenli Ç.D.V.A. düzeninin sonuçları tartı-: silmiştir. Burada, bağımsız değişkenlerden biri, olasılık matrisleri ile karakterize edilen problem yapısını, öteki ise Markov karar süreci dönüşümlerini temsil etmektedir. Bunla rın ikisi de beş düzeyli ve sabit seçimlidir. Bağımlı değiş kenlerin herbiri beş temel ardışık yaklaşımlar algoritmasının belli bir anlamdaki etkinliğini temsil etmektedirler. Bu ko şullar altında elde edilen haraveri, betimsel yöntemler ve te mel bileşenler Ç.D.V.A. ile incelenmiş ve sonuçlar tartışıl mıştır.

SUMMARY The investegated main topic of this work is the relations between the efficiency of some dynamic programming algo rithms, such as standart successive approximations, accele rated successive approximations, extrapolations, value- oriented methods, and the structure of an important class of Markov decision processes» expected discounted total cost problems. The theory of Markov decision processes has ex panded at an increasing rate since 1960, until we have now a broad understanding of the general theory. Meanwhile, the potential areas of application have also increased, if at a much slower rate. The one disappointing feature has been that the practical use of Markov decision processes has been minimal'. The main reason is the complexity of real real- world problems. In practical situations,, one has to solve the Markov decision problem again and again with different values of the parameters as well as with modified state and action spaces. So, the reduction of the computational effort might be very valuable. Such reduction is closely related with the efficiency of existing successive approximations variants and, this efficiency is strongly depended on the structure of the Markov decision processes which can be characterized with the dimensions of state and action spaces, probability matricies, cost function, discounting factor, etc. However, such relationships are not completely clear- In this work, this problem has been studied under a MANOVA design. This statistical approach is one of the required well-designed experimental designs for this efficiency-structure problem. After summarizing some of the theoretical results and tecni- cal materials, results of the MANOVA design which has two treatment factors and five dependent variables, have been discussed. One of the independent variables represents prob lem structure which has- been characterized only probability matricies and the other represents data transformations. Each of these is a five-level factors with fixed selection. Each of five dependent variables represents.in a certain manner, the efficiency of selected five main successive approxina-*VI tions variants. Under these conditions 5 experiment has been performed with randomly selected test problems such that each belongs to one of the five structural classes and then, transf creations have been applied and efficiency measures have been recorded,. This raw data has been analysed with descriptive statistical methods;, descriptive factor analysis and principal components MANOVA and the results have been discussed in the final section.