Algoritmos para controle de aprendizagem
Contenido
Aunque el tema de la exploración se tiene en cuenta, e incluso si el estado era observable (que asumimos a partir de ahora), el problema sigue siendo saber qué acciones son buenas basadas en la experiencia pasada.
Critério de otimalidade
Para simplificar, vamos supor por um momento que o problema estudado seja episódico, um episódio que termina quando um estado terminal é alcançado. Suponha ainda que, independentemente do curso de ação do agente, a rescisão seja inevitável. Sob certas condições de regularidade adicional, a expectativa da recompensa total para qualquer política e qualquer distribuição inicial entre os estados fica então bem definida. Neste sentido, uma política refere-se à atribuição de uma certa distribuição de probabilidade sobre ações a todas as histórias possíveis. Dada uma distribuição inicial fixa, podemos, portanto, atribuir o retorno esperado à política: onde a variável aleatória denota o retorno e é definida por: onde é a recompensa recebida após a -ésima transição, o estado inicial é amostrado aleatoriamente e as ações são selecionadas pela política. Aqui denota o momento aleatório em que um estado terminal é alcançado, ou seja, o momento em que o episódio termina. No caso de problemas não episódicos o retorno é muitas vezes descontado, dando origem ao critério de recompensa esperada para um desconto total. É o chamado fator de desconto. Como a devolução sem desconto é um caso especial de devolução com desconto, a partir de agora assumiremos o desconto. Embora isso pareça bastante inocente, o desconto é na verdade um problema se alguém se preocupa com o desempenho online. Isso ocorre porque o desconto torna o momento inicial das etapas mais importante. Uma vez que é provável que um agente de aprendizagem cometa erros durante os primeiros passos após a sua “vida” inicial, nenhum algoritmo de aprendizagem desinformado pode atingir um desempenho quase óptimo no desconto, mesmo que a classe de ambientes seja restrita à dos PDMs finitos. (Isto não significa, contudo, que, com tempo suficiente, um agente de aprendizagem não consiga compreender como agir de forma quase óptima se o tempo tiver sido reiniciado.) O problema então é especificar um algoritmo que possa ser utilizado para encontrar uma política com o desempenho máximo esperado. Da teoria do PDM sabe-se que, sem perda de generalidade, a busca pode ser restrita ao conjunto das chamadas políticas estacionárias. Uma política é chamada estacionária se a ação de distribuição que ela retorna depende apenas do último estado visitado (que faz parte do histórico de observação do agente, pela nossa suposição simplificadora). Na verdade, a pesquisa pode ser ainda mais restrita a políticas estacionárias determinísticas. Uma política estacionária determinística é aquela que seleciona deterministicamente ações com base no estado atual. Dado que qualquer uma destas políticas pode ser identificada com uma correspondência entre o conjunto de estados no conjunto de ações, estas políticas podem ser identificadas com estes tipos de atribuições, sem perda de generalidade.
força bruta
A abordagem de força bruta envolve os dois estágios a seguir:
Um problema disto é que o número de políticas pode ser extremamente grande, ou mesmo infinito. Outra é que a variância dos retornos pode ser grande, caso em que é necessário um grande número de amostras para estimar com precisão o retorno de cada política. Estes problemas podem ser atenuados utilizando alguma estrutura e permitindo que sejam geradas amostras a partir de uma política para influenciar as estimativas feitas por outra. As duas principais abordagens para alcançar este objetivo são uma função da estimativa do valor e da prossecução de políticas diretas.
Abordagem ao valor da função
As funções de valor tentam encontrar uma política que maximize os retornos, mantendo um conjunto de estimativas dos retornos esperados por alguma política (geralmente a "mainstream" ou a ótima). Esses métodos são baseados na teoria dos PDMs, onde a otimalidade é definida em um sentido mais forte que os anteriores: uma política é chamada de ótima se atinge um melhor desempenho esperado em qualquer estado inicial (ou seja, as distribuições iniciais não desempenham nenhum papel nesta definição). Mais uma vez, uma política óptima pode sempre ser encontrada entre políticas estacionárias. Para definir a otimalidade de forma formal, defina o valor de uma política por: onde significa o retorno aleatório associado ao seguinte do estado inicial. É definido como o valor máximo possível de , onde é permitido alterar: Uma política que atinge esses valores ótimos em cada estado é chamada de ótima. É evidente que uma política óptima neste sentido forte também é óptima no sentido de que maximiza o retorno esperado, uma vez que , onde é um estado da distribuição amostrada aleatoriamente. Embora os valores de estado sejam suficientes para definir o ideal, eles serão úteis para definir valores de ação. Dado um estado, uma ação e uma política de, o valor da ação do par baixo é definido por: onde, agora, significa o retorno aleatório associado à primeira ação no estado de e após, depois disso. É bem conhecido da teoria PDM que se alguém nos der uma política óptima, podemos sempre escolher acções óptimas simplesmente escolhendo a acção com o valor mais elevado em cada estado. A função de valor de ação de uma política ótima é chamada de função de valor de ação ideal e é representada por . Assumindo pleno conhecimento do MDP, existem duas abordagens básicas para calcular a função de valor de ação ideal, valor de iteração e política de repetição. Ambos os algoritmos calculam uma sequência de funções () que convergem para.
Os métodos de Monte Carlo mais simples podem ser usados em um algoritmo que imita políticas de iteração. A política de iteração consiste em duas etapas: avaliação e melhoria. Os Métodos de Monte Carlo são utilizados na etapa de avaliação. Nesta etapa, dada a política determinística estacionária, o objetivo é calcular os valores da função (ou uma boa aproximação deles) para todos os pares estado-ação. Vamos supor (para simplificar) que o MDP seja finito e que exista uma tabela de ações de estado na memória. Além disso, o problema é assumido como episódico e após cada episódio um novo começa a partir de um estado inicial aleatório. Então, a estimativa do valor de um determinado par estado-ações pode ser simplesmente calculada calculando a média dos retornos da amostra originados dele. Com tempo suficiente, este procedimento pode, portanto, construir uma estimativa precisa da função valor-ações. Isto encerra a descrição da etapa de avaliação da política. No estágio de melhoria da política, como feito no algoritmo de iteração, a próxima política é obtida calculando uma política gananciosa em relação a: Dado um estado, a nova política retorna uma ação que maximiza. Na prática, muitas vezes evita calcular e armazenar a nova política, mas utiliza a avaliação preguiçosa para adiar ações de maximização da computação quando for realmente necessário. Este procedimento pode causar alguns problemas como os seguintes:
Pesquisa política direta
Um método alternativo para encontrar uma boa política é pesquisar diretamente em (algum subconjunto) do espaço político, caso em que o problema se torna uma instância de otimização estocástica. As duas abordagens disponíveis são baseadas em métodos gradientes e sem gradiente. Os métodos baseados em gradiente (que dão origem aos chamados métodos de política de gradiente) começam com uma atribuição de um espaço (parâmetro) de dimensão finita ao espaço de política: dado o vetor de parâmetro, dado denota a política associada a. Defina a função de desempenho por: Sob condições amenas esta função será diferenciável como uma função do vetor de parâmetros. Se o gradiente fosse conhecido, a subida do gradiente poderia ser usada. Como uma expressão analítica para o gradiente não está disponível, deve-se confiar em uma estimativa ruidosa. Tal estimativa pode ser construída de várias maneiras, dando origem a algoritmos como o método Reinforce de Williams. Uma grande classe de métodos evita depender de informações de gradiente. Estes incluem recozimento simulado, pesquisa de entropia cruzada ou métodos de computação evolutiva. Muitos métodos livres de gradiente podem alcançar (em teoria e no limite) um ótimo global. Em vários casos, demonstraram de facto um desempenho notável. O problema com os métodos de pesquisa é que eles podem convergir lentamente se a informação em que se baseiam for ruidosa. Por exemplo, isto acontece quando em problemas episódicos as trajetórias são longas e a variância dos retornos é grande. Como argumentado anteriormente, métodos baseados em valores de características que dependem de diferenças temporais poderiam ajudar aqui. Nos últimos anos, vários algoritmos de atores e críticos foram propostos seguindo esta ideia e demonstraram bom desempenho em vários problemas.