# Tutorial Summary
## Masalah RL
Bagaimana agent dapat menjadi profisien pada unknown environment hanya diberikan percepts dan reward (feedback yang merupakan bagian dari input percept yang dapat digunakan untuk membantu agent untuk mengetahui sesuatu itu baik atau buruk terjadi
## Perbedaan RL dengan ML paradigma yang lain
- Tidak adanya supervisor (hanya menggunakan feedback) hanya sinyal reward mengindikasikan agent itu sangat baik saat step t dan pekerjaan agent adlh untuk memaksimalkan reward kumulatif
- Feedback terdelay
- Waktu berpengaruh karena kita melihat sekuensi
- Action dari agent mempengaruhi data sebagaimana agent melihatnya
Ada variabel lain bernama history yang merupakan sekuensi observasi, action, dan reward yg setiap variabel menuju time t, dan mempengaruhi action yg dipilih oleh agent, observasi/reward yg dipilih oleh enviroment
Lalu variable state yang merupakan informasi yg digunaan untuk menentukan apa yg akan terjadi selanjutnya dan merupakan fungsi dari history, Sa merupakan state agent dan Se merupakan state environment
## Komponen utama pada agent RL
Sebuah RL agent memiliki satu atau lebih dari komponen ini yaitu:
- Policy atau pemetaan state ke action dan bisa deterministik dan stokastik
- Value function yang merupakan seberapa baik agent jika diberikan state atau seberapa baik untuk melakukan suatu action di state tsb dan merupakan prediksi dr reward masa yg akan datang dan bisa digunakan utk memilih action
- Model yang merupakan representasi dari agent dari environment yg memprediksi apa yg akan terjadi selanjutnya, state selanjutnya, dan reward langsung selanjutnya
Taksonomi agent RL:
- Value based
o Tanpa policy (implisit)
o Dengan fungsi value
- Policy based
o Dengan policy
o Tanpa fungsi value
- Actor critic
o Dengan policy
o Dengan fungsi value
- Model
o Model free
o Model based
## Q-Learning
Reinforcement Learning adalah salah satu algoritma machine learning dimana agent mengambil keputusan di environment utk memaksimalkan reward. Elemen pada RL, policy adlh bagamaina agent mengambil keputusan, reward adlh tujuan utama dari agent, value adlh jumlah reward dlm jangka panjang yg bisa didapatkan dari suatu state (long term state), model environment adlh cara prediksi reward dari state tertentu (fungsi dari state dan action yang outputnya reward). Terdapat dua approach RL, model based dan model free. Salah satu contoh model-free adlh algoritma Q-Learning. Q-Learning merupakan value dari action yang dilakukan dari state tertentu yg direpresentasikan dlm bentuk tabel dgn ukuran NxZ dimana N adlh jumlah state (contoh pada mobil: posisi) dan Z adlh jumlah action (contoh pada mobil: arah geraknya).
## Algoritma Q-Learning
1. Inisialisasi parameter α, γ, ϵ
2. Inisialisasi tabel Q(s,a) untuk setiap state dan action
3. Loop hingga mencapai jumlah iterasi yg diinginkan:

* Inisialisasi state S
* Loop hingga mencapai terminal state atau state terakhir (contoh mobil: goal/posisi terakhir):
* Pilih action A dari S menggunakan policy yang menggunakan nilai Q (e.g: epsilon-greedy)
* Melakukan A, amati reward R dan state selanjutnya S’ (pindah kemana)
Update Q(S,A) dgn persamaan Q(S,A)←Q(S,A)+α[R+γ+〖max〗_a Q(S^',a)-Q(S,A)]
* S<-S’
* Iterasi <- Iterasi + 1
## Metode
1. Salah satu metode adlh dgn memilih action dgn value terbesar dr sebuah state (greedy)
2. Greedy action adlh action yg menghasilkan immediate reward terbesar tanpa mempertimbangkan action lain yg rewardnya lebih kecil
3. Alternatifnya epsilon-greedy, epsilon adlh probabilitas action diambil secara acak (dari 0 hingga 1), yg mengambil keputusan acak dgn probabilitas epsilon dan greedy action dgn probabilitas 1-ϵ
4. Keuntungan ϵ-greedy: Q_t (a) akan konvergen ke value optimal utk jumlah sample →∞
## Perancangan sistem VLSI
Sistem terdiri dari:
1. Policy Generator (PG)
2. Q-Learning Accelerator

Agen mendapatkan state selanjutnya dan reward selanjutnya dari observer, shg action selanjutnya digenerasikan dengan PG berdasarkan nilai dari matrix Q yg disimpan ke Q-Learning accelerator
State, reward, dan action saat ini didapatkan dari mendelay state, reward, dan action selanjutnya.
PG tergantung dari aplikasi seperti contoh pada maze exploration actionnya ada kanan, kiri, atas, bawah, dan menghindari rintangan

Pada Q-Learning Accelerator terdapat dua blok:
Blok ram
Q-matrix disimpan ke Z dual-port ram yg bernama action ram setiap memori block menyimpan action
Setiap ram menyimpan satu kolom dari Q-matrix dan jumlah memory location yg bersangkutan dengan jumlah state N
Blok Q-Updater
Mengimplementasikan persamaan Q-matrix update (1) menggenerasikan Q(s,a) untuk disimpan ke action ram yg bersangkutan
Pada blok Max

Untuk memilih nilai maksimum namun delay propagasi dari blok ini menjadi limitasi utama dari kecepatan Q-Learning accelerator ketika jumlah action yg banyak dibutuhkan
Pada blok Q updater

Q(S,A)←Q(S,A)+α[R+γ+〖max〗_a Q(S^',a)-Q(S,A)]
Ini membutuhkan hanya 2 multiplier yg jika dgn pers Q(S,A)←(1-α)Q(S,A)+α[R+γ〖max〗_a Q(S^',a)] yg membutuhkan 3 multiplier
Pengoptimasian architecture lanjutan
Limitasi kecepatan utama di updater blok adlh pada propagasi delay dr multiplier dgn menggantikan full multiplier dgn multiplier aproksimasi dgn barrel shifter
Penggunaan operasi right shift dgn α dan γ
Aproksimasi dan dengan angka yang sama dgn pangkat dua terdekat (single shifter) atau dgn jumlah pangkat dua terdekat (dua atau lebih shifter)
Contoh komputasi aproksimasi
x=x_0 2^0+x_(-1) 2^(-1)+x_(-2) 2^(-2)+⋯+x_(-M) 2^(-M)
Operasi umum
<x>OP_1=2^(-i)
<x>OP_1=2^(-i)+2^(-j)
<x>OP_1=2^(-i)+2^(-j)+2^(-k)