�����w�K�̊T�v�C���p��̗��_�C�K�p��C��b���_�C��\�I��@�C���p�ɕK�v�ȋZ�p�Ȃǂ̐����B

�{�y�[�W�̋L�q�͉��L�̉���L�������Ƃ�WEB�p�ɏC���������̂ł���F
�ؑ� ���C�{�� �a���C���� �d�M�F
�����w�K�V�X�e���̐݌v�w�j�C �v���Ɛ���, Vol.38, No.10, pp.618--623 (1999), �v����������w��.
6 pages, postscript file, sice99.ps (1.31MB)
PDF file, sice99.pdf (148KB)


��P�́F �����w�K�̊T�v

1.1 �����w�K (Reinforcement Learning) �Ƃ�?
1.2 ����̎��_���猩�������w�K�̓���
1.3 ���p����҂ł��邱��

��Q�́F �����w�K�̓K�p��F���{�b�g�̕��s����l��

��R�́F �����w�K�̊�b���_

3.1 �}���R�t����ߒ�(Markov decision process: MDP)�Ƃ́H
3.2 MDP�̍œK���F������V�ɂ��]��
3.3 �}���R�t����ߒ�(MDP)�̊‹��ɂ����鋭���w�K(Q-learning)

��S�́F ���p���w���������_�ƋZ�p

4.1 �Z�~�}���R�t����ߒ�(SMDP)
4.2 �����ϑ��}���R�t����ߒ�(POMDP)
4.3 �A���ȏ�ԋ�Ԃւ̑Ή�
4.4 �A���ȍs����Ԃւ̑Ή�
4.5 �}���`�G�[�W�F���g�‹����ł̋����w�K
4.6 �����w�K�A���S���Y���̊K�w��
4.7 ���p�ɕK�v�Ȃ��̑��̋Z�p

��T�́F �����w�K�̉��p��

5.1 �Z�����[�ʐM�V�X�e���̎��g���т̓��I���肠��
5.2 �݌ɊǗ��E���Y���C���œK��
5.3 �|���U�q�̐U��グ���艻
5.4 ���̑��̉��p��

������

�Q�l����


��P�́F �����w�K�̊T�v

1.1 �����w�K (Reinforcement Learning) �Ƃ�?

�����w�K�Ƃ́C���s�����ʂ��Ċ‹��ɓK������w�K����̘g�g�ł���D ���t�t���w�K(Supervised learning)�Ƃ͈قȂ�C��ԓ��͂ɑ΂��鐳�����s�� �o�͂𖾎��I�Ɏ������t�����݂��Ȃ��D�����ɕ�V�Ƃ����X�J���[�̏��� �肪����Ɋw�K���邪�C��V�ɂ̓m�C�Y��x�ꂪ����D���̂��߁C �s�������s��������̕�V���݂邾���ł́C�w�K��̂͂��̍s������������ �����ǂ����𔻒f�ł��Ȃ��Ƃ�������𔺂��D
�����w�K�̘g�g��Fig.1�Ɏ����D

SEITAI0.gif

�w�K��́u�G�|�W�F���g�v�Ɛ���Ώہu�‹��v�͈ȉ��̂��Ƃ���s���D

  1. �G�|�W�F���g�͎���t�ɂ����Ċ‹��̏�Ԋϑ�S(t)�ɉ����� �ӎu������s���C�s��a(t)���o��
  2. �G�|�W�F���g�̍s���ɂ��C�‹���S(t+1)�֏�ԑJ�ڂ��C ���̑J�ڂɉ�������Vr(t)���G�|�W�F���g�֗^����D
  3. ����t��t+1�ɐi�߂ăX�e�b�v1�֖߂�D

�G�|�W�F���g�͗����ireturn: �ł��P���ȏꍇ�C��V�̑��v�j �̍ő剻��ړI�Ƃ��āC��Ԋϑ�����s���o�͂ւ̃}�b�s���O�i����ipolicy�j �ƌĂ΂��j���l������D
�‹��ƃG�|�W�F���g�ɂ͈�ʂɉ��L�̐������z�肳���D

1.2 ����̎��_���猩�������w�K�̓���

�����w�K�����ڂ��W�߂闝�R�̈�‚́C �s�m�����̂���‹��������Ă���_�ɂ���D �����̎����E�̐�����ł́C�s�m�����̈����͖��ł���D ������‚̗��R�́C ��V�ɒx�ꂪ���݂��C���U�I�ȏ�ԑJ�ڂ��܂񂾒i���I�� ����K���̊l�����s���_�ɂ���D �݌v�҂��S�|����Ԃŕ�V��^����Ƃ����`�ŁC ���������^�X�N���G�|�W�F���g�Ɏw�����Ă����΁C �S�|���ւ̓��B���@�̓G�|�W�F���g�̎��s����w�K�ɂ���Ď����I�� �l�������D �‚܂� �݌v�҂��u�������ׂ����v���G�|�W�F���g�ɕ�V�Ƃ����`�� �w�����Ă����΁u�ǂ̂悤�Ɏ������邩�v���G�|�W�F���g���w�K�ɂ���� �����I�Ɋl������g�g�ƂȂ��Ă���D

1.3 ���p����҂ł��邱��

1.3.1 ����v���O���~���O�̎������E�ȗ͉�

�‹��ɕs�m������v���s�\�Ȗ��m�̃p�����[�^�����݂���ƁC�^�X�N�̒B�����@ ��S�[���ւ̓��B���@�͐݌v�҂ɂƂ��Ď����ł͂Ȃ��D ����ă��{�b�g�փ^�X�N�𐋍s���邽�߂̐���K�����v���O�������邱�Ƃ͐݌v �҂ɂƂ��ďd�J���ł���D �Ƃ��낪�C �B�����ׂ��ڕW���V�ɂ���Ďw�����邱 �Ƃ͑O�L�ɔ�ׂ�Ηy���ɊȒP�ł���D ���̂��߁C�^�X�N���s�̂��߂̃v���O���~���O�������w�K�Ŏ��������邱�Ƃɂ� ��C�݌v�҂̕��S�y�������҂ł���D �\���ɗD�ꂽ���\�����‹����w�K�G�[�W�F���g���R���g���[���Ƃ��ĂP�‚����J �����Ă����΁C���Ƃ̓��{�b�g�̖ړI�ɉ����ĕ�V�̗^����������݌v�҂��ݒ� ���邾���ŁC�������ނ̃��{�b�g������@�𓯈�̃R���g���[���ɂ���Ď� ���I�Ɋl���ł���D

1.3.2 �n���h�R�[�f�B���O�����D�ꂽ��

���s�����ʂ��Ċw�K���邽�߁C �l�Ԃ̃G�L�X�p�[�g�������������D�ꂽ���𔭌�����”\��������D ���ɕs�m�����i���C��K�^�C�U���C�덷�Ȃǁj�� �v��������Ȗ��m�p�����[�^�������ꍇ�C�l�Ԃ̏펯�ł͑Ώ����؂�Ȃ����Ƃ� �\�z����C�����w�K�̌��ʂ����҂ł���D �G�L�X�p�[�g�̐���K�����w�K������Ԃɐݒ肵�āC��������P����ꍇ �ƁC�S���̃[������w�K���J�n���C�݌v�҂ɂƂ��Ă͈ӊO�ȐV�������� ��������ꍇ�Ƃ��l������D

1.3.3 �������Ƒz��O�̊‹��ω��ւ̑Ή�

�@�B�̏�Ȃǂ̋}���ȕω���v�����g�̌o�N�ω��̂悤�Ȋɖ��ȕω��ȂǁC �\�ߎ��Ԃ�z�肵�ăv���O���~���O���Ă������Ƃ�����Ȋ‹��̕ω��ɑ� ���Ă������I�ɒǏ]���邱�Ƃ����҂ł���D ���ɉF����C��ȂǁC�ʐM�������I�ɍ���ȏꍇ��C �ʐM�l�b�g���[�N�̐���̂悤�Ɍ��ۂ̃_�C�i�~�N�X���l�ԂɂƂ��đ������� �ꍇ�ɂ����āC�����w�K�̎����I�ȓK���\�͂����ɈЗ͂𔭊�����D


��Q�́F �����w�K�̓K�p��F���{�b�g�̕��s����l��

�O�͂Ő������������w�K�̗��_�ɂ‚��āC��̗�������Đ�������D
���{�b�g�̕��s����l���̃y�[�W��

��R�́F �����w�K�̊�b���_

�����w�K���_�ł́C�‹��̃_�C�i�~�N�X�� �}���R�t����ߒ�(Markov decision process: MDP)�ɂ���ă��f�������C �A���S���Y���̉�͂��s���̂���ʓI�ł���D �ȉ��C�����w�K�̊�b���_�ɂ‚��ĊȒP�ɐ�������D

3.1 �}���R�t����ߒ�(Markov decision process: MDP)�Ƃ́H

�‹��̃_�C�i�~�N�X���ȉ��̂悤�Ƀ��f���������̂�MDP�ł���D �‹��̂Ƃ肤���Ԃ̏W���� S = �o s 1 , s 2 , �c , s n �p�C �G�[�W�F���g���Ƃ肤��s���̏W���� A = �o a 1 , a 2 , �c , a l �p �ƕ\���D �‹����̂����� s �� S �ɂ����āC�G�[�W�F���g������s�� a �� ���s����ƁC�‹��͊m���I�ɏ�� s' �� S �֑J�ڂ���D ���̑J�ڊm���� Pr�o st+1 = s' | st = s, at = a �p= Pa(s,s') �ɂ��\���D ���̂Ƃ��‹�����G�[�W�F���g�֕�V r ���m���I�ɗ^�����邪�C ���̊��Ғl�� E�o rt | st = s, at = a, st+1 = s' �p= Ra(s,s') �ɂ��\���D
�G�[�W�F���g�̊e�����ɂ�����ӎu����́C ����֐���(s, a) = Pr{ at = a | st = s}, �i�������S���s,�S�s��a�ɂ����Ē�`�����j�ɂ���ĕ\�����D ����͒P�ɐ���� �Ƃ��Ă΂��D

���}���R�t���F ���s'�ւ̑J�ڂ��C ���̂Ƃ��̏��s�ƍs��a�ɂ݈̂ˑ����C ����ȑO�̏�Ԃ�s���ɂ͊֌W�Ȃ����ƁD

���G���S�|�g���F �C�ӂ̏��s����X�^�|�g���C�������Ԍo�߂�����̏�ԕ��z�m���� �ŏ��̏�ԂƂ͖��֌W�ɂȂ邱�ƁD

3.2 MDP�̍œK���F������V�ɂ��]��

���鎞�ԃX�e�b�v�Ŏ��s�����s�����C ���̌�̕�V�l���ɂǂ̒��x�v�������̂���]�����邽�߁C ���̌㓾�����V�̎��n����l����D ��V�̎��n��]���͗���(return)�ƌĂ΂��D �G�[�W�F���g�̊w�K�ڕW�́C�������ő剻���邱�ƁC ���邢�͂��̂悤�Ȑ�������߂邱�Ƃł���D �����w�K�ł́C������V���v�ɂ��]���𗘓��Ƃ��ėp����ꍇ�������D ����́C���Ԃ̌o�߂ƂƂ��ɕ�V�������� �� (0 �� �� < 1)�Ŋ������č��v����D ���鎞�� t�ɂ������ԁC���邢�͂��̂Ƃ����s�����s���̗��� V t ���ȉ��Œ�`����D
RETURN.gif
������ rt �͎��� t �ɂ������V�ł���D ���� Vt �̊��Ғl�́C1 �X�e�b�v������ ( 1 - �� ) �̊m���Œ�~����G�[�W�F ���g�ɂ���ē������V���v�̊��Ғl�Ɠ����ł���D �����̕�V�����������R�͈ȉ��ɂ��D

�}���R�t����ߒ��ɂ����ăG�|�W�F���g����퐭�� �� �i���s�ςȐ���j���Ƃ�Ƃ��C �����̊��Ғl�́C���ԂɊ֌W�Ȃ���� s �����Ɉˑ����鐫�������D �����value�͏�� s�̊֐��ɂȂ�̂�State-Value�֐��ƌĂсC V��(s) �ƕ\���D

���œK��State-Value�֐��F�S�Ă̏�� s �ɂ����� V��(s) �� V��'(s) �ƂȂ�Ƃ��C ���� �� �� ��' ���D��Ă���Ƃ����D �}���R�t����ߒ��ł́C���̂ǂ�Ȑ�������D�ꂽ�C���邢�͓����Ȑ��􂪏��Ȃ��Ƃ�1�‘��݂���D ����� �œK���� ��* �Ƃ����D �œK����͕������݂��邱�Ƃ����邪�C�S�Ă̍œK����͗B���State-Value�֐������L����D ����͍œK��State-Value�֐� V* �ƌĂ΂�C�ȉ��̂悤�ɒ�`�����D
V*(s) = max�� V��(s), for all s �� S.

���œK��Action-Value�֐��F�œK�Ȑ���͂܂��C �ȉ��Ɏ����B���Action-Value�֐������L����D
Q*(s,a) = max �� Q��(s,a) �C for all s �� S and a �� A.
Q*(s,a) ��Q�l�ƌĂ΂�C��� s �ōs�� a ��I����C�����ƍœK����� �Ƃ�‚Â���Ƃ��̗����̊��Ғl��\���D Q*(s,a) ���^����ꂽ�ꍇ�C ��� s �ɂ����čő��Q�l�����s�� a ���œK�ȍs���ł���D

3.3 �}���R�t����ߒ�(MDP)�̊‹��ɂ����鋭���w�K

�}���R�t����ߒ��̊‹����ł̋����w�K���́C�ȉ��̂悤�ɒ莮�������D Q*(s,a) ��������΁C�œK�Ȑ���͊ȒP�ɓ�����D Q-learning [Watkins92]�͊‹��Ƃ̎��s����I�ȑ��ݍ�p�̌J��Ԃ��� �ʂ��� Q*(s,a) �𐄒肷���\�I�ȋ����w�K�A���S���Y���ł���D �ȉ��ɂ��̊T�v�������D

��Q-learning�̏����葱���F S �~ A �‚̃G���g��������2�����z��ϐ�Q(s,a) ��p�ӂ��C�ȉ��̂悤�Ɋ‹��Ƃ̃C���^���N�V�����ɉ����ĕϐ����C������B QL.gif
Q-learning�̏�����}���������摜(Qlearning.jpg 88KB)
max a' Q( s',a') �́C���s'�ɂ����čő��Q�l�����s����Q�l���Ӗ�����D

�� Q-learning�̎����藝 [Watkins92]�F
�G�[�W�F���g�̍s���I���ɂ����āC�S�Ă̍s�����\���ȉ񐔑I�����C ���Šw�K������ �� t = 0 �� ��(t) �� �� ���� �� t = 0 �� ��(t) 2 < �� �𖞂������� t �̊֐��ƂȂ��Ă���Ƃ��C Q-learning�̃A���S���Y���œ���Q�l�͊m��1�ōœK��Q�l�Ɏ�������(�T����)�D �������‹��̓G���S�[�g����L���闣�U�L���}���R�t����ߒ��ł��邱�Ƃ����肷��D
���̑��C��͂ɂ‚��Ă͕��� [Bertsekas96]���Q�ƁD

�� �s���I����@(�T���헪)�F
��L�̎����藝�́C�S�Ă̍s�����\���ȉ񐔑I������������� �s���I����@(�T���헪)�ɂ͈ˑ������ɐ��藧�D ����čs���I���̓����_���ł��悢�D �������C�����w�K�ł͂܂�Q�l���������Ă��Ȃ��w�K�̓r���ɂ����Ă��Ȃ�ׂ����� �̕�V�𓾂�悤�ȍs���I�������߂��邱�Ƃ������D �w�K�ɉ����ď��X�ɋ��������P���Ă����悤�ȍs���I����@�Ƃ��āC�ȉ��̕��@����\�I�ł���D

�Ȃǂ̕��@����Ă���Ă���[Sutton98]�D

��S�́F ���p���w���������_�ƋZ�p

�O�͂�MDP�ɂ��‹����f�����Ƌ����w�K�@�́C �A���S���Y�����P���Ȋ��ɍœK���ւ̎������ۏႳ���Ƃ����Ӗ��ŋ��͂����C ���̂܂܉��p����ɂ͖�肪�����D ���p������ɂ́C�K�p������̐����ɉ����Ċ‹��̃��f������A���S���Y���� �H�v����K�v������D �ȉ��ɂ����‚����Љ��D

4.1 �Z�~�}���R�t����ߒ�(SMDP)

�l�b�g���[�N�̃��[�e�B���O��T�[�r�X�C�݌ɊǗ����ȂǁC�҂��s������� ���p���ł́C�ӎu����̎��ԊԊu�����ł͂Ȃ��C�����_���ɂȂ�D �T�b�J�[���{�b�g�̂悤�ɒn�ʂ��������郍�{�b�g�ł́C ��莞�ԊԊu�ŕp�ɂɈӎu���肷��ƁC�w�K�������ꏊ���s�����藈����� �J��Ԃ��΂���Ŋw�K���i�܂Ȃ����߁C����s����I���������Ԋϑ��� �ω����݂���܂ŐV���Ȉӎu��������Ȃ��Ȃǂ̕��@���Ƃ���[Asada97]�D �����̖��ł́C�C�x���g�h���u���Ȉӎu�����C �‚܂��ӎu����̎��ԊԊu���C�ӂȏꍇ�ɑΉ����� �����w�K�����߂���D ���̂悤�Ȋ‹��̐������f���Ƃ��ăZ�~�}���R�t����ߒ�(SMDP)������D
�ȉ���SMDP�‹��֑Ή�����Q-learning�A���S���Y���mBradtke94�n�mParr98�n�������D
SMDPQL.gif
�{�A���S���Y�����ʏ��Q-learning�A���S���Y���Ɠ��l�����_�I���������D �T���헪�����l�D

4.2 �����ϑ��}���R�t����ߒ�(POMDP)

MDP�̊‹��ł́C�G�[�W�F���g�ɂ��‹��̏�Ԋϑ��͊��S�ł��邱�Ƃ����肳 ��Ă���D �����������ł́C�m�C�Y��Z���T�̔\�͂��s�\���Ȃ��߁C��Ԋϑ��ɕs�m���� ��s���S�������݂��邱�Ƃ������D �����ϑ��}���R�t����ߒ�(POMDP)�mLovejoy91�n�́CMDP�̃��f�����g�����C �G�[�W�F���g�̏�Ԋϑ��ɕs�m������t�������������f���ł���C ��L�̂悤�Ȏ��������f�������ĉ�͂����ŗL�p�Ȓm����^����D POMDP�̊‹��ɑΉ����������w�K�@�́C�����‚��̃A�v���[�`�ɕ��ނł��� �mKimura97c�n�F

  1. �G�[�W�F���g�����ŁC�‹��̏�ԑJ�ڂ𐄒�^�\��������@(���f���x�[�X�� ��������ԕ\��)�C
  2. �L�����̉ߋ��̏�Ԃ�s���̗�����p����������ԕ\���C
  3. �m���I�Ȑ����p������@�C
�Ȃǂ���Ă���Ă���D

4.3 �A���ȏ�ԋ�Ԃւ̑Ή�

�A���ȋ�Ԃɂ����鋭���w�K�̐����pOHP����

�����ł̓R���g���[���̏�ԓ��͂��A���l�̃x�N�g���ŗ^������ꍇ������ ���Ȃ��D�ʏ��Q-learning�A���S���Y���̌`���ɍ��킹�āC�A���l�̏�ԓ��� ��K�X���U������̂����ʂ����C��ԓ��̓x�N�g���̎��������傫���Ɓu������ ��(Curse of dimensionality)�v�ƌĂ΂���ԋ�Ԃ̔����������D

�A���ȏ�ԋ�Ԃł́C�e��ԊԂɈʑ��\��(�‚܂��ԊԂ̋������`�ł���) �����D�����I�ɋ߂���Ԃł�Q�l���߂��l�������C�Q�‚̏�Ԃ̒��Ԃ������ ���݂����Ԃ�Q�l�͂����Q�‚�Q�l�̒��Ԃ��炢�̒l�����‚��Ƃ������D �����ŁC�A���ȏ�ԋ�Ԃ����‹����w�K���ł́C Q-learning�ɂ�����Q�l��Value�̕\���Ɋ֐��ߎ���p���邱�Ƃ������D �֐��ߎ���p����ƁC�w�K�������ɂȂ�����C ���܂Ōo���������Ƃ̂Ȃ���Ԃɑ������Ă��C������Ԃł̌o���𐶂����� �K�؂ȍs���I�����ł���Ȃǂ̃����b�g������D ��\�I�Ȋ֐��ߎ��@�Ƃ��āCtile coding(CMAC)�C�j���[�����l�b�g�C�t�@�W�B�C ���֐����Œ肵��radial-basis-function network�Cnearest neighbor�C locally weighted linear regression�Ȃǂ���Ă���Ă���mSutton98�n�D ��L�̊֐��ߎ��͑��w�j���[�����l�b�g�������Đ��`�A�[�L�e�N�`���ƌĂ΂��D ����́C�����ԓ��� s ���^����ꂽ�Ƃ��CValue���ߎ����邽�߂ɂ܂� s �� K ���������x�N�g�� ��(s) �� RK�Ƀ}�b�s���O���C ���� K �����̃p�����[�^�x�N�g�� W �Ƃ̐��`�a�ɂ�� V(s) = ��(s) �E W �̂悤�ɕ\�����̂ł���(Q�l�����l)�D ���`�A�[�L�e�N�`����p�����ꍇ�C����������ōœK�l�ւ̎������ۏ� �����mTsitsiklis97�n�D

���̑��C��ԋ�Ԃ�K���I�ɕ������Ă������@�mAsada97�n�mMoore95�n �Ȃǂ���Ă���Ă���D

4.4 �A���ȍs����Ԃւ̑Ή�

�A���ȋ�Ԃɂ����鋭���w�K�̐����pOHP����

�����ł͘A���l�̏�ԓ��͂Ɠ��l�C�A���l�̍s���o�͂����߂��邱�Ƃ������D �s����Ԃ𗣎U������̂����ʂ����C���܂�e�����U������ƍׂ₩�Ȑ��䂪�� ���Ȃ��Ƃ�����肪������D���Ƃ����ė��U�����ׂ�������ƒT����Ԃ����債�C �ʏ�̗��UMDP�ɂ�����Q-learning�Ƃ��̍s���I����@�ł́C �Ȃ��Ȃ��w�K���i�܂Ȃ��Ȃ����p�I�ƂȂ�D

�������̘A�����-�s����Ԃɂ�����Q-learning���s�����߂̎������@�̈�‚Ƃ��āA �M�҂́u�����_���^�C�����O��Gibbs�T���v�����O��p���������w�K�v���Ă��C �������{�b�g�V�~�����[�^��Rod-In-Maze���CMulti-Joint Arm���֓K�p�����i2005.12.06�X�V�j�D �����_���^�C�����O�͐��`�A�[�L�e�N�`���̂P�‚ł��邪�C �O���b�h�^�C�����O��b�l�`�b�̂悤�ɋK���I�Ƀ^�C������ׂ�̂ł͂Ȃ��C ��Ԓ��Ƀ����_���Ƀ^�C����z�u������@�ł���D �s�v�c�Ȃ��ƂɁC�����̃^�C�����O���b�h��ɋK���������z�u��������A �����_���ɔz�u�����ق����y���ɗǂ��w�K���ʂƂȂ�B Gibbs�T���v�����O�Ƃ́C�������̍s����Ԃɂ�����Q-learning�̍s���I���̂��߂� �c���Q�l�̏W�v���s���đI���m�����s��Ȃ���΂Ȃ�Ȃ��������C �ߎ��v�Z�ɂ���Čy�����邽�߂ɗ��p�����m���T���v�����O�@�ł���D Gibbs�T���v�����O���̂́C �������m����ԂŌ����ǂ��T���v���𓾂邽�߂̈�ʓI���@�ł���D �����ł́C�v�Z�R�X�g��1������1���x�Ɍy���ł����D �ȉ��ɕ����������̂ŎQ�l�ɂ��ꂽ���D

  1. �ؑ� ���F
    �����_���^�C�����O��p�������������-�s���̋����w�K
    �v����������w�� �V�X�e���E��񕔖�w�p�u����2005�u���_���W, pp.37--42 (2005).
    �\�e�W���e 6 pages, PDF file, ssi2005_u.pdf (255KB)
    �u���Ɏg�p����PowerPoint������PDF�t�@�C��, SSI2005_1128ppt.pdf (576KB)
  2. �ؑ� ���F
    �����w�K�ɂ����鍂�������̍s����Ԃ̈����ɂ‚��� �|�n�b�V����Gibbs-Sampling��p�����s���I����@�̒��-�C
    �v����������w�� ��32��m�\�V�X�e���V���|�W�E��, pp.399--404 (2005).
    6 pages, PDF file, sice20050137.pdf (302KB)
  3. ���{�b�g���w�n���h�u�b�N�@��7.4�߁u�����w�K�v
    ������Ѓi�m�I�v�g�j�N�X�E�G�i�W�[ �o�ŋ� (2010)
    PDF file, Chapter7.pdf (343KB)

Fuzzy���}�^Q-learning�mHoriuchi99�n�́C �t�@�W�B��p�����֐��ߎ��ɂ���ĘA���l�̍s���Ɋւ���Q�l��\�����C �s���I�����ɂ́C�s����Ԃ𓙊Ԋu�ɋ�؂��������‚��̓_�ɂ‚���Q�l�� �v�Z����D�����̗��U�I�ȃ|�C���g�ɂ�����Q�l��p���čs�������肷�邪�C �A���I�Ȓl�̍s����I�Ԃ悤�Ȋg�����[���b�g�I�����Ă��Ă���D

�s����Ԃ��A���I�ȏꍇ�́CQ-learning���� actor-critic �mSutton98�n�mKimura98�n�� �Ă΂����@�̂ق������т�����D ����͏�Ԃ�Value��]������critic�ƌĂ΂�镔���ƁC��Ԋϑ��ɉ����� �m���I�ɍs���I�����s��actor�Ƃ����Q�‚̗v�f���\�������D ������actor�͍s���I���̊m���𒲐��ł��镨�ł���΂悢�D�A���l�̍s�� �ł���΁Cactor�̊m���I����́C��ԓ��͂ɉ����Ē��S�l�ƕ��U���ω��� �鐳�K���z�Ƃ�����@������D�ȉ��Ɏ����Ƃ���C �s����I���������ʁC�悢��Ԃ֑J�ڂ����Ȃ�I�������s������������D ���K���z��actor�̏ꍇ�ɂ����čs������������ɂ́C ���s�����s���֕��z�̒��S�l���ߕt���C���s�����s�����W���΍��̓����Ȃ�C ���K���z�̍L��������߁C�O���Ȃ�L����悤���߂���΂悢�̂ŁC �����͋ɂ߂ĊȒP�ł���D
AHC.gif
Actor-Critic�̏�����}���������摜(ActorCritic.jpg 71KB)
Critic�̏���(TD�@)��}�������������iPowerPoint2000�ɂč쐬�j
�E Critic�̏���(TD�@)��}���������摜(TD_method.jpg 75KB)
�E TD�@��value���w�K���Ă����l�q��}���������摜(TDExample.jpg 71KB)

4.5 �}���`�G�[�W�F���g�‹����ł̋����w�K

���x�ɕ��G�C���剻�����V�X�e���ł́C ������x�̋@�\�P�ʂ��ƂɎ����I�Ȓm�I���f�����������C �������݂��ɋ��������鎩�����U�V�X�e���ɂ��Ǘ������߂��Ă���D ����͈ȉ���2�‚̗��R������D

�]���̕��UAI�̘g�g�ł́C�X�̃G�[�W�F���g�̐���K���̊l���ɂ‚��Ă� �G�L�X�p�[�g�̒m����p����ȊO�ɕ��@�_�����������D �����̉�����Ƃ��āC�}���`�G�[�W�F���g�‹����ł̋����w�K�����ڂ���Ă� ��mMikami97�n�D �}���R�t�Q�[���Ƃ����������f����p���āC�~�j�}�b�N�X�_�mLittman94�n�� �i�b�V���ύt�mHu98�n���w�K����}���`�G�[�W�F���g�����w�K�V�X�e���̉� �͂��s�������������邪�C�����̏ꍇ�C���_�I��͂�œK������������ ������D �����ŁC�œK���Ƃ����v�����ɘa���C���̍�������ۏ؂���Ƃ����A�v���[�`�� �}���`�G�[�W�F���g�n�̋����w�K�ɓK�����A���S���Y���Ɖ�͂������������� ����mTeru99�n�D

4.6 �����w�K�A���S���Y���̊K�w��

�K�w�I�����w�K(Hierarchical RL)�́C��K�͂Ȗ��𕪊����ĉ����Ƃ����Ӗ� �ɂ����ă}���`�G�[�W�F���g�Ɨގ����Ă���C �l�X�ȕ��@����Ă���Ă���mParr98�n�mSchneider99�n�mWang99�n�D �}���`�G�[�W�F���g�ƈقȂ�̂́C��ʊK�w�����ʊK�w(�T�u�^�X�N)�̒m���� �ė��p�܂��͋��L����_�ƁC ���ʊK�w�ł̕����ϑ�������ʊK�w�ŃJ�o�[�ł���_�ł���D

4.7 ���p�ɕK�v�Ȃ��̑��̋Z�p

�摜���͂Ȃǖc��ȃZ���T����̏�񂩂�ǂ̂悤�ɂ��ď�ԕ\���𐶐����邩 �ɂ‚��ẮC�����w�K�Ɍ��炸AI�ɂ������{�I�ȉۑ�ł���mAsada97�n�D �܂��C�l�X�ȃ^�X�N�������ǂ��w�K���邽�߂ɂ́C�‹��̏�ԑJ�ڂɊւ���m�� ��~���ă^�X�N���ɋ��L�^�ė��p���邱�Ƃ����ʓI�ƍl������D ����̓��f���x�[�X��@�ƌĂ΂�C �����̎�@����������Ă���mKaelbling96�n�mSutton98�n�D ���̑��C��V�̊��Ғl�ő剻�����ł͂Ȃ����X�N�ŏ����╡���]���K�͂Ȃǂ� ��������Ă���D


��T�́F �����w�K�̉��p��

�ȉ����p����Љ�C�O�ɏЉ�����_�Ƃ̊֌W�������D

5.1 �Z�����[�ʐM�V�X�e���̎��g���т̓��I���肠��

������PHS�̂悤�ȒʐM�V�X�e���ł́C �T�[�r�X�n����Z���ƌĂ΂��n��ɕ������C�e�Z�����ł͊e�ʘb�҂� ���ꂼ��قȂ���g���т��g�����C�ߐڂ���Z���ł͓���̎��g���т� �g���Ȃ��Ƃ������񂪂���D����ꂽ�`�����l���ʼn”\�Ȓʘb�����ő�ƂȂ� �悤�Ɏ��g���������Ă邱�Ƃ��v�������D �ʘb�T�[�r�X�v����ؒf�̔����͊m���I�ŁC�����̕p�x�̓Z�����ɈقȂ��C ���I�ɕϓ����邽�߁C��K�͂ɂȂ�Ɩ�肪�ɂ߂ĕ��G�ɂȂ�D Singh��́CSMDP�̋����w�K�Ɋ�Â����@���Ă��C�w�K���Ԃ����قǂ����邱 �ƂȂ������̃q���[���X�e�B�N�X�����鐫�\��B������[Singh97]�D

5.2 �݌ɊǗ��E���Y���C���œK��

Fig7�Ɏ����悤�ɁC�����̉��H�@�B�𒼗�ɘA�����č\�����ꂽ ���Y���C���ɂ����āC�݌ɂ��ŏ������‚��i�̎��v�𖞂����悤�ȍœK�Ȑ��� ���w�K������ł���D
TLINE.gif
�e�@�B�̉����ɂ͑q��(buffer)���ݒu����C�@�B�̌̏ᒆ���邢�̓����e�i���X ���̐��i���v�ɑΉ����邱�ƂőS�̗̂���ɗ^����e�������Ȃ�����D �e�@�B�͉^�p���Ԃ̑����ƂƂ��Ɍ̏Ⴊ�������₷���Ȃ�C �̏Ⴗ��ƏC�����K�v�ł���D�R�X�g�̂�����C����������C �݌ɕs���ɂ�郉�C����~������C���݌ɂ��R�X�g��������̂łȂ�ׂ��ŏ� ���̍݌ɂƂȂ�悤�ɁC�^�p���Ԃ�݌ɂ̗ʂɉ����� �@�B�̉ғ��^�A�C�h�����O�^�����e�i���X�̃^�C�~���O�𐧌䂵�Ȃ���΂Ȃ�Ȃ��D ���̖���SMDP�Ƃ��ă��f�����ł��邪�C���C���S�̂�P��̃G�[�W�F���g�� �w�K����Ɩ��̃T�C�Y���������邽�߁C�e�@�B���ɃG�[�W�F���g�����蓖�Ă� �}���`�G�[�W�F���g�V�X�e�����p�����Ă���[Wang99]�D �g���^�̃J���o���������Ɣ�r���C�D�ꂽ����K�����l�������Ƃ̕񍐂�����D ����͋����w�K����ԑJ�ڂɕs�m�������܂݁C�S�̂̐��\���ő剻������ɂ����� ���͂Ȏ�@�ł��邱�Ƃ������Ă���

5.3 �|���U�q�̐U��グ���艻

swing3355a3.gif
Fig.8: �|���U�q�̐U��グ���艻�̓����
�K�w����actor-critic�Ɋ�Â��A���l�s����g�ݍ��킹�邱�ƂŁC Fig8�Ɏ����|���U�q�̐U��グ���艻���[������w�K���� �Ⴊ�񍐂���Ă���[Kimura99c]�D ����̏����l�����t���^���C�����w�K�ɂ���Đ���̉��P���s�����Ƃɂ�� ���₩�Ɋw�K������@����Ă���Ă���[Doya96]�D

5.4 ���̑��̉��p��

�G���x�[�^�Q����CJob-Shop�X�P�W���[�����O�C �o�b�N�M��������`�F�X�Ȃǂ̃Q�[���ւ̓K�p�Ⴊ����[Sutton98]�D �ߔN�ł͓d�͖Ԃ̕��U�w�K����[Schneider99]�� �C���^�[�l�b�g�o�i�[�̃X�P�W���[�����O�ւ̓K�p[Abe99]���񍐂���Ă� ��D


������

�{�e�ł͋����w�K�������̖��֓K�p���邱�Ƃɏd�_��u���C ���ɍ��킹���A���S���Y���ɂ‚��ďЉ���D �������C�����ł͋����w�K�ŕK�v�ȁu���s����v��������Ȃ��ꍇ�������C ���{�b�g�̊w�K�ł͖����ȓ�����l������O�ɉ��Ă��܂��Ȃǖ��������D ���̂��߁C�����w�K�̉��p�ɑ΂��Ĕᔻ�I�Ȉӌ������邱�Ƃ������ł��邪�C ���t�t���w�K�Ƃ̑g�ݍ��킹�Ȃǂɂ���ĉ�������Ă������̂Ɗ��҂����D ����ɍ���C �����w�K�̎g�p��O��Ƃ����n�[�h�E�G�A�݌v���Ȃ����΁C �\�t�g�ƃn�[�h����̂ƂȂ����A�[�L�e�N�`���ɂ��C �����w�K�̃|�e���V�������\���ɐ������� ���܂łɂȂ��V�������i��T�[�r�X���o������”\��������D


�Q�l����

(�ȉ��C�܂��H����)

�����w�K�̗�

�����‚��̗�� �iJava�A�v���b�g�j
�����w�K�������{�b�g�֓K�p

���\�_���ꗗ


�ؑ� ���̃z�[���y�[�W��