Thereforewecanviewtheoriginaljointobservationspaceasthenewstatespace S: = Q iOi

Therefore,polynomial sample complexity for learning IIEFGs does not imply polynomial sample complexity resultsfor learningPOMGs. Delayed and state-action-dependent reward: different from our definition of reward in Section 2, now eachri,h is arandom function fromS Ato[0,1], and the rewards are revealed toeachlearner only atthe end ofeachepisode. Clearly, in this case the joint emission is identity and therefore satisfies the single-step weaklyrevealingcondition(Assumption1)withα=1. We view the entire interaction history as the state of IIEFG, that is, sh = (o1,a1,...,oh). First we rewrite Algorithm 1 in an equivalent form that is perfectly compatible with the analysisin[26].