Mengapa tabel gagal

Pada permainan papan dan FrozenLake, agen dapat menyimpan satu nilai Q per state karena jumlah state terbatas dan dapat dihitung. Pada lingkungan dengan observasi kontinu seperti CartPole, ruang state menjadi tak hingga sehingga representasi tabular kehilangan makna. Topik ini menghitung berapa banyak state diskret yang muncul bila observasi CartPole dibagi menjadi sepuluh tingkat per dimensi, lalu membandingkannya dengan ruang pixel Atari untuk menunjukkan mengapa pendekatan tabular gagal pada masalah dengan state nyata.

Ruang state CartPole adalah kontinu#

Lingkungan CartPole-v1 mengembalikan observasi berupa vektor empat angka real, yaitu posisi gerobak, kecepatan gerobak, sudut tiang, dan kecepatan sudut tiang. Empat angka ini bukan label diskret, melainkan nilai kontinu yang dapat mengambil berapa pun nilai di dalam rentang yang ditetapkan oleh Gymnasium. Karena setiap dimensi bernilai real, kombinasi keempatnya membentuk himpunan tak hingga, sehingga tidak ada tabel yang mampu menyimpan satu entri Q per state. Blok berikut memeriksa bentuk dan batas ruang observasi CartPole.

import warnings; warnings.filterwarnings("ignore")
import numpy as np, torch
np.random.seed(0); torch.manual_seed(0)
import random; random.seed(0)
import gymnasium as gym

env = gym.make("CartPole-v1")
obs, info = env.reset(seed=0)
env.action_space.seed(0)
env.observation_space.seed(0)

print("obs              =", obs)
print("obs_shape         =", env.observation_space.shape)
print("obs_low           =", env.observation_space.low)
print("obs_high          =", env.observation_space.high)
print("action_space      =", env.action_space)

obs              = [ 0.01369617 -0.02302133 -0.04590265 -0.04834723]
obs_shape         = (4,)
obs_low           = [-4.8               -inf -0.41887903        -inf]
obs_high          = [4.8               inf 0.41887903        inf]
action_space      = Discrete(2)

Keluaran menunjukkan bahwa obs_space berbentuk Box dengan empat dimensi, dan dua di antaranya memiliki batas tak hingga pada kecepatan. Hal ini menyiratkan bahwa agen tidak hanya menghadapi state kontinu, tetapi juga tak terbatas, sehingga menyimpan nilai Q per state yang dikunjungi saja sudah tidak praktis. Aksi tetap diskret, yaitu dua pilihan mendorong ke kiri atau ke kanan, sehingga agen tetap dapat memilih, tetapi cara menyimpan pengetahuannya harus berubah.

Kutukan dimensionalitas#

Satu jalan keluar yang naif adalah membagi setiap dimensi menjadi sejumlah tingkat (bin), lalu memperlakukan kombinasi bin sebagai state diskret. Bila tiap dimensi CartPole dibagi menjadi sepuluh bin, jumlah state diskret menjadi $10^4 = 10000$, yang masih dapat ditampung tabel. Namun, jumlah state tumbuh secara eksponensial terhadap jumlah dimensi, sebuah fenomena yang disebut curse of dimensionality, yaitu kutukan dimensionalitas. Setiap dimensi baru melipatgandakan ukuran tabel, sehingga memori dan data yang dibutuhkan meledak sebelum agen sempat mengunjungi sebagian besar state. Blok berikut menghitung perbandingan jumlah state antara CartPole yang dibagi menjadi bin dengan ruang pixel Atari.

bins_per_dim = 10
state_count_cartpole = bins_per_dim ** 4
print("bins_per_dim      =", bins_per_dim)
print("state_cartpole    =", state_count_cartpole)

atari_height, atari_width, atari_channels = 210, 160, 3
state_count_atari_raw = atari_height * atari_width * atari_channels
print("state_atari_raw   =", state_count_atari_raw)

ratio_cartpole_to_atari = state_count_atari_raw / state_count_cartpole
print("ratio_atari_cart  =", f"{ratio_cartpole_to_atari:.0f}")

ratio_cartpole_to_1 = state_count_cartpole / 1
print("ratio_cart_to_1   =", f"{ratio_cartpole_to_1:.0f}")

bins_per_dim      = 10
state_cartpole    = 10000
state_atari_raw   = 100800
ratio_atari_cart  = 10
ratio_cart_to_1   = 10000

CartPole dengan sepuluh bin per dimensi menghasilkan 10000 state, sedangkan satu bingkai pixel Atari berukuran 210x160x3 sudah memiliki 100800 nilai pixel, atau sepuluh kali lipat dari itu. Angka 100800 baru menghitung jumlah pixel, bukan jumlah state diskret, karena setiap pixel masih dapat bernilai berapa pun dari 256 tingkat. Bila setiap pixel diperlakukan sebagai dimensi diskret dengan 256 tingkat, jumlah state menjadi $256^{100800}$, yang tidak dapat ditulis sebagai bilangan biasa. Tabel yang menyimpan satu entri per state dengan demikian mustahil dibangun, dan agen tidak akan pernah mengunjungi sebagian besar state lebih dari satu kali.

Permasalahan tidak berhenti pada ukuran. Pada tabel, nilai Q untuk satu state hanya diperbarui ketika state itu dikunjungi, sehingga pengetahuan tidak menyebar ke state lain yang serupa. Dua state CartPole yang beda sedikit pada kecepatan diperlakukan sebagai entri terpisah yang tidak saling terkait, padahal keduanya hampir pasti membutuhkan aksi yang sama. Akibatnya, agen harus belajar dari nol untuk setiap state, dan generalisasi yang seharusnya murah menjadi mahal. Karena itulah representasi tabular ditinggalkan begitu state menjadi kontinu atau berdimensi tinggi.

Kesalahan umum#

• Mengangkat binning sebagai solusi tanpa mempertimbangkan ledakan kombinasi. Penyebabnya, sepuluh bin pada empat dimensi tampak kecil, tetapi pada delapan dimensi menjadi $10^8$. Perbaikannya, mengganti tabel dengan function approximation yang berbagi parameter lintas state, sehingga pertumbuhan memori mengikuti kompleksitas model, bukan ukuran ruang state.
• Membuang dimensi kecepatan agar tabel mengecil. Penyebabnya, kecepatan gerobak dan sudut tiang menentukan nasib episode. Perbaikannya, mempertahankan seluruh observasi dan membiarkan jaringan mempelajari representasi yang relevan dari data.

Ringkasan#

• CartPole mengembalikan observasi kontinu Box(4,) dengan dua dimensi tak terbatas, sehingga state yang mungkin jumlahnya tak hingga.
• Membagi setiap dimensi menjadi sepuluh bin menghasilkan 10000 state diskret, tetapi jumlahnya tumbuh eksponensial terhadap dimensi, yang disebut curse of dimensionality.
• Satu bingkai pixel Atari berisi 100800 nilai, dan jika setiap pixel didiskretkan menjadi 256 tingkat, ruang state menjadi $256^{100800}$, yang mustahil ditampung tabel.

Referensi#

• Reinforcement Learning: An Introduction (2nd ed.) — Sutton & Barto — Bab 9 membahas curse of dimensionality sebagai alasan utama beralih dari tabel menuju function approximation.