عملية اتخاذ القرار ماركوف

عملية اتخاذ القرار ماركوف ( MDP ) هي نموذج رياضي لاتخاذ القرارات المتسلسلة عندما تكون النتائج غير مؤكدة. ^{[ 1 ]} وهي نوع من أنواع عمليات اتخاذ القرار العشوائية ^{[ 2 ]} ، وغالبًا ما يتم حلها باستخدام أساليب البرمجة الديناميكية العشوائية .

نشأت نماذج ماركوف للقرار (MDPs) من بحوث العمليات في خمسينيات القرن الماضي، ^{[ 3 ]}^{[ 4 ]} ومنذ ذلك الحين، حظيت باعتراف واسع في مجالات متنوعة، تشمل علم البيئة ، والاقتصاد ، والرعاية الصحية ، والاتصالات ، والتعلم المعزز . ^{[ 5 ]} يستخدم التعلم المعزز إطار عمل نماذج ماركوف للقرار لنمذجة التفاعل بين عامل التعلم وبيئته. في هذا الإطار، يتميز التفاعل بالحالات، والإجراءات، والمكافآت. صُمم إطار عمل نماذج ماركوف للقرار لتقديم تمثيل مبسط للعناصر الأساسية لتحديات الذكاء الاصطناعي . يتضمن إطار النمذجة هذا فهم السبب والنتيجة ، وإدارة عدم اليقين واللا حتمية، والسعي لتحقيق أهداف محددة. ^{[ 5 ]}

يُستمد الاسم من ارتباطه بسلاسل ماركوف ، وهو مفهوم طوره عالم الرياضيات الروسي أندريه ماركوف . تشير كلمة "ماركوف" في "عملية اتخاذ القرار ماركوف" إلى البنية الأساسية لانتقالات الحالة التي لا تزال تتبع خاصية ماركوف . تُسمى هذه العملية "عملية اتخاذ قرار" لأنها تتضمن اتخاذ قرارات تؤثر على انتقالات الحالة هذه، مما يوسع مفهوم سلسلة ماركوف ليشمل مجال اتخاذ القرار في ظل عدم اليقين.

تعريف

عملية اتخاذ القرار ماركوف هي عبارة عن رباعية $(S,A,P_{a},R_{a})$ ، أين:

$S$ هي مجموعة من الحالات تسمى فضاء الحالة . قد يكون فضاء الحالة منفصلاً أو متصلاً، مثل مجموعة الأعداد الحقيقية .
$A$ هي مجموعة من الإجراءات تسمى فضاء الإجراءات (أو، بدلاً من ذلك، $A_{s}$ هي مجموعة الإجراءات المتاحة من الدولة $s$ أما بالنسبة للحالة، فقد تكون هذه المجموعة منفصلة أو متصلة.
$P_{a}(s,s')$ هو احتمال أن يكون الفعل $a$ في الولاية $s$ في ذلك الوقت $t$ سيؤدي ذلك إلى حالة $s'$ في ذلك الوقت $t+1$ بشكل عام، يُعرَّف هذا الانتقال الاحتمالي بحيث يحقق $\Pr(s_{t+1}\in S'\mid s_{t}=s,a_{t}=a)=\int _{S'}P_{a}(s,s')ds',$ لكل $S'\subseteq S$ قابل للقياس. في حالة كون فضاء الحالة منفصلاً، يُقصد بالتكامل قياس العد ، بحيث يتبسط الأخير إلى $P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)$ في حالة $S\subseteq \mathbb {R} ^{d}$ ، عادةً ما يُقصد بالتكامل بالنسبة إلى مقياس ليبيغ .
$R_{a}(s,s')$ هي المكافأة الفورية (أو المكافأة الفورية المتوقعة) التي يتم الحصول عليها بعد القيام بالعمل $a$ يتم اتخاذها للانتقال من حالة $s$ للتصريح $s'$ . المكافأة هي في العموم متغير عشوائي .

وظيفة السياسة $\pi$ هي عملية ربط (احتمالية محتملة) من فضاء الحالة ( $S$ ) إلى مساحة العمل ( $A$ ).

هدف التحسين

الهدف في عملية اتخاذ القرار في نموذج ماركوف هو إيجاد "سياسة" جيدة لصانع القرار: دالة $\pi$ ذلك يحدد الإجراء $\pi (s)$ أن صانع القرار سيختار عندما يكون في الولاية $s$ بمجرد دمج عملية اتخاذ القرار ماركوف مع السياسة بهذه الطريقة، يتم تحديد الإجراء لكل حالة، ويتصرف المزيج الناتج كسلسلة ماركوف (حيث يتم اختيار الإجراء في الحالة). $s$ يتم تحديده بالكامل بواسطة $\pi (s)$ ).

الهدف هو اختيار سياسة $\pi$ سيؤدي ذلك إلى تعظيم دالة تراكمية معينة للمكافآت العشوائية، وعادةً ما تكون المجموع المتوقع بعد الخصم على مدى أفق زمني لا نهائي محتمل:

E\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\right]

(حيث نختار)

a_{t}=\pi (s_{t})

(أي الإجراءات التي تنص عليها السياسة). ويتم استيعاب التوقع.

s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})

أين $\ \gamma \$ هل عامل الخصم مُرضٍ؟ $0\leq \ \gamma \ \leq \ 1$ ، وهو ما يكون عادةً قريبًا من $1$ (على سبيل المثال، $\gamma =1/(1+r)$ للحصول على بعض أسعار الخصم $r$ ). إن انخفاض عامل الخصم يجعل صانع القرار أكثر قصر نظر، لأنه يتجاهل نسبياً التأثير الذي قد يترتب على اتباع سياسته الحالية في بعض الأحيان في المستقبل البعيد.

ثمة هدف آخر محتمل، ولكنه مرتبط ارتباطًا وثيقًا، ويُستخدم عادةً وهو $H-$ عائد الخطوة. هذه المرة، بدلاً من استخدام عامل الخصم $\ \gamma \$ ، لا يهتم الوكيل إلا بالأول $H$ خطوات العملية، مع حصول كل مكافأة على نفس الوزن.

E\left[\sum _{t=0}^{H-1}{R_{a_{t}}(s_{t},s_{t+1})}\right]

(حيث نختار)

a_{t}=\pi (s_{t})

(أي الإجراءات التي تنص عليها السياسة). ويتم استيعاب التوقع.

s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})

أين $\ H\$ هو الأفق الزمني. بالمقارنة مع الهدف السابق، فإن الهدف الأخير يُستخدم بشكل أكبر في نظرية التعلم .

تُسمى السياسة التي تُعظّم الدالة المذكورة أعلاه بالسياسة المثلى ، ويُرمز لها عادةً بـ $\pi ^{*}$ قد يمتلك نموذج ماركوف للقرار (MDP) عدة سياسات مثلى متميزة. وبسبب خاصية ماركوف ، يمكن إثبات أن السياسة المثلى هي دالة للحالة الراهنة، كما هو مفترض أعلاه. $R_{a}(s,s')$ إذا كانت حتمية، فسيكون هناك دائمًا سياسة مثلى $\pi ^{*}$ وهو أمر حتمي أيضاً.

[دليل]

افترض أن $R$ هو حتمي، أي بالنسبة للثوابت $a,s,s'$ القيمة $R_{a}(s,s')$ وهو ثابت أيضًا. لـ $\gamma <1$ من المعروف أن هناك نقطة ثابتة فريدة $V^{*}$ والتي تحقق التكرار القيمي (معادلة بيلمان)

$V^{*}(s)=\max _{a}E\left[R_{a}(s,s')+\gamma V^{*}(s')\right]$

من خلال الفحص، لاحظ أن هذه النقطة الثابتة هي دالة القيمة المرتبطة بالسياسة التالية.

$\pi ^{*}(s):=\arg \max _{a}E\left[R_{a}(s,s')+\gamma V^{*}(s')\right]$

من خلال فكّ تكرار بيلمان، يمكن للمرء أن يُظهر أن $V^{*}$ إنها بالفعل الأمثل (في وقت واحد لجميع الحالات) على مجموعة السياسات الحتمية.

${\begin{aligned}V^{*}(s_{0})&=\max _{a_{0}}E\left[R_{a_{0}}(s_{0},s_{1})+\gamma V^{*}(s_{1})\right]\\&=\max _{a_{0}}E\left[R_{a_{0}}(s_{0},s_{1})+\gamma \max _{a_{1}}E\left[R_{a_{1}}(s_{1},s_{2})+\gamma V^{*}(s_{2})\right]\right]\\&=\max _{a_{0},a_{1}}E\left[R_{a_{0}}(s_{0},s_{1})+\gamma \left(R_{a_{1}}(s_{1},s_{2})+\gamma V^{*}(s_{2})\right)\right]\\&=\sup _{\{a_{t}\}_{t=0}^{\infty }}E\left[\sum _{t=0}^{\infty }\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})\right]\end{aligned}}$

لنفترض الحالة التي $\pi$ هو احتمالي، بمعنى أن الإجراء المتخذ $a:=\pi (s)$ هو متغير عشوائي. يمكن إثبات أن أي سياسة غير حتمية من هذا القبيل تهيمن عليها سياسة حتمية $\pi ^{*}$ على النحو التالي.

${\begin{aligned}V^{*}(s_{0})&=\max _{a_{0}}E\left[R_{a_{0}}(s_{0},s_{1})+\gamma V^{*}(s_{1})\right]\\&\geq E\left[R_{\pi (s_{0})}(s_{0},s_{1})+\gamma V^{*}(s_{1})\right]\\&=E\left[R_{\pi (s_{0})}(s_{0},s_{1})+\gamma \max _{a_{1}}E\left[R_{a_{1}}(s_{1},s_{2})+\gamma V^{*}(s_{2})\right]\right]\\&\geq E\left[R_{\pi (s_{0})}(s_{0},s_{1})+\gamma \left(R_{\pi (s_{1})}(s_{1},s_{2})+\gamma V^{*}(s_{2})\right)\right]\\&\geq E\left[\sum _{t=0}^{\infty }\gamma ^{t}R_{\pi (s_{t})}(s_{t},s_{t+1})\right]\end{aligned}}$

نماذج المحاكاة

في كثير من الحالات، يصعب تمثيل توزيعات احتمالية الانتقال، $P_{a}(s,s')$ بشكل صريح. في مثل هذه الحالات، يمكن استخدام محاكاة لنمذجة عملية ماركوف للقرار ضمنيًا من خلال توفير عينات من توزيعات الانتقال. أحد الأشكال الشائعة لنموذج عملية ماركوف للقرار الضمني هو محاكاة البيئة الدورية التي يمكن تشغيلها من حالة أولية، وتُنتج حالة ومكافأة لاحقة في كل مرة تتلقى فيها مدخلات فعل. بهذه الطريقة، يمكن إنتاج مسارات الحالات والأفعال والمكافآت، والتي تُسمى غالبًا بالحلقات .

يُعدّ النموذج التوليدي شكلاً آخر من أشكال المحاكاة ، وهو عبارة عن محاكاة أحادية الخطوة قادرة على توليد عينات من الحالة التالية ومكافأة بناءً على أي حالة وفعل. ^{[ 6 ]} (تجدر الإشارة إلى أن هذا المعنى يختلف عن مصطلح النموذج التوليدي في سياق التصنيف الإحصائي ). في الخوارزميات التي تُعبّر عنها باستخدام الشفرة الزائفة ، $G$ يُستخدم غالبًا لتمثيل نموذج توليدي. على سبيل المثال، التعبير $s',r\gets G(s,a)$ قد يشير ذلك إلى عملية أخذ العينات من النموذج التوليدي حيث $s$ و $a$ الوضع الراهن والإجراءات المتخذة، و $s'$ و $r$ تمثل الحالة الجديدة والمكافأة. بالمقارنة مع المحاكاة العرضية، يتميز النموذج التوليدي بقدرته على توليد بيانات من أي حالة، وليس فقط تلك التي تمت مواجهتها في مسار معين.

تشكل فئات النماذج هذه تسلسلاً هرمياً لمحتوى المعلومات: يُنتج النموذج الصريح نموذجاً توليدياً بسهولة من خلال أخذ عينات من التوزيعات، ويؤدي التطبيق المتكرر للنموذج التوليدي إلى محاكاة دورية. في المقابل، لا يمكن تعلم نماذج تقريبية إلا من خلال الانحدار . يلعب نوع النموذج المتاح لعملية ماركوف القرار (MDP) دوراً هاماً في تحديد خوارزميات الحل المناسبة. على سبيل المثال، تتطلب خوارزميات البرمجة الديناميكية الموضحة في القسم التالي نموذجاً صريحاً، ويتطلب بحث شجرة مونت كارلو نموذجاً توليدياً (أو محاكاة دورية يمكن نسخها في أي حالة)، بينما لا تتطلب معظم خوارزميات التعلم المعزز سوى محاكاة دورية.

مثال

ومن الأمثلة على عملية اتخاذ القرار ماركوف نموذج موازنة الأقطاب، والذي ينبع من نظرية التحكم الكلاسيكية.

في هذا المثال، لدينا

$S$ هي مجموعة من الصفوف المرتبة $(\theta ,{\dot {\theta }},x,{\dot {x}})$ يتم تحديدها بواسطة زاوية القطب، والسرعة الزاوية، وموضع العربة وسرعتها.
$A$ يكون $\{-1,1\}$ ، وهو ما يتوافق مع تطبيق قوة على اليسار (اليمين) على العربة.
$P_{a}(s,s')$ إنها عملية انتقال النظام، والتي ستكون في هذه الحالة حتمية ومدفوعة بقوانين الميكانيكا.
$R_{a}(s,s')$ يكون $1$ إذا كان العمود مرفوعًا بعد الانتقال، فتكون قيمته صفرًا في غير ذلك. لذلك، تعتمد هذه الدالة فقط على $s'$ في هذه الحالة تحديداً.

الخوارزميات

يمكن إيجاد حلول لعمليات ماركوف القرار ذات فضاءات الحالة والفعل المحدودة باستخدام طرق متنوعة، مثل البرمجة الديناميكية . تنطبق الخوارزميات الواردة في هذا القسم على عمليات ماركوف القرار ذات فضاءات الحالة والفعل المحدودة، والتي تُعطى فيها احتمالات الانتقال ودوال المكافأة بشكل صريح، ولكن يمكن توسيع المفاهيم الأساسية لتشمل فئات أخرى من المسائل، على سبيل المثال باستخدام تقريب الدوال . كذلك، يمكن اختزال بعض العمليات ذات فضاءات الحالة والفعل اللانهائية القابلة للعد إلى عمليات ذات فضاءات حالة وفعل محدودة. ^{[ 7 ]}

تتطلب المجموعة القياسية من الخوارزميات لحساب السياسات المثلى لعمليات ماركوف القرار ذات الحالات والإجراءات المحدودة مساحة تخزين لمصفوفتين مفهرستين حسب الحالة والقيمة . $V$ والتي تحتوي على قيم حقيقية، وسياسة $\pi$ والتي تحتوي على الإجراءات. في نهاية الخوارزمية، $\pi$ سيحتوي على الحل و $V(s)$ سيحتوي على المبلغ المخفض للمكافآت التي يمكن الحصول عليها (في المتوسط) باتباع هذا الحل من الولاية $s$ .

تتألف الخوارزمية من خطوتين: (1) تحديث القيمة، و(2) تحديث السياسة، وتُكرر هاتان الخطوتان بترتيب معين لجميع الحالات حتى لا تحدث أي تغييرات أخرى. وتقوم كلتا الخطوتين بتحديث تقدير جديد للسياسة المثلى وقيمة الحالة بشكل متكرر باستخدام تقدير سابق لتلك القيم.

V(s):=\sum _{s'}P_{\pi (s)}(s,s')\left(R_{\pi (s)}(s,s')+\gamma V(s')\right)

\pi (s):=\operatorname {argmax} _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V(s')\right)\right\}

يعتمد ترتيب هذه الخطوات على نوع الخوارزمية؛ إذ يمكن تطبيقها على جميع الحالات دفعة واحدة أو حالةً تلو الأخرى، وبشكل متكرر على بعض الحالات أكثر من غيرها. وطالما لم تُستبعد أي حالة بشكل دائم من أي من الخطوتين، ستصل الخوارزمية في النهاية إلى الحل الصحيح. ^{[ 8 ]}

المتغيرات البارزة

تكرار القيمة

في تكرار القيمة ( بيلمان 1957 ) ، والذي يُسمى أيضًا بالاستقراء العكسي ، $\pi$ لم يتم استخدام الدالة؛ بدلاً من ذلك، قيمة $\pi (s)$ يتم حسابها في غضون $V(s)$ عند الحاجة. استبدال حساب $\pi (s)$ في حساب $V(s)$ يعطي الخطوة المدمجة؛

V_{i+1}(s):=\max _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V_{i}(s')\right)\right\},

أين $i$ هو رقم التكرار. يبدأ تكرار القيمة عند $i=0$ و $V_{0}$ كتخمين لدالة القيمة . ثم تتكرر العملية، وتحسب بشكل متكرر $V_{i+1}$ لجميع الولايات $s$ ، حتى $V$ يتقارب الطرف الأيسر مع الطرف الأيمن (وهي " معادلة بيلمان " لهذه المسألة ). وقد تضمنت ورقة لويد شابلي البحثية لعام 1953 حول الألعاب العشوائية، كحالة خاصة، طريقة تكرار القيمة لعمليات ماركوف القرار، ^{[ 9 ]} ولكن لم يتم الاعتراف بذلك إلا لاحقًا. ^{[ 10 ]}

يضمن تكرار القيمة التقارب لـ $\gamma <1$ بحسب نظرية باناش للنقطة الثابتة .

[دليل]

تنص نظرية باناش للنقطة الثابتة على أن أي دالة انكماشية لها نقطة ثابتة فريدة؛ علاوة على ذلك، يمكن الوصول إلى هذه النقطة الثابتة تقاربياً من خلال تطبيق دالة الانكماش بشكل متكرر. يكفي بعد ذلك إثبات أن تكرار القيمة هو دالة انكماشية، كما هو موضح أدناه. $\gamma <1$ .

دل $X_{a}^{V}(s):=\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V_{i}(s')\right)$ و $({\mathcal {B}}V)(s):=\max _{a}X_{a}^{V}(s)$ للتسهيل.

${\begin{aligned}\|{\mathcal {B}}V-{\mathcal {B}}W\|_{\infty }&=\max _{s}\left|({\mathcal {B}}V)(s)-({\mathcal {B}}W)(s)\right|\\&=\max _{s}\left|\max _{a}X_{a}^{V}(s)-\max _{a}X_{a}^{W}(s)\right|\\&\leq \max _{s}\max _{a}\left|X_{a}^{V}(s)-X_{a}^{W}(s)\right|\\&=\max _{s}\max _{a}\gamma \left|\sum _{s'}P_{a}(s,s')\left(V_{i}(s')-W_{i}(s')\right)\right|\\&\leq \max _{s}\max _{a}\gamma \max _{s'}\left|V_{i}(s')-W_{i}(s')\right|\\&=\gamma \max _{s'}\left|V_{i}(s')-W_{i}(s')\right|\\&=\gamma \|V_{i}-W_{i}\|_{\infty }\end{aligned}}$

تكرار السياسات

في عملية تكرار السياسة ^{[ 11 ]} ، يتم أولاً تحديد القيمة عن طريق حل المعادلة لـ $V$ ثم يقوم النظام الخطي الموصوف في الخطوة الأولى بتحسين السياسة عن طريق الحساب $\pi$ كما في الخطوة الثانية، ثم يكرر الخطوتين حتى تتقارب السياسة. (ابتكر هوارد تكرار السياسة لتحسين عملية إرسال كتالوجات سيرز بالبريد، والتي كان يعمل على تحسينها باستخدام تكرار القيمة. ^{[ 12 ]} )

بما أن تكرار السياسة يدمج بشكل فعال مشكلة عكسية خطية مع عملية غير خطية، فقد يتم تفسيره على أنه نوع من أساليب الاسترخاء .

يتميز هذا الخيار بوجود شرط توقف محدد، حيث يوجد حل فريد. $V$ لكل وثيقة $\pi$ تكتمل الخوارزمية بمجرد أن ينتج تحسين السياسة نفس السياسة مرتين متتاليتين.

على الرغم من وجود حالات قد يكون فيها تكرار السياسة أسرع من تكرار القيمة (على سبيل المثال عندما تكون مساحة العمل أكبر بكثير من مساحة الحالة)، إلا أن تكرار السياسة عادة ما يكون أبطأ من تكرار القيمة لعدد كبير من الحالات الممكنة.

تعديل تكرار السياسة

في عملية تكرار السياسة المعدلة ( فان نونين 1976 ؛ بوتيرمان وشين 1978 )، تُكرر الخطوة الأولى عدة مرات، ثم تُنفذ الخطوة الثانية مرة واحدة. ^{[ 13 ]}^{[ 14 ]} ثم تُكرر الخطوة الأولى مرة أخرى عدة مرات وهكذا.

عمليات كنس ذات أولوية

في هذا الشكل، تُطبق الخطوات بشكل تفضيلي على الحالات المهمة بطريقة ما – سواءً كان ذلك بناءً على الخوارزمية (حدثت تغييرات كبيرة في $V$ أو $\pi$ (حول تلك الولايات مؤخراً) أو بناءً على الاستخدام (تلك الولايات قريبة من ولاية البداية، أو ذات أهمية أخرى للشخص أو البرنامج الذي يستخدم الخوارزمية).

التعقيد الحسابي

توجد خوارزميات لإيجاد السياسات المثلى ذات تعقيد زمني متعدد الحدود بالنسبة لحجم تمثيل المسألة، وذلك بالنسبة لعمليات ماركوف القرار المحدودة. وبالتالي، تندرج مسائل القرار القائمة على عمليات ماركوف القرار ضمن فئة التعقيد الحسابي P. ^{[ 15 ]} مع ذلك، ونظرًا لظاهرة "لعنة الأبعاد" ، غالبًا ما يكون حجم تمثيل المسألة أُسّيًا بالنسبة لعدد متغيرات الحالة والفعل، مما يحد من تقنيات الحل الدقيق للمسائل ذات التمثيل المُختصر. عمليًا، يمكن لتقنيات التخطيط الفوري، مثل بحث شجرة مونت كارلو، إيجاد حلول مفيدة في المسائل الأكبر حجمًا، ونظريًا، من الممكن بناء خوارزميات تخطيط فوري قادرة على إيجاد سياسة شبه مثالية دون أي اعتماد على حجم فضاء الحالة في التعقيد الحسابي. ^{[ 16 ]}

التوسعات والتعميمات

عملية اتخاذ القرار ماركوف هي لعبة عشوائية بلاعب واحد فقط.

إمكانية الملاحظة الجزئية

يفترض الحل أعلاه أن الحالة $s$ يُعرف ذلك عندما يتعين اتخاذ إجراء؛ وإلا $\pi (s)$ لا يمكن حسابها. عندما لا يكون هذا الافتراض صحيحًا، تُسمى المشكلة عملية قرار ماركوف قابلة للملاحظة جزئيًا أو POMDP.

عمليات اتخاذ القرار المقيدة لماركوف

تُعدّ عمليات اتخاذ القرار ماركوف المقيدة (CMDPS) امتدادًا لعمليات اتخاذ القرار ماركوف (MDPs). وهناك ثلاثة اختلافات جوهرية بين MDPs وCMDPs. ^{[ 17 ]}

تترتب تكاليف متعددة بعد تطبيق إجراء بدلاً من إجراء واحد.
يتم حل مسائل القرار الحرج باستخدام البرامج الخطية فقط، ولا تعمل البرمجة الديناميكية .
تعتمد السياسة النهائية على الحالة الابتدائية.

تُطبَّق طريقة مُضاعِفات لاغرانج على مسائل القرار المشترك. وقد طُوِّرت العديد من الخوارزميات القائمة على لاغرانج.

طريقة التدرج الأولي الثنائي للسياسة الطبيعية. ^{[ 18 ]}

توجد العديد من التطبيقات لـ CMDPs. وقد تم استخدامها مؤخراً في سيناريوهات تخطيط الحركة في مجال الروبوتات. ^{[ 19 ]}

عملية اتخاذ القرار ماركوف في الزمن المستمر

في عمليات اتخاذ القرار ماركوفية ذات الزمن المتقطع، تُتخذ القرارات على فترات زمنية منفصلة. أما في عمليات اتخاذ القرار ماركوفية ذات الزمن المستمر ، فيمكن اتخاذ القرارات في أي وقت يختاره صانع القرار. وبالمقارنة مع عمليات اتخاذ القرار ماركوفية ذات الزمن المتقطع، فإن عمليات اتخاذ القرار ماركوفية ذات الزمن المستمر تُعدّ نموذجًا أفضل لعملية اتخاذ القرار في نظام ذي ديناميكيات مستمرة ، أي أن ديناميكيات النظام تُحدد بواسطة معادلات تفاضلية عادية . ويمكن تطبيق إطار النمذجة هذا على مجالات مثل أنظمة الانتظار ، والعمليات الوبائية، والعمليات السكانية .

كما هو الحال في عمليات اتخاذ القرار ماركوف ذات الزمن المتقطع، يسعى العامل في عمليات اتخاذ القرار ماركوف ذات الزمن المستمر إلى إيجاد السياسة المثلى التي من شأنها تعظيم المكافأة التراكمية المتوقعة. ويكمن الاختلاف الرئيسي عن الحالة القياسية في أنه، نظرًا للطبيعة المستمرة لمتغير الزمن، يتم استبدال الجمع بالتكامل.

\max \operatorname {E} _{\pi }\left[\left.\int _{0}^{\infty }\gamma ^{t}r(s(t),\pi (s(t)))\,dt\;\right|s_{0}\right]

أين $0\leq \gamma <1.$

الفضاء المتقطع: صياغة البرمجة الخطية

إذا كانت مساحة الحالة ومساحة الفعل محدودتين، فيمكننا استخدام البرمجة الخطية لإيجاد السياسة المثلى، وهي إحدى أوائل الطرق المُطبقة. هنا، نقتصر على النموذج الإرجودي، ما يعني أن عملية اتخاذ القرار الماركوفية ذات الزمن المستمر تتحول إلى سلسلة ماركوف إرجودية ذات زمن مستمر في ظل سياسة ثابتة . في ظل هذا الافتراض، على الرغم من أن صانع القرار يستطيع اتخاذ قرار في أي وقت في الحالة الراهنة، إلا أنه لا فائدة من اتخاذ إجراءات متعددة. من الأفضل اتخاذ إجراء فقط عندما ينتقل النظام من الحالة الراهنة إلى حالة أخرى. في ظل بعض الشروط، ^{[ 20 ]} إذا كانت دالة القيمة المثلى لدينا $V^{*}$ مستقل عن الدولة $i$ ، وسيكون لدينا المتباينة التالية:

g\geq R(i,a)+\sum _{j\in S}q(j\mid i,a)h(j)\quad \forall i\in S{\text{ and }}a\in A(i)

إذا كانت هناك دالة $h$ ، ثم ${\bar {V}}^{*}$ سيكون الأصغر $g$ بما يحقق المعادلة أعلاه. من أجل إيجاد ${\bar {V}}^{*}$ يمكننا استخدام نموذج البرمجة الخطية التالي:

برنامج خطي أولي (P-LP)

{\begin{aligned}{\text{Minimize}}\quad &g\\{\text{s.t}}\quad &g-\sum _{j\in S}q(j\mid i,a)h(j)\geq R(i,a)\,\,\forall i\in S,\,a\in A(i)\end{aligned}}

برنامج خطي مزدوج (D-LP)

{\begin{aligned}{\text{Maximize}}&\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\\{\text{s.t.}}&\sum _{i\in S}\sum _{a\in A(i)}q(j\mid i,a)y(i,a)=0\quad \forall j\in S,\\&\sum _{i\in S}\sum _{a\in A(i)}y(i,a)=1,\\&y(i,a)\geq 0\qquad \forall a\in A(i){\text{ and }}\forall i\in S\end{aligned}}

$y(i,a)$ يُعد حلاً قابلاً للتطبيق لمشكلة D-LP إذا $y(i,a)$ غير أصلي، ولكنه استوفى القيود في مسألة البرمجة الخطية الديناميكية. حل ممكن $y^{*}(i,a)$ يُقال إن D-LP هو الحل الأمثل إذا

{\begin{aligned}\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y^{*}(i,a)\geq \sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\end{aligned}}

لجميع الحلول الممكنة $y(i,a)$ إلى D-LP. بمجرد أن نجد الحل الأمثل $y^{*}(i,a)$ ، يمكننا استخدامه لوضع السياسات المثلى.

الفضاء المتصل: معادلة هاميلتون-جاكوبي-بيلمان

في عملية ماركوف للقرار ذات الزمن المستمر، إذا كانت فضاءات الحالة وفضاءات الفعل متصلة، فيمكن إيجاد المعيار الأمثل بحل معادلة هاميلتون-جاكوبي-بيلمان التفاضلية الجزئية (HJB) . ولمناقشة معادلة HJB، نحتاج إلى إعادة صياغة المسألة.

{\begin{aligned}V(s(0),0)={}&\max _{a(t)=\pi (s(t))}\int _{0}^{T}r(s(t),a(t))\,dt+D[s(T)]\\{\text{s.t.}}\quad &{\frac {ds(t)}{dt}}=f[t,s(t),a(t)]\end{aligned}}

$D(\cdot )$ هي دالة المكافأة النهائية، $s(t)$ هو متجه حالة النظام، $a(t)$ هو متجه التحكم في النظام الذي نحاول إيجاده. $f(\cdot )$ يوضح الشكل كيف يتغير متجه الحالة بمرور الوقت. معادلة هاميلتون-جاكوبي-بيلمان هي كما يلي:

0=\max _{a}(r(t,s,a)+{\frac {\partial V(t,s)}{\partial s}}f(t,s,a))

يمكننا حل المعادلة لإيجاد دالة القيمة المثلى $V^{*}$ مما يؤدي بدوره إلى التحكم الأمثل في أي وقت $t$ ، $a(t)$ خلال $a(t)={\underset {a}{\text{argmax}}}(r(t,s,a)+{\frac {\partial V^{*}(t,s)}{\partial s}}f(t,s,a)).$

التعلم المعزز

التعلم المعزز هو مجال متعدد التخصصات يجمع بين التعلم الآلي والتحكم الأمثل ، ويتمثل هدفه الرئيسي في إيجاد سياسة مثلى تقريبًا لعمليات ماركوف القرار حيث تكون احتمالات الانتقال والمكافآت غير معروفة. ^{[ 21 ]}

يمكن للتعلم المعزز حل عمليات ماركوف لاتخاذ القرار دون تحديد صريح لاحتمالات الانتقال، والتي تُعدّ ضرورية لتنفيذ تكرار السياسة. في هذا السياق، يجب تعلم احتمالات الانتقال والمكافآت من خلال التجربة، أي عن طريق السماح للوكيل بالتفاعل مع عملية ماركوف لاتخاذ القرار لعدد محدد من الخطوات. على المستويين النظري والعملي، يُبذل جهد كبير لزيادة كفاءة العينة إلى أقصى حد، أي تقليل عدد العينات اللازمة لتعلم سياسة يكون أداؤها $\varepsilon -$ قريب من الأمثل (بسبب الطبيعة العشوائية للعملية، فإن تعلم السياسة المثلى بعدد محدود من العينات أمر مستحيل بشكل عام).

التعلم المعزز لعمليات ماركوف المنفصلة

لأغراض هذا القسم، من المفيد تعريف وظيفة أخرى، والتي تتوافق مع اتخاذ الإجراء $a$ ثم الاستمرار على النحو الأمثل (أو وفقًا لأي سياسة يتبعها المرء حاليًا):

\ Q(s,a)=\sum _{s'}P_{a}(s,s')(R_{a}(s,s')+\gamma V(s')).\

على الرغم من أن هذه الوظيفة غير معروفة أيضاً، إلا أن الخبرة أثناء التعلم تعتمد على $(s,a)$ أزواج (مع النتيجة) $s'$ أي أنني كنت في الدولة $s$ وحاولت أن أفعل $a$ و $s'$ حدث ذلك). وبالتالي، يكون لدى المرء مصفوفة $Q$ ويستخدم الخبرة لتحديثها مباشرةً. وهذا ما يُعرف باسم التعلم المعزز (Q-learning) .

نطاقات أخرى

أتمتة التعلم

يُعرف تطبيق آخر لعملية ماركوف للقرار (MDP) في نظرية التعلم الآلي باسم "أتمتة التعلم". وهي أيضًا نوع من أنواع التعلم المعزز في البيئة العشوائية. أول ورقة بحثية تناولت أتمتة التعلم بالتفصيل هي تلك التي نشرها ناريندرا وثاثاشار (1974)، والتي وُصفت في الأصل صراحةً بأنها أتمتة ذات حالات محدودة . ^{[ 22 ]} وكما هو الحال في التعلم المعزز، تتميز خوارزمية أتمتة التعلم بقدرتها على حل المشكلة حتى في حال عدم معرفة الاحتمالات أو المكافآت. ويكمن الفرق بين أتمتة التعلم والتعلم Q في أن الأولى تتجاهل تخزين قيم Q، ولكنها تُحدّث احتمالية الفعل مباشرةً للوصول إلى نتيجة التعلم. وتُعد أتمتة التعلم مخططًا تعليميًا مدعومًا ببرهان دقيق للتقارب. ^{[ 23 ]}

في نظرية تعلم الأوتوماتا، تتكون الأوتوماتا العشوائية من:

مجموعة x من المدخلات الممكنة،
مجموعة Φ = { Φ ₁ , ..., Φ _s } من الحالات الداخلية المحتملة،
مجموعة α = { α ₁ , ..., α _r } من المخرجات أو الإجراءات الممكنة، حيث r ≤ s ,
متجه احتمالية الحالة الابتدائية p (0) = ≪ p ₁ (0), ..., p _s (0) ≫,
دالة قابلة للحساب A تقوم بعد كل خطوة زمنية t بتوليد p ( t +1) من p ( t )، والمدخل الحالي، والحالة الحالية، و
دالة G : Φ → α التي تولد المخرجات في كل خطوة زمنية.

تُطابق حالات هذا النوع من الآلات حالات " عملية ماركوف ذات الحالات المنفصلة والمعاملات المنفصلة ". ^{[ 24 ]} في كل خطوة زمنية t = 0,1,2,3,...، تقرأ الآلة مدخلًا من بيئتها، وتُحدِّث P( t ) إلى P( t +1) بواسطة A ، وتختار عشوائيًا حالة لاحقة وفقًا للاحتمالات P( t +1)، وتُخرج الإجراء المُناسب. بدورها، تقرأ بيئة الآلة الإجراء وتُرسل المدخل التالي إليها. ^{[ 23 ]}

التفسير النظري للفئات

وبغض النظر عن المكافآت، فإن عملية اتخاذ القرار ماركوفية $(S,A,P)$ يمكن فهم ذلك من منظور نظرية الفئات . أي، لنفترض ${\mathcal {A}}$ لنرمز إلى المونويد الحر ذي المجموعة المولدة A. ولنرمز إلى فئة كليسلي للموناد جيري بـ Dist . عندئذٍ، يكون المؤثر ${\mathcal {A}}\to \mathbf {Dist}$ يشفر كلاً من مجموعة الحالات S ودالة الاحتمال P.

وبهذه الطريقة، يمكن تعميم عمليات اتخاذ القرار ماركوف من أحاديات (فئات ذات عنصر واحد) إلى فئات عشوائية. ويمكن تسمية النتيجة $({\mathcal {C}},F:{\mathcal {C}}\to \mathbf {Dist} )$ عملية اتخاذ قرار ماركوف تعتمد على السياق ، لأن الانتقال من كائن إلى آخر في ${\mathcal {C}}$ يغير مجموعة الإجراءات المتاحة ومجموعة الحالات الممكنة.

رموز بديلة

لم يتم التوصل إلى اتفاق نهائي بشأن المصطلحات والرموز المستخدمة في عمليات ماركوف للقرار. هناك اتجاهان رئيسيان: الأول يركز على مسائل التعظيم في سياقات مثل الاقتصاد، مستخدمًا مصطلحات الفعل، والمكافأة، والقيمة، ومُسميًا عامل الخصم $β$ أو $γ$ ؛ بينما يركز الثاني على مسائل التصغير في الهندسة والملاحة ، مستخدمًا مصطلحات التحكم، والتكلفة، وتكلفة الانتقال، ومُسميًا عامل الخصم $α$ . إضافةً إلى ذلك، يختلف رمز احتمالية الانتقال.

في هذه المقالة	بديل	تعليق
الإجراء $أ$	التحكم $u$
مكافأة $R$	تكلفة $ز$	$g$ هو معكوس $R$
القيمة $V$	تكلفة الطلب الخارجي $J$	$J$ هو معكوس $V$
سياسة $π$	السياسة $μ$
عامل الخصم $γ$	عامل الخصم $α$
احتمالية الانتقال $P_{a}(s,s')$	احتمالية الانتقال $p_{ss'}(a)$

بالإضافة إلى ذلك، يُكتب احتمال الانتقال أحيانًا $\Pr(s,a,s')$ ، $\Pr(s'\mid s,a)$ أو، في حالات نادرة، $p_{s's}(a).$

انظر أيضاً

مراجع

↑ بوتيرمان، مارتن ل. (1994). عمليات اتخاذ القرار ماركوف: البرمجة الديناميكية العشوائية المنفصلة . سلسلة وايلي في الاحتمالات والإحصاء الرياضي. قسم الاحتمالات والإحصاء التطبيقي. نيويورك: وايلي. ISBN 978-0-471-61977-2.
↑ ين، بو (2021). إدارة وقت البث للشبكات اللاسلكية منخفضة زمن الوصول ذات الانتشار الكثيف (أطروحة دكتوراه). اليابان: جامعة كيوتو.
↑ شنايدر، س.؛ فاغنر، د.هـ. (26 فبراير 1957). "اكتشاف الأخطاء في الأنظمة المتكررة" . أوراق بحثية قُدِّمت في المؤتمر المشترك للحاسوب الغربي المنعقد في الفترة من 26 إلى 28 فبراير 1957: تقنيات الموثوقية - IRE-AIEE-ACM '57 (الغربي) . نيويورك، نيويورك، الولايات المتحدة الأمريكية: رابطة آلات الحوسبة. الصفحات 115-121 . doi : 10.1145/1455567.1455587 . ISBN 978-1-4503-7861-1.{{cite book}}عدم توافق رقم ISBN / التاريخ ( مساعدة )
↑ بيلمان، ريتشارد (1958-09-01). "البرمجة الديناميكية وعمليات التحكم العشوائية" . المعلومات والتحكم . 1 (3): 228-239 . Bibcode : 1958InfCo...1..228B . doi : 10.1016/S0019-9958(58)80003-0 . ISSN 0019-9958 .
1 2 ساتون، ريتشارد س.؛ بارتو، أندرو ج. (2018). التعلم المعزز: مقدمة . سلسلة الحوسبة التكيفية والتعلم الآلي ( الطبعة الثانية). كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 978-0-262-03924-6.
↑ كيرنز، مايكل؛ منصور، يشاي؛ نغ، أندرو (2002). "خوارزمية أخذ عينات متفرقة للتخطيط شبه الأمثل في عمليات اتخاذ القرار ماركوف الكبيرة" . تعلم الآلة . 49 ( 193-208 ): 193-208 . doi : 10.1023/A:1017932429737 .
^ وروبل، أ. (1984). “في نماذج القرار الماركوفية ذات الهيكل المحدود”. Zeitschrift لبحوث العمليات . 28 (1): 17-27 . دوى : 10.1007 / bf01919083 . S2CID 2545336 .
↑ التعلم المعزز: النظرية والتطبيق باستخدام لغة بايثون . بكين: دار النشر الصينية للآلات. 2019. ص 44. ISBN 9787111631774.
↑ شابلي، لويد (1953). "الألعاب العشوائية" . وقائع الأكاديمية الوطنية للعلوم في الولايات المتحدة الأمريكية . 39 (10): 1095-1100 . Bibcode : 1953PNAS...39.1095S . doi : 10.1073 / pnas.39.10.1095 . PMC 1063912. PMID 16589380 .
↑ كالينبيرغ، لودويجك (2002). "عمليات اتخاذ القرار ماركوفية ذات الحالة المحدودة والفعل". في: فينبرغ، يوجين أ .؛ شوارتز، آدم (محرران). دليل عمليات اتخاذ القرار ماركوفية: الأساليب والتطبيقات . سبرينغر. ISBN 978-0-7923-7459-6.
↑ هوارد، رونالد أ. (1960). البرمجة الديناميكية وعمليات ماركوف (ملف PDF) . مطبعة معهد ماساتشوستس للتكنولوجيا.
↑ هوارد 2002، "تعليقات على أصل وتطبيق عمليات اتخاذ القرار ماركوف"
↑ بوتيرمان، إم إل؛ شين، إم سي (1978). "خوارزميات تكرار السياسة المعدلة لمشاكل اتخاذ القرار ماركوف المخصومة". علوم الإدارة . 24 (11): 1127-1137 . doi : 10.1287/mnsc.24.11.1127 .
^ فان نونين، جاي إي (1976). “مجموعة من طرق التقريب المتعاقبة لمشاكل القرار الماركوفية المخفضة”. Zeitschrift لبحوث العمليات . 20 (5): 203-208 . دوى : 10.1007 / bf01920264 . S2CID 5167748 .
↑ باباديميتريو، كريستوس ؛ تسيتسيكليس، جون (1987). "تعقيد عمليات اتخاذ القرار ماركوف" . رياضيات بحوث العمليات . 12 (3): 441-450 . doi : 10.1287/moor.12.3.441 . hdl : 1721.1/2893 . تاريخ الاسترجاع: 2 نوفمبر 2023 .
↑ كيرنز، مايكل؛ منصور، يشاي؛ نغ، أندرو (نوفمبر 2002). "خوارزمية أخذ عينات متفرقة للتخطيط شبه الأمثل في عمليات اتخاذ القرار ماركوف الكبيرة" . تعلم الآلة . 49 (2/3): 193-208 . doi : 10.1023/A:1017932429737 .
↑ ألتمان، إيتان (1999). عمليات اتخاذ القرار ماركوف المقيدة . المجلد 7. مطبعة سي آر سي.
↑ دينغ، دونغشنغ؛ تشانغ، كايتشينغ؛ يوفانوفيتش، ميهايلو؛ باسار، تامر (2020). طريقة التدرج الطبيعي للسياسة الأولية-الثنائية لعمليات اتخاذ القرار ماركوف المقيدة . التطورات في أنظمة معالجة المعلومات العصبية.
↑ فيزابادي، س.؛ كاربين، س. (18-22 أغسطس 2014). "تخطيط المسار الواعي بالمخاطر باستخدام عمليات اتخاذ القرار ماركوفية الهرمية المقيدة" . وقائع المؤتمر الدولي لهندسة وعلوم الأتمتة (CASE) . IEEE. الصفحات 297، 303.
↑ عمليات اتخاذ القرار ماركوفية ذات الزمن المستمر . النمذجة العشوائية والاحتمالات التطبيقية. المجلد 62. 2009. doi : 10.1007/978-3-642-02547-1 . ISBN 978-3-642-02546-4.
↑ شوهام، ي.؛ باورز، ر.؛ غرينجر، ت. (2003). "التعلم المعزز متعدد العوامل: دراسة نقدية" (ملف PDF) . تقرير فني، جامعة ستانفورد : 1-13 . تاريخ الاسترجاع : 12 ديسمبر 2018 .
↑ ناريندرا، ك.س .؛ ثاتاشار، م.أ.ل. (1974). "التعلم الآلي - دراسة استقصائية". معاملات IEEE في الأنظمة والإنسان وعلم التحكم الآلي . SMC-4 (4): 323-334 . Bibcode : 1974ITSMC...4..323N . CiteSeerX 10.1.1.295.2280 . doi : 10.1109/TSMC.1974.5408453 . ISSN 0018-9472 .
1 2 ناريندرا, كومباتي إس ; ثاتشار، مندايم آل (1989). التعلم الآلي: مقدمة برنتيس هول. رقم ISBN 9780134855585.
^ ناريندرا وتاتاتشار 1974 ، ص.325 اليسار.

مصادر

Bellman, R. (1957), Dynamic Programming, Princeton University Press, ISBN 978-0-486-42809-3{{citation}}: ISBN / Date incompatibility (help). Dover paperback edition (2003)

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗