Iterating through distributions *with weights*

[zsunberg]

Consider the case where there are only a few states that an MDP can transition to given the current state (e.g. GridWorld). This is quite common, and it would be very useful for beginners (e.g. AA228 students) to have the following stock distribution type in POMPDToolbox:

struct ObjectCategorical{VA<:AbstractArray, PA<:AbstractArray{Float64}}
    values::VA
    probabilties::PA
end

The problem is that the pdf(d::ObjectCategorical{T}, x::T) method requires us to find x in d.values every time. Often (e.g. in value iteration), we want to iterate through all of the values in a distribution and find each of their probabilities, which is needlessly slow if we use the current method

for x in iterator(d)
    # ...
    p = pdf(d, x)
    # ...
end

Should we add a new shortcut function to the POMDPs.jl interface that returns an iterator through pairs of value and probability? For example, we could call it weighted_iterator, it could have a default implementation of

weighted_iterator(d) = (x=>pdf(d, x) for x in iterator(d))

The implementation for ObjectCategorical would be

function weighted_iterator(d::ObjectCategorical)
    return (d.values[i]=>d.probabilities[i] for i in 1:length(d.values))
end

so

collect(weighted_iterator(ObjectCategorical([:a, :b, :c], [0.3, 0.2, 0.5])))

would output [:a=>0.3, :b=>0.2, :c=>0.5] - great for value iteration with no finding overhead in pdf.

What do people think of this?

[mykelk]

Should this be part of POMDPs.jl or a separate package?

[zsunberg]

weighted_iterator should be part of POMDPs I think because it could be used by multiple solvers and implemented by many problems. ObjectCategorical (or whatever we call it) should be in POMDPToolbox

[zsunberg]

Basically the reason I want to do this is because not having something like ObjectCategorical is a huge roadblock for new users - having to implement your own distributions makes implementing the transition function much, much more difficult. But, in order to make ObjectCategorical efficient at all, the weighted_iterator interface shortcut is necessary.

[zsunberg]

Every time I sat down with AA228 students to implement a problem, after defining the states I would say "ok, let's implement the transition function that will return a distribution", and then they would ask me "What is a distribution?", and they would have to both understand what a distribution is and what the transition function does. Having ObjectCategorical allows me to say "the distribution can just be a vector of states that we can transition to and a vector or probabilities for those states" and then we could focus on transition

[zsunberg]

Maybe we would even just call ObjectCategorical BasicDistribution or something.

[mykelk]

Okay, what about DiscreteDistribution? That would be part of POMDPToolbox, right? I don't see why we need weighted_iterator in POMDPs.jl. The problem writer doesn't have to use it. The solver writer would use it, of course, but this could be part of the toolbox, right?

[zsunberg]

yeah... I guess it could be part of the toolbox, but then we are putting interface in the toolbox. I kind of liked the clean distinction

interface -> POMDPs implementation -> POMDPToolbox

[zsunberg]

problem writers may want to use it if they want to implement their own custom distributions

[zsunberg]

by "use it" i mean "make their own custom implementation" in the comment above

[rejuvyesh]

@zsunberg Have you measured how slow the naive implementation actually is in comparison?

I don't think we should be adding more functions to the interface which may not necessarily be useful for everyone. But then again, this is from someone who thinks that GenerativeModel should have been a separate module (even if part of POMDPs).

[zsunberg]

yeah, it is very similar to generative models

[zsunberg]

I guess it can go in the toolbox, I suppose it is a lot like ordered_states

[mykelk]

Yeah, I think we should be pretty minimalistic with respect to POMDPs.jl.

[zsunberg]

thanks for chiming in @mykelk and @rejuvyesh that was helpful. I'll just put it in the toolbox