Wcześniej przyjęliśmy w pełni obserwowalne, deterministyczne, znane środowisko. Dzięki temu agent może obserwować stan początkowy, obliczać sekwencję działań, które prowadzą do celu i wykonywać je z „zamkniętymi oczami”, nigdy nie musząc używać swoich percepcji. Kiedy jednak środowisko jest częściowo obserwowalne, osoba nie wie na pewno, w jakim jest stanie; a gdy środowisko jest niedeterministyczne, agent nie wie, do jakiego stanu przechodzi po wykonaniu działania. Oznacza to, że zamiast myśleć „Jestem w stanie s1 i jeśli podejmę działanie, skończę w stanie s2 ”, agent będzie teraz myślał „Jestem w stanie s1 lub s3 , a jeśli podejmę działanie Skończę w stanie s2, s4 lub s5”. Zbiór stanów fizycznych, które według agenta są możliwe, nazywamy stanem przekonań. W środowiskach częściowo obserwowalnych i niedeterministycznych rozwiązanie problemu nie jest dłuższa sekwencja, ale raczej plan warunkowy (czasami nazywany planem awaryjnym lub strategią), który określa, co należy zrobić w zależności od tego, jakie percepty otrzymuje agent podczas wykonywania planu. W tej części zbadamy niedeterminizm, a w następnej częściową obserwowalność.