בעיית הידיות הגונבות: מה אם היינו מיישמים למידת מכונה בקזינו?

מה אם היינו מיישמים עקרונות למידת מכונה (ML) בקזינו ובוחרים כך באיזו מכונת מזל לשחק?

מקור: Pixabay

מאת תמיר נווה, The AI Blog

אחת מנגזרות מהפכת הלמידה העמוקה היותר מעניינות התרחשה – ועדיין מתרחשת – בתחום ה-Reinforcement Learning או הלמידה החיזוקית. הניצחון של האלגוריתם של DeepMind על אלוף העולם הסיני ב-GO ב-2016, והאלגוריתמים שלומדים לשחק משחקי אטארי ישנים מתוך תמונה שרואים על המסך – ללא הכנסת מודל כלשהוא אלא רק ע”י ניסוי וטעייה במשחק.


בעולם ה-Reinforcement Learning אנחנו מוצאים סוכן (Agent) שחי בסביבה כלשהיא Environment ויש לו אוסף כלשהוא של פעולות (Actions) שהוא יכול לעשות בה. הסוכן מקבל תגמול Reward מהסביבה בהתאם לפעולותיו, ובכל רגע נתון הסוכן נמצא במצב (State) כלשהו. מצב זה הוא כל האינפורמציה הידועה לסוכן, שמקבל את ההחלטות בכל רגע.

סצנריו זה מתאים לתוכנה שמשחקת משחקי מחשב, או לרובוט שיש לו משימה כלשהיא בעולם הפיסי או לרכב אוטונומי ועוד.

בכתבה זו אסקור בעיה בסיסית ופשוטה Multi-Armed bandit עם state בודד ומספר קטן של אפשרויות פעולה action בכל תור (כמספר הידיות).

איך להרוויח הכי מהר בקזינו?

תארו לעצמכם קזינו שבו מכונות המזל עקביות בהתנהגותן הסטטיסטית אך אינן זהות זו לזו. במילים אחרות יש הרבה מכונות מזל (ידיות) שלכל אחת יש את המזל או הנאחס הקבוע שלה. כלומר, יש אחת שבממוצע תוציא לכם 10 דולר וכאלו שיוציאו בממוצע דולר בודד. כשאני כותב בממוצע אני מתכוון לכך שהמכונה תוציא בכל פעם סכום אחר, אך לאחר הרבה משחקים תשאף לערך ממוצע אחד. כמובן שלכל משחק גם יש עלות, נניח 5 דולר, כך שההשקעה תחזור – אם בכלל – רק אחרי הרבה משחקים, וכדי לבחור באילו מכונות לשחק ובאילו לא.

אז אם אתה כבר יודע מהן המכונות שמוציאות בממוצע הרבה, תוכל לשחק רק בהן, אבל בהתחלה אינך יודע כלום, מה גם שאפילו ומצאת מכונה כזו טובה, תמיד יחלפו במוחך המחשבות שיש אפשרות שיש מכונות אפילו יותר מוצלחות איתן תוכל להרוויח יותר כסף ויותר מהר.

בבעיית הידיות (הקזינו) יש מצב state יחיד כי בכל רגע נתון הסוכן יודע שיש את אותן האפשרויות לפעול ואין לו מידע חדש מהסביבה (לא כולל מידע שהוא צבר מניסיונותיו). בעיות עם ריבוי מצבים הינן למשל לשחק ב-GO או רובוט שלומד לפתוח דלת על בסיס מה שרואה (כלומר, מה שמתקבל ממצלמה שמותקנת עליו). בסיטואציות אלו יש המון states כי האינפורמציה מהסביבה כל רגע או תור משתנה.

בעיית הפשרה בין מחקר ופיתוח

אז במה להשקיע את ניסיונות המשחק שלך, שעולים 5 דולר כל אחד? בלשחק במכונה מוכרת או בלחקור ולהכיר עוד מכונות? – דילמת ה–exploration\exploitation. או אפילו בלהכיר יותר טוב מכונה שכבר קצת הכרנו, כי למשל אם שיחקנו במכונה ועד עתה אלו היו הזכיות שלנו: 2,5,3 אז הממוצע בינתיים הינו 3.333, ואם נשחק במכונה זו עוד הממוצע כנראה ישתנה, וככל שנשחק במכונה יותר כך “נאמין” לממוצע שיוצא לנו יותר (כי הרי אמרנו שהמכונות מכווננות על ממוצע מסוים).

הפתרון

אחד הפתרונות לבעיה זו נקרא ε-greedy (אפסילון התאב בצע J) שזה אומר, קבע ערך כלשהוא בין 0 ל-1 (אפסילון) ואז בכל פעם הגרל ערך אקראי בין אפס לאחד. אם גדול מאותו קבוע אפסילון – אז שחק במכונה אקראית כלשהיא. אחרת, שחק במכונה שעד עכשיו הממוצע שלה הכי טוב. בדרך זו מצד אחד תרוויח, כי לעיתים תשחק במכונה הכי רווחית למיטב ידיעותיך באותו הרגע, ומצד שני תרחיב את הידע שלך, כי לעיתים תנסה מכונות אחרות.

בשיטה זו הרווחים יגדלו כי ההכרות שלך עם הקזינו תגבר ותדע איפה יותר כדאי לשחק, אך בשלב מסויים הרווחים יגדלו פחות ואף יישארו קבועים כיוון שמיצית את ההכרות עם הקזינו, כלומר מצאת את המכונה הכי ריווחית ולכן המחקר שלך כבר לא מניב הגדלת רווחים יותר.

ראו את גרף הרווחים כתלות בכמות משחקים:

גם אם במשחקים הראשונים חשבנו שמכונה מסוימת היא הכי ריווחית והיא לא, כי כאמור הממוצע האמיתי מתגלה לאחר הרבה משחקים, וכל משחק בודד יכול להניב רווח כלשהוא שרחוק מהממוצע, אז זה די מהר יתוקן. כי לאחר עוד כמה משחקים במכונה שנראית הכי ריווחת נגלה שהיא לא כזו רווחית כפי שחשבנו בהתחלה ומכונה אחרת תוכתר להיות הכי ריווחית.

פתרון כללי יותר לבעיה נקרא Softmax Action Selection אשר לפיו בחירת הפעולה בכל רגע גם תוגרל אך לא רק בין שתי אפשרויות כמקודם – בין המכונה הכי ריווחית עד כה או מכונה כלשהיא אקראית. אלא תוגרל מבין כל האפשרויות, כל המכונות, אך לפי התפלגות שנלמדה עד עתה. במילים אחרות, נגריל מכונה לפי מידת הידע שלנו על הריווחיות שלה. ככה, עדיין המכונה הכי טובה, לפי הידע של אותו הרגע, תיבחר הכי הרבה, אך גם המכונה השניה הכי טובה, לפי הידע של אותו הרגע, תיבחר השנייה הכי הרבה. מכונות שאין לנו עליהן מידע כלל ייבחרו הכי פחות. בשיטה זו פחות נפסיד בהתחלה ויותר נמצה את הידע שלנו בסוף.

פורסם במקור ב-AI Blog

כתב אורח

אנחנו מארחים מפעם לפעם כותבים טכנולוגים אורחים, המפרסמים כתבות בתחומי התמחות שלהם. במידה ואתם מעוניינים לפרסם פוסט בשמכם, פנו אלינו באמצעות טופס יצירת קשר באתר.

הגב

5 תגובות על "בעיית הידיות הגונבות: מה אם היינו מיישמים למידת מכונה בקזינו?"

avatar
Photo and Image Files
 
 
 
Audio and Video Files
 
 
 
Other File Types
 
 
 

* היי, אנחנו אוהבים תגובות!
תיקונים, תגובות קוטלות וכמובן תגובות מפרגנות - בכיף.
חופש הביטוי הוא ערך עליון, אבל לא נוכל להשלים עם תגובות שכוללות הסתה, הוצאת דיבה, תגובות שכוללות מידע המפר את תנאי השימוש של Geektime, תגובות שחורגות מהטעם הטוב ותגובות שהן בניגוד לדין. תגובות כאלו יימחקו מייד.

סידור לפי:   חדש | ישן | הכי מדורגים
אסף.פ
Guest

מעניין ופותח את הראש.
רק עשו טובה וטל תשימו גיפים באמצע כתבות, יש פה גיקים עם בעיות קשב וריכוז :)

ססס
Guest

וואו הגיף הזה נוראי תעיפו אותו.

deep-troll
Guest

איזה חפירה – תגיד softmmax וזהו…

mishu
Guest

הגיף הזה אונס את העין.
צריך לתלות את מי ששם אותו….

dan
Guest

גמר לי על העיניים נגיף הזה

wpDiscuz

תגיות לכתבה: