Q Öğrenme

Bahri ABACI

Bahri ABACI

Developer. Engineer.

Jan 5, 2020

İlk olarak Christopher JCH Watkins and Peter Dayan tarafından 1992 yılında literatüre kazandırılan Q Öğrenme (Q Learning) yöntemi, 2013 yılında DeepMind yapay zeka şirketinin kurucuları tarafından yayınlanan “Playing atari with deep reinforcement learning” makalesi ile oldukça popüler hale gelen bir pekiştirmeli öğrenme yöntemidir. Algoritmanın matematiksel temellerinin oluşturulduğu Pekiştirmeli Öğrenme yazımızda da bahsedildiği gibi pekiştirmeli öğrenme, K-Means, Temel Bileşen Analizi, Karar Ağaçları, Lojistik Regresyon Analizi ve Destek Vektör Makineleri gibi yöntemlerin hepsinden farklı olarak herhangi bir veriye ihtiyaç duymadan öğrenme yapabilmektedir. Yöntem verilen kurallar çerçevesinde durum uzayını (state-space) keşfederek her durum için elde edeceği ödülü en büyüklemesini sağlayan hareketi (action) öğrenmeye çalışmaktadır.

Bu yazımızda Pekiştirmeli Öğrenme yazımızda türetilen Q öğrenme yönteminin matematiksel ifadesi kullanılarak Q öğrenme algoritması incelenecek ve kodlanacaktır. Eğer pekiştirmeli öğrenme mantığı veya burada kullanılacak olan Bellman denklemi, kalite fonksiyonu gibi denklemler hakkında eksiğiniz olduğunu düşünüyorsanız öncelikle bir önceki yazıyı okumanızı tavsiye ederim.

Öğrenme işleminin matematiksel olarak nasıl yapıldığına geçmeden önce, kullanacağımız matematiksel sembolleri ve anlamlarını bir tablo şeklinde yazalım.

Sembol Açıklama
$s_t$ $t$ anındaki durum (state)
$a_t \in A$ $A$ hareketler uzayından alınan bir hareket (action)
$s^\prime_t=s_{t+1}$ $t$ anında $a$ hareketi ile geçilen yeni durum (new state)
$r_t = r(s_t, a_t, s^{\prime}_t)$ $s_t$ durumunda $a_t$ kararı ile $s^{\prime}_t$ durumuna geçilerek elde edilen ödül (reward)
$T(s, a, s^\prime) = P(s^\prime_t=s^\prime \lvert s_t=a, a_t=a)$ $s_t$ durumunda $a_t$ kararı ile $s_{t+1}$ durumuna geçme olasılığı (transition matrix)
$\pi(s, a) = P(a_t=a \lvert s_t=s)$ ajanın $s_t$ durumunda $a_t$ kararını verme olasılığı (policy)

Q Öğrenmesi

Pekişirmeli öğrenme başlığında öğrendğimiz determinisik sistemler için Bellman en iyi çözüm eşitliği aşağıda verilmiştir. İfadelerde basitlik sağlaması açısından $Q^{\pi^\ast} (s,a)$ ifadesi yerine $Q (s,a)$ tercih edilmiştir.

\[Q (s,a) = r(s, a, s^\prime) + \gamma \max_{a^\prime} Q (s^\prime, a^\prime) \tag{1}\]

Bu eşitliği çözmek için 1988 yılında Richard Sutton tarafından “Learning to Predict by the Methods of Temporal Differences” makalesi ile önerilen TD Öğrenme (Temporal Difference Learning) yöntemi kullanılacaktır. Yazarının da makalenin girişinde belirttiği gibi makalede önerilen yöntem, tahmin etmeyi öğrenme problemini çözme üzerinde kurulmuştur. Yöntem kendi yarattığı, kısmen eksik geçmiş tecrübelerini kullanarak, gelecekteki davranışları tahmin etmeyi amaçlamaktadır.

Şimdi bu yöntemin Q öğrenmesinde nasıl kullanılacağını inceleyelim. Amacımız $Q (s,a)$ fonksiyonunun değerini hesaplamak. Bu değeri ajan her $(s_t=s,a_t=a)$ durum-aksiyon kararını aldığında elde ettiği ortalama $\hat{Q}(s,a)$ olarak düşünebiliriz. Ancak ortalamanın hesaplanabilmesi için farklı $t=n, n \in N$ zamanları için $(s_n=s,a_n=a)$ olmasını beklememiz gereklidir. TD öğrenme yöntemi bu ortalama değerin süreç içerisinde gelen her yeni veri ile nasıl güncellenmesi gerektiğini göstermiştir. Sözel olarak anlattığımız algoritmanın matematiksel ispatı şu şekildedir.

Ortalama hesaplamak istediğimiz $N$ değerimiz olduğunu varsayalım. Bu durumda ortalama kalite değeri

\[\hat{Q}_N (s,a) = \frac{1}{N} \sum_{n=1}^{N} Q_n(s,a)\]

olacaktır. Denklemde $n=N-1$ için eklenen ödülü (son gelen ödül) toplam formulünün dışına alırsak

\[\hat{Q}_N (s,a) = \frac{1}{N} \left ( Q_N(s,a) + \sum_{n=1}^{N-1} Q_n(s,a) \right ) \tag{2}\]

elde edilir. Denklemde sağ taraftaki toplam formulüne dikkat edilirse bu formulün $(N-1)Q_{N-1} (s,a)$ olduğu görülür. Bu ifade açık bir şekilde Denklem $\eqref{2}$ de yerine yazılırsa

\[\hat{Q}_N (s,a) = \frac{1}{N} \left ( Q_N(s,a) + NQ_{N-1} (s,a) - Q_{N-1} (s,a) \right )\]

bulunur. Gerekli sadeleştirmeler yapıldığı takdirde

\[\hat{Q}_N (s,a) = Q_{N-1} (s,a) + \alpha(N) \left ( Q_N(s,a) - Q_{N-1} (s,a) \right ) \tag{3}\]

elde edilir. Burada $\alpha(N)=\frac{1}{N}$ seçilmesi durumunda doğrudan ortalama elde edilirken, $\alpha(N)$ öğrenme katsayısı olarak düşünülerek, süreç boyunca farklı değerlere ayarlanarak ortalamanın hesaplandığı pencere aralığı da değiştirilebiir olacaktır. Denklem $\eqref{3}$ ile verilen iteratif hesaplama yöntemi TD(0) olarak da bilinen TD($\lambda$) öğrenme algoritmalarının $\lambda=0$ için hesaplanan özel bir değeridir. Q öğrenme algoritması için TD(0) algoritması yeterli olduğundan “Learning to Predict by the Methods of Temporal Differences” makalesinde önerilen ve daha geniş bir kapsama alanı bulunan algoritmaya bu yazıda değinilmeyecektir.

Q öğrenmesi işleminin tamamlanması için Denklem $\eqref{3}$ ile verilen eşitlikte $Q_N(s,a)$ yerine Denklem $\eqref{1}$ ile verilen eşitlik yazılırsa Q öğrenmesi işlemi tamamlanmış olur.

\[\hat{Q}_N (s,a) = Q_{N-1} (s,a) + \alpha(N) \left ( r(s, a, s^\prime) + \gamma \max_{a^\prime} Q (s^\prime, a^\prime) - Q_{N-1} (s,a) \right ) \tag{4}\]

Bu işlem ajan çevreyi öğrenmeye devam ettiği sürece tekrarlanarak Q tablosunun öğrenilmesi sağlanır.

Q Öğrenmesi C Kodu

Yukarıda bahsedilen Q öğrenme algortimasının güncelleme adımı aşağıdaki C kodu ile gerçeklenmiştir. Denklemden de görüleceği üzere güncelleme adımında $(s,a,s^\prime)$ değerlerine ihtiyaç vardır. Bunlara ek olarak unutma katsayısı ve bu ödül de fonksiyona girdi olarak verilmiştir.

// compute the update for the Q table
void q_table_update(struct q_table_t *Q, uint32_t s, uint32_t a, uint32_t sp, float alpha, float reward)
{
    uint32_t a = 0;

    // find the maximum q in the next state
    float max_q = Q->qtable[sp][0];
    for(a = 1; a < Q->num_actions; a++)
    {
        max_q = max(max_q, Q->qtable[sp][a]);
    }

    // update the table
    Q->qtable[s][a] += alpha * (reward + Q->gamma * max_q - Q->qtable[s][a]);
}

Q öğrenmede durumlar arasında geçiş için kullanılan $\pi^\ast (s) = \arg\max_{a} Q^\pi (s,a)$ fonksiyonu q_table_get_action yöntemi ile gerçeklenmiştir. Verilen bir durum ve keşfetme katsayısı ile fonksiyon yeni bir yol mu deneyeceğine yoksa bildiği en iyi yoldan mı gideceğine karar verdikten sonra duruma uygun bir aksiyonu seçmektedir.

// get the action proposed by the q learning algorithm
uint32_t q_table_get_action(struct q_table_t *Q, uint32_t s, float exploration)
{
    // pick a random action
    uint32_t max_a = random_int(0, Q->num_actions - 1);

    // if in exploatation mode, find the best move
    if(random_float(0,1) > exploration)
    {
        // find the maximum q in the next state
        uint32_t a = 0;
        for (a = 0; a < Q->num_actions; a++)
        {
            if (Q->qtable[s][a] > Q->qtable[s][max_a])
            {
                max_a = a;
            }
        }
    }
    
    // return the action
    return max_a;
}

Burada kullanılan exploration katsayısı ajanın öğrenme sırasında olabildiğince fazla durumu keşfetmesini sağlamak için yapılan bir ilavedir. exploration katsayısının bire yaklaştığı durumlarda ajan, en iyi yolu izlemek yerine rastgele bir yolu seçecektir. Bu katsayı özellikle öğrenme işleminin başlarında tablonun tüm durum-aksiyon çiftlerinin güncellenebilmesi için gerekli bir değişkendir. Öğrenme safhası belirli bir noktaya gelip, $Q(s,a)$ değerleri ideal duruma yaklaştığında bu değer azaltılarak ajanın en ideal durum-aksiyon çiftlerini öğrenmesi sağlanır.

Pekiştirmeli Öğrenme ile Oyun Programlama

Şimdi basit bir oyunu pekiştirmeli öğrenme kullanarak nasıl öğrenebileceğimize bir bakalım. Aşağıdaki grafikte $5\times 7$ boyutlu bir ızagara dünyası verilmiştir.

Pekiştirmeli Öğrenme ile Oyun Programlama#half

Ajanımız amacı bu dünyadan sol,yukarı,sağ veya aşağı yönlü hareketler yaparak çıkmaya çalışmak olacak. Izgara dünyasından çıkış için kullanılabilecek toplam beş kapı bulunmakta. Ajan grafikte siyah ile gösterilen kapılardan çıkması durumunda $P=r(s \in \{ 9,11,23,25\})=-1.0$ ödülünü alırken, yeşil ile gösterilen çıkış kapısından çıkması durumunda $R=r(s \in \{ 17 \}=1.0$ ödülünü alacaktır. Ajanın ızgara dünyasından çıkışını hızlandırmak için ajanımız yaptığı her hareket sonucunda eğer siyah veya yeşil karelere gelemedi ise $T=r(s \not\in \{ 9,11,17,23,25\})=-0.1$ ceza alacaktır.

Bu şartlar altında çevreyi keşfederek her durum için alması gereken kararı öğrenen pekiştirmeli öğrenme algoritması C dilinde yazılmıştır. Yazılan kodun tamamı projenin GitHub sayfası üzerinden incelenebilir. Burada pekiştirmeli öğrenmenin en önemli kısmını içeren ve öğrenmenin yapıldığı kod parçası verilmiştir.

// play single game and return the game result
int play_game(struct q_table_t *Q, struct game_t *game, float exploration)
{
    uint32_t current_state = get_state(game);

    // play a single game untill the end
    while (!game->isEndS[current_state])
    {
        uint32_t action = q_table_get_action(Q, current_state, exploration);

        // update the target position
        update_target_position(game, action);

        // get the next state after the selected action
        uint32_t next_state = get_state(game);

        // do learning
        q_table_update(Q, current_state, action, next_state, 0.01, game->reward[next_state]);

        // goto next state
        current_state = next_state;
    }

    return game->reward[current_state] == R ? 1:0;
}

Verilen play_game fonksiyonu farklı exploration katsayıları ile 100 bin kez çağrılarak girdi olarak verilen Q tablsonun öğrenilmesi sağlanmıştır. Her bir çağrıda; ilk olarak ajanın bulunduğu durum hesaplanmış ve bu durum için en uygun hareket yukarıda gerçeklemesi verilen q_table_get_action yöntemi ile bulunmuştur. Ardından ajanın bu hareket ile gideceği yeni durum next_state hesaplanmış ve Denklem $\eqref{3}$ ile verilen matematiksel ifadenin gerçeklendiği q_table_update yöntemi ile pekiştirmeli öğrenme gerçeklenmiştir.

Bu öğrenme işlemi sonrasında ajan her durum için hangi kararın ne kadar kazançlı olduğunu gösteren Q tablosuna sahip olacaktır. Q öğrenmenin de temelinde olduğu gibi $\pi^\ast (s) = \arg\max_{a} Q^\pi (s,a)$ kuralına göre hareket eden bir ajan için hangi durumda hangi yöne gitmesini gösteren tablo aşağıdaki grafikte verilmiştir.

Pekiştirmeli Öğrenme ile Oyun Programlama#half

Grafikten de görüldüğü üzere ajan her durum için alması gereken doğru kararı başarılı bir şekilde öğrenmiştir. Serinin bir sonraki yazısında daha karmaşık bir problemin pekiştirmeli öğrenme problemine nasıl dönüştüreleceği incelenecektir.

Referanslar

  • Mnih, Volodymyr, et al. “Playing atari with deep reinforcement learning.” arXiv preprint arXiv:1312.5602 (2013).
  • Sutton, Richard S. “Learning to predict by the methods of temporal differences.” Machine learning 3.1 (1988): 9-44.
  • Watkins, Christopher JCH, and Peter Dayan. “Q-learning.” Machine learning 8.3-4 (1992): 279-292.
  • Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
« Pekiştirmeli Öğrenme Ana Sayfa Lagrange Çarpanları Yöntemi »