Mustahkamlash bilan o’qitishga asoslangan ta’lim asoslari

Dinamik dasturlash
"Dinamik dasturlash" (DD) atamasi Markov qaror qabul qilish jarayoni (MQQJ) sifatida atrof-muhitning ideal modelini hisobga olgan holda optimal strategiyani qurish uchun algoritmlar to'plamini anglatadi. Mustahkamlash bilan o‘qitishda klassik DD algoritmlarini qo‘llash modeli ideal deb taxmin qilinganligi sababli ham, yuqori hisoblash xarajatlari tufayli ham juda cheklangan; shunga qaramay, bu algoritmlar nazariy jihatdan muhim ahamiyatga ega. Ko'rib chiqilayotgan usullar DD bilan bir xil maqsadlarga xizmat qiladi, ammokamroq hisoblashlar talab qilinadi va ekologik model ideal deb hisoblanmaydi.
Uning holatlari va harakatlari to‘plamlari S va A(s), s ∈ S chekli, dinamikasi esa o‘tish ehtimolilar to‘plami bilan berilgan deb faraz qilinadi.

va kutilgan mukofotlar darhol qabul qilindi

DD va umuman mustahkamlash bilan o'qitishning asosiy g'oyasi yaxshi strategiyalarni qidirishni yaratish va tuzish uchun qiymat funktsiyasidan foydalanishdir. Optimal strategiyani Bellman optimallik tenglamasini qanoatlantiruvchi V ∗ yoki Q∗ qiymat funksiyalarini belgilash orqali osongina olish mumkin:

yoki

Dinamik dasturlash samaradorligi
DD juda katta muammolarni hal qilish uchun unchalik qulay bo'lmasligi mumkin, ammo MQQJ hisoblashning boshqa usullari bilan solishtirganda, DD usullari ancha samarali. Ba'zi texnik tafsilotlarni hisobga olmagan holda, optimal strategiyani topish uchun DD usullari talab qiladigan vaqt (eng yomon holatda) polinom tomonidan baholanadi, uning darajasi holatlar va harakatlarning umumiy soniga teng. Agar n va m holatlar va harakatlar sonini bildirsa, u holda DD usulida talab qilinadigan hisoblash amallari soni ba'zi (n+m) darajali ko'phadli funktsiyaning qiymatidan kichik bo'ladi. DD usuli (deterministik) strategiyalarning umumiy soni mn bo'lganida ham, polinomial vaqtda optimal strategiyani topishni kafolatlaydi. Shu ma'noda, DD strategiya makonida mumkin bo'lgan har qanday to'g'ridan-to'g'ri qidiruvga qaraganda eksponent ravishda tezroq, chunki to'g'ridan-to'g'ri qidiruv natijaning o'xshash kafolatlarini berish uchun har bir strategiyani to'liq o'rganishi kerak. MQQJ bilan ishlash uchun chiziqli dasturlash usullaridan ham foydalanish mumkin va ba'zi hollarda ularning yaqinlashishi kafolatlari hatto eng yomon holatda ham DD usullaridan yaxshiroqdir. Ammo chiziqli dasturlash usullari DD holatiga qaraganda holatlar soni ancha kichikroq bo'lganida (100 tagacha) o'z samarasini yo'qotadi. Juda katta muammolar uchun faqat DD usullari mos keladi. Ba'zida DD ning qo'llanilish ko'lami "o'lchovlilik la'nati" (Bellman, 1957a) bilan cheklangan deb hisoblashadi, ya'ni holatlarni tavsiflovchi o'zgaruvchilar soni ortishi bilan mumkin bo'lgan holatlar soni eksponental ravishda o'sib boradi. Holatlarning katta to'plami ba'zi qiyinchiliklarni keltirib chiqaradi, ammo ular DD usullarining xususiyati emas, balki hal qilinayotgan muammoning o'ziga xos xususiyatidir. Darhaqiqat, DD usullari to'g'ridan-to'g'ri qidirish yoki chiziqli dasturlash kabi raqobatdosh usullardan ko'ra katta holatlar to'plami bilan ishlash uchun ko'proq mos keladi. Amalda, zamonaviy kompyuterlarning imkoniyatlarini hisobga olgan holda, DD usullari millionlab holatlar mavjud MQQJni hal qilish uchun ishlatilishi mumkin. Strategiyalar bo'yicha iteratsiya ham, qiymatlar bo'yicha iteratsiya ham keng qo'llaniladi va bu usullardan qaysi biri umumiy holatda yaxshiroq ekanligini aytish mumkin emas. Amaliy muammolarni hal qilishda, bu usullar odatda nazariy hisoblangan eng yomon holatlardagiga qaraganda tezroq bir biriga yaqinlashadi, ayniqsa ular yaxshi boshlang'ich qiymat funktsiyalari va strategiyalari bilan boshlangan bo'lsa.